정보실

웹학교

정보실

javascript JavaScript에서 8 가지 필수 그래프 알고리즘을 구현하는 방법

본문

이 기사에서는 JavaScript에서 그래프의 검색 및 조합 문제 (순회, 최단 경로 및 일치)를 탐색하는 8 개의 그래프 알고리즘을 구현합니다.


How to Implement 8 Essential Graph Algorithms in JavaScript 


https://www.freecodecamp.org/news/8-essential-graph-algorithms-in-javascript/ 


문제는 Java의 프로그래밍 인터뷰 요소 (Elements of Programming Interviews in Java) 책에서 차용됩니다. 이 책의 솔루션은 소유 한 책의 버전에 따라 Java, Python 또는 C ++로 코딩됩니다.


문제 모델링의 논리는 언어에 구애 받지 않지만 이 기사에서 제공하는 코드 스니펫은 몇 가지 JavaScript주의 사항을 사용합니다.


각 문제에 대한 모든 솔루션은 솔루션 개요, 의사 코드 및 마지막으로 JavaScript의 실제 코드의 3 가지 섹션으로 구분됩니다.


코드를 테스트하고 수행해야 할 작업을 확인하려면 Chrome의 개발 도구를 사용하여 브라우저 자체에서 스니펫을 실행하거나 NodeJS를 사용하여 명령 행에서 실행할 수 있습니다.


그래프 구현 


가장 일반적으로 사용되는 2 가지 그래프 표현은 인접 목록과 인접 행렬입니다.


내가 풀게 될 문제는 희소 그래프에 대한 것이며 (가장자리가 적음) 인접 목록 접근 방식의 정점 연산은 일정한 (정점 추가, O (1)) 선형 시간 (정점 삭제, O (V + E) )). 그래서 저는 그 구현을 대부분 고수하겠습니다.


인접 목록을 사용하여 간단한 무 방향, 비가 중 그래프 구현으로 이를 해결해 봅시다. 그래프의 모든 정점을 키로 포함하는 객체 (adjacencyList)를 유지합니다. 값은 모든 인접한 정점의 배열입니다. 아래 예에서 꼭짓점 1은 꼭짓점 2와 4에 연결되어 있으므로 다른 꼭짓점의 adjacencyList : {1 : [2, 4]} 등입니다.


그래프를 작성하기 위해 addVertex와 addEdge의 두 가지 기능이 있습니다. addVertex는 목록에 꼭짓점을 추가하는 데 사용됩니다. addEdge는 방향이 지정되지 않은 그래프이므로 인접한 정점을 소스 및 대상 배열 모두에 추가하여 정점을 연결하는 데 사용됩니다. 유 방향 그래프를 만들려면 아래 코드에서 14–16 및 18 행을 제거하면 됩니다.


정점을 제거하기 전에 인접한 정점의 배열을 반복하고 해당 정점에 대한 가능한 모든 연결을 제거해야 합니다.


image_1_graphs.jpg 

인접 목록을 사용하여 구현 된 무 방향, 비가 중 그래프


class Graph {
  constructor() {
    this.adjacencyList = {};
  }
  addVertex(vertex) {
    if (!this.adjacencyList[vertex]) {
      this.adjacencyList[vertex] = [];
    }
  }
  addEdge(source, destination) {
    if (!this.adjacencyList[source]) {
      this.addVertex(source);
    }
    if (!this.adjacencyList[destination]) {
      this.addVertex(destination);
    }
    this.adjacencyList[source].push(destination);
    this.adjacencyList[destination].push(source);
  }
  removeEdge(source, destination) {
    this.adjacencyList[source] = this.adjacencyList[source].filter(vertex => vertex !== destination);
    this.adjacencyList[destination] = this.adjacencyList[destination].filter(vertex => vertex !== source);
  }
  removeVertex(vertex) {
    while (this.adjacencyList[vertex]) {
      const adjacentVertex = this.adjacencyList[vertex].pop();
      this.removeEdge(vertex, adjacentVertex);
    }
    delete this.adjacencyList[vertex];
  }  
}

