[JavaScript] 그래프 알고리즘

인접한 노드를 탐색하는 자료구조로, DFS나 BFS를 이용하여 탐색한다.

DFS로 탐색하는 구조

• 어떤 노드에서 어떤 노드로 갈수 있는지 여부 파악하기
• 몇개의 덩어리로 나눠져있는지 파악하기
• 백트래킹(모든 노드를 탐색하며 조건에 맞는 것들의 수 세기)

function dfs(graph, visited, node) {
  if (visited[node]) return;

  visited[node] = true;
  console.log("Visiting:", node);

  for (let neighbor of graph[node]) {
    dfs(graph, visited, neighbor);
  }
}

// 예시
const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 4],
  3: [1],
  4: [2]
};

const visited = Array(Object.keys(graph).length).fill(false);
dfs(graph, visited, 0);

 

BFS로 탐색하는 구조 (출발 노드와의 거리를 찾는 문제 등에서 사용)

function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [[start, 0]];
  const result = [];

  while (queue.length > 0) {
    const [node, depth] = queue.shift();
    result.push({ node, depth });

    for (const next of graph[node]) {
      if (!visited.has(next)) {
        visited.add(next);
        queue.push([next, depth + 1]);
      }
    }
  }

  console.table(result);
}

const graph = {
  1: [3],
  3: [1, 6, 4],
  6: [3, 2],
  4: [3, 2],
  2: [6, 4, 5],
  5: [2]
};

bfs(graph, 1);

 

문제에 따라 인접노드 테이블(graph)을 주지 않고 '간선'의 좌표(vertex)를 주는 경우가 있는데 그럴때는 인접노드 테이블로 바꿔줘야 한다.

for (const [a, b] of edge) {
    const graph = {};
    
    if (!graph[a]) {
        graph[a] = [];
    }

    if (!graph[b]) {
        graph[b] = [];
    }

    graph[a].push(b);
    graph[b].push(a);
}