JS로 BFS, DFS 구현

위 와 같은 그래프를 탐색하는 알고리즘은 크게 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)으로 나뉩 니다.

위 그림과 같은 그래프를 탐색하는 알고리즘을 js로 구현해 보려 합니다.

 

 BFS

• 위 그림과 같이 너비를 우선으로 탐색 => 현재 정점에가 같은 deps에 있는 노드들은 먼저 방문한다는 뜻
• 탐색 중인 현재 노드에서 인접한 노드를 먼저 방문
• 최단 거리를 찾을 때 주로 사용
• 자료구조 queue를 사용하여 구현

 DFS

• 방문할 수 있는 최대 deps를 우선적으로 방문
• 루트 노드에서 시작해서 해당 그래프의 최대 deps 까지 탐색, 더이상 탐색할 수 없다면 되돌아가 다시 최대 deps로 방문
• stack 혹은 재귀 함수로 구현 가능

 code

const graph = {
  A: ["B", "D"],
  B: ["A", "E", "F"],
  D: ["A", "I", "J"],
  E: ["B"],
  F: ["B"],
  I: ["D"],
  J: ["D"],
};

const printBFS = [];
const printDFS = [];
const printRecursiveDFS = [];

// queue 사용
function BFS(graph, start) {
  const visited = [];
  const queue = [start];

  visited.push(start);

  while (queue.length > 0) {
    const node = queue.shift();
    printBFS.push(node);

    for (const adjNode of graph[node]) {
      if (!visited.includes(adjNode)) {
        visited.push(adjNode);
        queue.push(adjNode);
      }
    }
  }
}

// stack 사용
function DFS(graph, start) {
  const visited = [];
  const stack = [start];

  while (stack.length > 0) {
    const node = stack.pop();

    if (!visited.includes(node)) {
      visited.push(node);
      printDFS.push(node);
      for (const adjNode of graph[node]) {
        stack.push(adjNode);
      }
    }
  }
}

// 재귀함수 사용
function RecursiveDFS(graph, start, visited)  {
  visited.push(start);
  printRecursiveDFS.push(start);

  for (const adjNode of graph[start]) {
    if (!visited.includes(adjNode)) {
      RecursiveDFS(graph, adjNode, visited);
    }
  }
};

BFS(graph, "A");
console.log("BFS : ", printBFS.join(" "));
DFS(graph, "A");
console.log("DFS : ", printDFS.join(" "));
RecursiveDFS(graph, "A", []);
console.log('DFS Recursive : ',printRecursiveDFS.join(" "));

출력