그래프 순회 


이전 섹션의 그래프 구현을 바탕으로 그래프 탐색 (폭 우선 검색 및 깊이 우선 검색)을 구현합니다.


너비 우선 검색 


BFS는 한 번에 한 레벨 씩 노드를 방문합니다. 동일한 노드를 두 번 이상 방문하지 못하게 하기 위해 방문한 개체를 유지 관리합니다.


First In First Out 방식으로 노드를 처리해야 하므로 큐는 데이터 구조에서 사용하기에 좋은 경쟁자입니다. 시간 복잡도는 O (V + E)입니다.


function BFS
   Initialize an empty queue, empty 'result' array & a 'visited' map
   Add the starting vertex to the queue & visited map
   While Queue is not empty:
     - Dequeue and store current vertex
     - Push current vertex to result array
     - Iterate through current vertex's adjacency list:
       - For each adjacent vertex, if vertex is unvisited:
         - Add vertex to visited map
         - Enqueue vertex
   Return result array

깊이 첫 검색 


DFS는 노드를 깊이 방문합니다. Last In First Out 방식으로 노드를 처리해야 하므로 스택을 사용합니다.


정점에서 시작하여 인접한 정점을 스택으로 푸시합니다. 꼭짓점이 터질 때마다 방문한 객체에서 방문으로 표시됩니다. 인접한 정점이 스택으로 푸시됩니다. 우리는 항상 새로운 인접 정점을 팝하기 때문에 알고리즘은 항상 새로운 수준을 탐색합니다.


또한 내장 스택 호출을 사용하여 DFS를 재귀 적으로 구현할 수 있습니다. 논리는 동일합니다.


시간 복잡도는 BFS, O (V + E)와 동일합니다.


function DFS
   Initialize an empty stack, empty 'result' array & a 'visited' map
   Add the starting vertex to the stack & visited map
   While Stack is not empty:
     - Pop and store current vertex
     - Push current vertex to result array
     - Iterate through current vertex's adjacency list:
       - For each adjacent vertex, if vertex is unvisited:
         - Add vertex to visited map
         - Push vertex to stack
   Return result array
Graph.prototype.bfs = function(start) {
    const queue = [start];
    const result = [];
    const visited = {};
    visited[start] = true;
    let currentVertex;
    while (queue.length) {
      currentVertex = queue.shift();
      result.push(currentVertex);
      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          queue.push(neighbor);
        }
      });
    }
    return result;
}
Graph.prototype.dfsRecursive = function(start) {
    const result = [];
    const visited = {};
    const adjacencyList = this.adjacencyList;
    (function dfs(vertex){
      if (!vertex) return null;
      visited[vertex] = true;
      result.push(vertex);
      adjacencyList[vertex].forEach(neighbor => {
          if (!visited[neighbor]) {
            return dfs(neighbor);
          }
      })
    })(start);
    return result;
}
Graph.prototype.dfsIterative = function(start) {
    const result = [];
    const stack = [start];
    const visited = {};
    visited[start] = true;
    let currentVertex;
    while (stack.length) {
      currentVertex = stack.pop();
      result.push(currentVertex);
      this.adjacencyList[currentVertex].forEach(neighbor => {
        if (!visited[neighbor]) {
          visited[neighbor] = true;
          stack.push(neighbor);
        }
      });
    }
    return result;
}

미로 찾기 


문제 설명:


지정된 입구와 출구 지점이 있는 미로를 나타내는 2D 흑백 항목 배열이 주어지면 입구에서 출구까지의 경로를 찾으십시오. – Aziz, Adnan 등 프로그래밍 인터뷰 요소


흰색은 0으로, 검은 색은 1로 표시합니다. 흰색 항목은 열린 영역과 검은 색 항목 벽을 나타냅니다. 시작 및 종료 지점은 각각 행 및 열 색인으로 채워진 배열, 0 번째 색인 및 1 번째 색인으로 표시됩니다.


Screen-Shot-2020-05-30-at-7.40.29-PM.png 

2D 배열로 표현되는 미로


해결책:


다른 위치로 이동하기 위해 길 찾기 배열에서 네 가지 가능한 움직임을 하드 코딩합니다 (오른쪽, 아래쪽, 왼쪽 및 상단, 대각선 이동 없음).


[ [0,1], [1,0], [0,-1], [-1,0] ]

이미 방문한 셀을 추적하기 위해 흰색 항목 (0)을 검은 색 항목 (1)으로 바꿉니다. 우리는 기본적으로 미로를 가로 지르기 위해 DFS를 재귀적으로 사용하고 있습니다. 재귀를 끝내는 기본 사례는 종료점에 도달하여 true를 반환하거나 모든 흰색 항목을 방문하여 false를 반환하는 것입니다.


추적해야 할 또 다른 중요한 사항은 우리가 항상 미로의 경계 안에 있는지 확인하고 우리가 백인 입장에 처한 경우에만 진행하는 것입니다. isFeasible 함수가 이를 처리합니다.


시간 복잡도 : O (V + E)


의사 코드 :


function hasPath
   Start at the entry point
   While exit point has not been reached
     1. Move to the top cell
     2. Check if position is feasible (white cell & within boundary)
     3. Mark cell as visited (turn it into a black cell)
     4. Repeat steps 1-3 for the other 3 directions
var hasPath = function(maze, start, destination) {
    maze[start[0]][start[1]] = 1;
    return searchMazeHelper(maze, start, destination);
};
function searchMazeHelper(maze, current, end) { // dfs
    if (current[0] == end[0] && current[1] == end[1]) {
        return true;
    }
    let neighborIndices, neighbor;
    // Indices: 0->top,1->right, 2->bottom, 3->left 
    let directions = [ [0,1] , [1,0] , [0,-1] , [-1,0] ];
    for (const direction of directions) {
        neighborIndices = [current[0]+direction[0], current[1]+direction[1]];
        if (isFeasible(maze, neighborIndices)) {
            maze[neighborIndices[0]][neighborIndices[1]] = 1;
            if (searchMazeHelper(maze, neighborIndices, end)) {
                return true;
            }
        }
    }
    return false;
}
function isFeasible(maze, indices) {
    let x = indices[0], y = indices[1];
    return x >= 0 && x < maze.length && y >= 0 && y < maze[x].length && maze[x][y] === 0;
}
var maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]]
hasPath(maze, [0,4], [3,2]);

불리언 매트릭스 페인트 


문제 설명:


n x m 부울 배열 A를 항목 (x, y)과 함께 사용하고 (x, y)와 연관된 영역의 색상을 뒤집는 루틴을 구현하십시오. – Aziz, Adnan 등 프로그래밍 인터뷰 요소


2 가지 색상은 0과 1로 표시됩니다.


아래 예에서 배열의 중심 ([1,1])에서 시작합니다. 이 위치에서 가장 왼쪽의 삼각 행렬에만 도달 할 수 있습니다. 가장 오른쪽에 있는 가장 낮은 위치에 도달 할 수 없습니다 ([2,2]). 따라서 프로세스가 끝나면 뒤집지 않은 유일한 색상입니다.


imgonline-com-ua-twotoone-H6wQUCSVtaaILRR.jpg 

n x m 색상 반전 전후의 부울 배열


해결책:


  • 앞의 질문에서와 같이 4 가지 가능한 동작을 정의하기 위해 배열을 코딩합니다.
  • 그래프를 탐색하기 위해 BFS를 사용할 것입니다.
  • isFeasible 함수를 약간 수정하겠습니다. 새 위치가 행렬의 경계 내에 있는지 여전히 확인합니다. 다른 요구 사항은 새 위치에 이전 위치와 동일한 색상이 지정되어야 합니다. 새 위치가 요구 사항에 맞으면 색상이 반전됩니다.
  • 시간 복잡도 : O (mn)

의사 코드 :


function flipColor
   Start at the passed coordinates and store the color
   Initialize queue
   Add starting position to queue
   While Queue is not empty:
     - Dequeue and store current position
     - Move to the top cell
       1. Check if cell is feasible
       2. If feasible,
          - Flip color
          - Enqueue cell
       3. Repeat steps 1-2 for the other 3 directions
function flipColor(image, x, y) {
    let directions = [ [0,1] , [1,0] , [0,-1] , [-1,0] ];
    let color = image[x][y];
    let queue = [];
    image[x][y] = Number(!color);
    queue.push([x,y]);
    let currentPosition, neighbor;
    while (queue.length) {
        currentPosition = queue.shift();
        for (const direction of directions) {
            neighbor = [currentPosition[0]+direction[0], currentPosition[1]+direction[1]];
            if (isFeasible(image, neighbor, color)) {
                image[neighbor[0]][neighbor[1]] = Number(!color);
                queue.push([neighbor[0], neighbor[1]]);
            }
        }
    }
    return image;
}
function isFeasible(image, indices, color) {
    let x = indices[0], y = indices[1];
    return x >= 0 && x < image.length && y >= 0 && y < image[x].length && image[x][y] == color;
}
var image = [[1,1,1],[1,1,0],[1,0,1]];
flipColor(image,1,1);

둘러싸인 지역 계산 


문제 설명:


항목을 W 또는 B 인 2D 배열로 A를 지정합니다. A를 사용하고 경계에 도달 할 수 없는 모든 W를 B로 대체하는 프로그램을 작성하십시오. – Aziz, Adnan, et al. 프로그래밍 인터뷰 요소


1-Yjky-DB8p7ABUk3n37GXRA.png 

동봉 된 전후 격자


해결책:


  • 동봉 된 W 항목을 찾기 위해 모든 항목을 반복하는 대신 경계 W 항목으로 시작하고 그래프를 통과하고 연결된 W 항목을 표시하는 것이 가장 좋습니다. 이 표시된 항목은 보드 테두리의 W 항목에 연결되어 있으므로 동봉 되지 않습니다. 이 전처리는 기본적으로 프로그램이 달성해야 하는 것의 보완입니다.
  • 그런 다음 A가 다시 반복되고 표시되지 않은 W 항목 (동봉 된 항목)이 B 항목으로 변경됩니다.
  • A와 동일한 차원의 부울 배열을 사용하여 표시 및 표시되지 않은 W 항목을 추적합니다. 표시된 항목은 true로 설정됩니다.
  • 시간 복잡도 : O (mn)


의사 코드 :


function fillSurroundedRegions
   1. Initialize a 'visited' array of same length as the input array
      pre-filled with 'false' values
   2. Start at the boundary entries
   3. If the boundary entry is a W entry and unmarked:
         Call markBoundaryRegion function
   4. Iterate through A and change the unvisited W entry to B
function markBoundaryRegion
   Start with a boundary W entry
   Traverse the grid using BFS
   Mark the feasible entries as true
function fillSurroundedRegions(board) {
    if (!board.length) {
        return;
    }
    const numRows = board.length, numCols = board[0].length;
    let visited = [];
    for (let i=0; i<numRows; i++) {
        visited.push(new Array(numCols).fill(false, 0, numCols));
    }
    for (let i=0; i<board.length; i++) {
        if (board[i][0] == 'W' && !visited[i][0]) {
            markBoundaryRegion(i, 0, board, visited);
        }
        if (board[i][board.length-1] == 'W' && !visited[i][board.length-1]) {
            markBoundaryRegion(i, board.length-1, board, visited);
        }
    }
    for (let j=0; j<board[0].length; j++) {
        if (board[0][j] == 'W' && !visited[0][j]) {
            markBoundaryRegion(0, j, board, visited);
        }
        if (board[board.length-1][j] == 'W' && !visited[board.length-1][j]) {
            markBoundaryRegion(board.length-1, j, board, visited);
        }
    }
    for (let i=1; i<board.length-1; i++) {
        for (let j=1; j<board.length-1; j++) {
            if (board[i][j] == 'W' && !visited[i][j]) {
                board[i][j] = 'B';
            }
        }
    }
    return board;
}
function markBoundaryRegion(i, j, board, visited) {
    let directions = [ [0,1] , [1,0] , [0,-1] , [-1,0] ];
    const queue = [];
    queue.push([i,j]);
    visited[i][j] = true;
    let currentPosition, neighbor;
    while (queue.length) {
        currentPosition = queue.shift();
        for (const direction of directions) {
            neighbor = [i+direction[0], j+direction[1]];
            if (isFeasible(board,visited,neighbor)) {
                visited[neighbor[0]][neighbor[1]] = true;
                queue.push(neighbor);
            }
        }
    }
}
function isFeasible(board, visited, neighbor) {
    let x = neighbor[0], y = neighbor[1];
    return x >= 0 && x < board.length && y >= 0 && y < board[x].length && board[x][y] == 'W';
}
var board = [['B','B','B','B'],['W','B','W','B'],['B','W','W','B'],['B','B','B','B']];
fillSurroundedRegions(board);

교착 상태 감지 (방향 그래프의 사이클) 


문제 설명:


한 교착 상태 탐지 알고리즘은 "대기"그래프를 사용하여 프로세스가 현재 차단하고 있는 다른 프로세스를 추적합니다. 대기 그래프에서 프로세스는 노드로 표시되며 프로세스 P에서 0까지의 엣지는 0에 P가 필요한 자원을 보유하고 있음을 의미하므로 P는 0이 해당 자원에 대한 잠금을 해제하기를 기다리고 있습니다. 이 그래프의 주기는 교착 상태 가능성을 나타냅니다. 이것은 다음과 같은 문제를 유발합니다. 유 방향 그래프를 입력으로 받아 그래프에 사이클이 포함되어 있는지 확인하는 프로그램을 작성하십시오. – Aziz, Adnan 등 프로그래밍 인터뷰 요소


1-Gn3M8mF6rHb2vu4z4d36_Q.gif 

대기 그래프의 예 (a)


위의 대기 그래프에서 교착 상태 감지 프로그램은 하나 이상의 주기를 감지하고 true를 리턴합니다.


이 알고리즘의 경우 다른 데이터 구조를 탐색하기 위해 약간 다른 방향 그래프의 구현 그래프를 사용합니다. 인접 목록을 사용하여 계속 구현하고 있지만 객체 (맵) 대신 정점을 배열에 저장합니다.


프로세스는 0 번째 프로세스부터 정점으로 모델링 됩니다. 프로세스 간의 종속성은 정점 간의 에지로 모델링 됩니다. 가장자리 (인접한 정점)는 링크 된 목록에 저장되고 프로세스 번호에 해당하는 색인에 저장됩니다.


class Node {
    constructor(data) {
        this.data = data;
        this.next = null;
    }
}
class LinkedList {
    constructor() {
        this.head = null;
    }
    insertAtHead(data) {
        let temp = new Node(data);
        temp.next = this.head;
        this.head = temp;
        return this;
    }
    getHead() {
        return this.head;
    }
}
class Graph {
    constructor(vertices) {
        this.vertices = vertices;
        this.list = [];
        for (let i=0; i<vertices; i++) {
            let temp = new LinkedList();
            this.list.push(temp);
        }
    }
    addEdge(source, destination) {
        if (source < this.vertices && destination < this.vertices) {
            this.list[source].insertAtHead(destination);
        }
        return this;
    }
}

1-ml99O-kqmyAxL73GdeAnqQ.png 

대기 그래프 (a) 구현


해결책:


  • 모든 정점에는 흰색, 회색 및 검은 색의 세 가지 색상이 할당됩니다. 처음에는 모든 정점이 흰색으로 표시됩니다. 정점을 처리 할 때는 회색으로 처리되고 검은 색으로 처리 된 후에 색이 지정됩니다.
  • 깊이 우선 검색을 사용하여 그래프를 탐색하십시오.
  • 회색 꼭짓점에서 다른 회색 꼭짓점으로 가장자리가 있으면 뒷면 가장자리 (자기 루프 또는 조상 중 하나에 연결되는 가장자리)가 발견되어주기가 감지됩니다.
  • 시간 복잡도 : O (V + E)

의사 코드 :


function isDeadlocked
   Color all vertices white
   Run DFS on the vertices
     1. Mark current node Gray
     2. If adjacent vertex is Gray, return true
     3. Mark current node Black
   Return false
const Colors = {
    WHITE: 'white', 
    GRAY: 'gray', 
    BLACK: 'black'
}
Object.freeze(Colors);
function isDeadlocked(g) {
    let color = [];
    for (let i=0; i<g.vertices; i++) {
        color[i] = Colors.WHITE;
    }
    for (let i=0; i<g.vertices; i++) {
        if (color[i] == Colors.WHITE) {
             if (detectCycle(g, i, color)) {
                return true;
             }   
        }
    }
    return false;
};
function detectCycle(g, currentVertex, color) {
    color[currentVertex] = Colors.GRAY;
    let neighbor;
    let nextNode = g.list[currentVertex].getHead();
    while (nextNode !== null) {
        neighbor = nextNode.data;
        if (color[neighbor] == Colors.GRAY) {
            return true;
        }
        if (color[neighbor] == Colors.WHITE && detectCycle(g, neighbor, color)) {
            return true;
        }
    }
    color[currentVertex] = Colors.BLACK;
    return false;
}
let g = new Graph(3);
g.addEdge(0,1);
g.addEdge(0,2);
isDeadlocked(g);

클론 그래프 


문제 설명:


정수 레이블과 다른 정점에 대한 참조 목록이라는 두 개의 필드가 있는 지향 그래프의 정점 유형을 고려하십시오. 꼭짓점 u에 대한 참조를 사용하고 u에서 도달 할 수 있는 꼭짓점에 그래프 사본을 생성하는 알고리즘을 설계하십시오. u의 사본을 반환하십시오. – Aziz, Adnan 등 프로그래밍 인터뷰 요소


해결책:


  • 원래 정점을 해당 정점에 매핑 하는 맵을 유지하십시오. 가장자리 위로 복사하십시오.
  • BFS를 사용하여 인접한 정점 (가장자리)을 방문하십시오.
  • 시간 복잡도 : O (n). 여기서 n은 총 노드 수입니다.

의사 코드 :


function cloneGraph
   Initialize an empty map
   Run BFS
   Add original vertex as key and clone as value to map
   Copy over edges if vertices exist in map
   Return clone
class GraphVertex {
    constructor(value) {
        this.value = value;
        this.edges = [];
    }
}
function cloneGraph(g) {
    if (g == null) {
        return null;
    }
    let vertexMap = {};
    let queue = [g];
    vertexMap[g] = new GraphVertex(g.value);
    while (queue.length) {
        let currentVertex = queue.shift();
        currentVertex.edges.forEach(v => {
            if (!vertexMap[v]) {
                vertexMap[v] = new GraphVertex(v.value);
                queue.push(v);
            }
            vertexMap[currentVertex].edges.push(vertexMap[v]);
        });
    }
    return vertexMap[g];
}
let n1 = new GraphVertex(1);
let n2 = new GraphVertex(2);
let n3 = new GraphVertex(3);
let n4 = new GraphVertex(4);
n1.edges.push(n2, n4);
n2.edges.push(n1, n3);
n3.edges.push(n2, n4);
n4.edges.push(n1, n3);
cloneGraph(n1);

유선 연결하기 


문제 설명:

핀 쌍과 핀 쌍을 연결하는 전선 세트를 취하는 알고리즘을 설계하고 PCB의 왼쪽 절반에 핀을 배치 할 수 있는지 여부와 나머지 절반을 오른쪽 절반에 배치하여 각 와이어가 왼쪽과 오른쪽 절반 사이. 그러한 부서가 존재하면 이를 반환하십시오. – Aziz, Adnan 등 프로그래밍 인터뷰 요소


1-Ye3P_VA_65-B708FzPCpTg.png 

그러한 부서의 예


해결책:


세트를 그래프로 모델링 하십시오. 핀은 꼭짓점으로 표시되며 핀을 연결하는 와이어는 가장자리입니다. 가장자리 목록을 사용하여 그래프를 구현합니다.


문제 설명에 설명 된 쌍은 모든 정점 (u, v)이 U에서 V로 정점을 연결하거나 V에서 정점을 연결하도록 정점 (핀)을“2 개의 독립적 인 세트 U와 V로 나눌 수 있는 경우에만 가능합니다. U에게” (소스) 이러한 그래프를 이분 그래프라고 합니다.


그래프가 이분인지 여부를 확인하기 위해 그래프 채색 기술을 사용합니다. 두 개의 핀 세트가 필요하므로 그래프가 2 색 (0과 1로 표시됨)인지 확인해야 합니다.


처음에는 모든 정점이 색상이 없습니다 (-1). 인접한 정점에 동일한 색상이 할당되면 그래프가 두 부분이 아닙니다. 2 가지 색상 만 사용하여 홀수 길이 주기로 그래프에 두 가지 색상을 번갈아 할당 할 수 없으므로 그래프를 탐욕스럽게 채색 할 수 있습니다.


추가 단계 : 연결되지 않은 그래프의 경우를 처리합니다. 바깥 쪽 for 루프는 모든 정점을 반복하여 처리합니다.


시간 복잡도 : O (V + E)


의사 코드 :

function isBipartite
   1. Initialize an array to store uncolored vertices
   2. Iterate through all vertices one by one
   3. Assign one color (0) to the source vertex
   4. Use DFS to reach the adjacent vertices
   5. Assign the neighbors a different color (1 - current color)
   6. Repeat steps 3 to 5 as long as it satisfies the two-colored     constraint
   7. If a neighbor has the same color as the current vertex, break the loop and return false
function isBipartite(graph) {
    let color = [];
    for (let i=0; i<graph.length; i++) {
        color[i] = -1;
    }
    for (let i=0; i<graph.length; i++) {
        if (color[i] == -1) {
            let stack = [];
            stack.push(i);
            color[i] = 0;
            let node;
            while (stack.length) {
                node = stack.pop();
                for (const neighbor of graph[node]) {
                    if (color[neighbor] == -1) {
                        stack.push(neighbor);
                        color[neighbor] = 1 - color[node];
                    }
                    else if (color[neighbor] == color[node]) {
                        return false;
                    }
                }
            }
        }
    }
    return true;
}
isBipartite([[],[2,4,6],[1,4,8,9],[7,8],[1,2,8,9],[6,9],[1,5,7,8,9],[3,6,9],[2,3,4,6,9],[2,4,5,6,7,8]]);

한 문자열을 다른 문자열로 변환 


문제 설명:


사전 D와 두 개의 문자열 s와 f가 주어지면 s가 t를 생성하는지 판별하는 프로그램을 작성하십시오. 모든 문자가 소문자 알파벳이라고 가정하십시오. s가 f를 생성하면 가장 짧은 생산 시퀀스의 길이를 출력합니다. 그렇지 않으면 -1을 출력하십시오. – Aziz, Adnan 등 프로그래밍 인터뷰 요소


예를 들어 사전 D가 [ "hot", "dot", "dog", "lot", "log", "cog"] 인 경우 s는 "hit"이고 t는 "cog"입니다. 최단 생산 순서는 5입니다. "hit"-> "hot"-> "dot"-> "dog"-> "cog"


해결책:


해당 문자열이 최대 한 문자에서 다를 경우 2 개의 정점 사이의 가장자리를 사용하여 무 방향, 무가 중 그래프에서 문자열을 정점으로 나타냅니다. 두 문자열 사이의 문자 차이를 계산하는 함수 (compareStrings)를 구현합니다.


이전 예제를 피기 백하면 그래프의 정점이


{hit, hot, dot, dog, lot, log, cog}

섹션 0에서 논의한 인접 목록 접근 방식으로 표현되는 에지는 다음과 같습니다. 그래프 구현은 다음과 같습니다.


{
    "hit": ["hot"],
    "hot": ["dot", "lot"],
    "dot": ["hot", "dog", "lot"],
    "dog": ["dot", "lot", "cog"],
    "lot": ["hot", "dot", "log"],
    "log": ["dog", "lot", "cog"],
    "cog": ["dog", "log"]
}

그래프 작성을 마치면 시작 노드에서 종료 노드까지의 최단 경로를 찾는 문제가 해결됩니다. 이것은 너비 우선 검색을 사용하여 자연스럽게 계산할 수 있습니다.


시간 복잡도 : O (M x M x N). 여기서 M은 각 단어의 길이이고 N은 사전의 총 단어 수입니다.


의사 코드 :


function compareStrings
   Compare two strings char by char
   Return how many chars differ
function transformString
   1. Build graph using compareStrings function. Add edges if and only if  the two strings differ by 1 character
   2. Run BFS and increment length
   3. Return length of production sequence
function transformString(beginWord, endWord, wordList) {
    let graph = buildGraph(wordList, beginWord);
    if (!graph.has(endWord)) return 0;
    let queue = [beginWord];
    let visited = {};
    visited[beginWord] = true;
    let count = 1;
    while (queue.length) {
        let size = queue.length;
        for (let i=0; i<size; i++) {
            let currentWord = queue.shift();
            if (currentWord === endWord) {
                return count;
            }
            graph.get(currentWord).forEach( neighbor => {
                if (!visited[neighbor]) {
                    queue.push(neighbor);
                    visited[neighbor] = true;
                }
            })
        }
        count++;
    }
    return 0;
};

function compareStrings (str1, str2) {
    let diff = 0;
    for (let i=0; i<str1.length; i++) {
        if (str1[i] !== str2[i]) diff++
    }
    return diff;
}

function buildGraph(wordList, beginWord) {
    let graph = new Map();
    wordList.forEach( (word) => {
        graph.set(word, []);
        wordList.forEach( (nextWord) => {
            if (compareStrings(word, nextWord) == 1) {
                graph.get(word).push(nextWord);
            }
        })
    })
    if (!graph.has(beginWord)) {
        graph.set(beginWord, []);
        wordList.forEach( (nextWord) => {
            if (compareStrings(beginWord, nextWord) == 1) {
                graph.get(beginWord).push(nextWord);
            }
        })
    }
    return graph;
}

여기서 어디로 가야 합니까? 


이 기사가 끝날 무렵, 그래프 문제에서 가장 어려운 부분은 문제를 그래프로 모델링 하는 방법을 식별하는 것입니다. 여기에서 두 개의 그래프 순회를 사용 / 수정하여 예상 출력을 얻을 수 있습니다.


툴킷에 포함 된 다른 그래프 알고리즘은 다음과 같습니다.


  • 토폴로지 순서
  • 최단 경로 알고리즘 (Dijkstra 및 Floyd Warshall)
  • 최소 스패닝 트리 알고리즘 (Prim and Kruskal)



페이지 정보

조회 22회 ]  작성일20-06-27 15:49

웹학교