[BFS/DFS] 너비우선탐색과 깊이우선탐색

BFS(Breadth First Search, 너비 우선 탐색)

• 정점들과 같은 레벨에 있는 노드를 먼저 탐색함.
• 구현에 큐를 사용한다.
• Root Node로부터 가장 가까운 Node부터 탐색하므로 Root Node와 가까이 있는 Target Node를 찾는데 유용하다.
• 최단거리 탐색, SNS 친구추천 등에 사용되고 있음.
• 시간복잡도 O(N)

 

DFS(Depth First Search, 깊이 우선 탐색)

• Root Node에 이어진 Child Node들 부터 먼저 탐색함.
• 구현에 스택을 사용한다.
• BFS보다 속도가 느릴 수 있다.
• 미로게임 등에서 경로가 존재하는지 여부를 판단할 때 유용하다.
• 시간복잡도 O(N)

 

탐색 방식 비교

출처:  https://www.fun-coding.org/

• BFS: A - B - C - D - G - H - I - E - F - J
• DFS: A - B - D - E - F - C - G - H - I - J

BFS 구현

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

const bfs = (graph, startNode) => {
  let visited = []; // 탐색 완료 노드
  let notVisit = []; // 아직 탐색하지 않은 노드

  notVisit.push(startNode);

  while (notVisit.length !== 0) { // 탐색을 모두 완료할 때 까지 반복
    const node = notVisit.shift(); // 맨 앞에 있는 노드 
    if (!visited.includes(node)) { // 해당 노드가 탐색된 적 없다면
      visited.push(node); 
      notVisit = [...notVisit, ...graph[node]];
    }
  }
  return visited;
};

console.log(bfs(graph, "A"));
// ["A", "B", "C", "D", "G", "H", "I", "E", "F", "J"]

DFS 구현

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

// (graph, 시작 정점)
const dfs = (graph, startNode) => {
  let notVisitStack = []; // 탐색하지 않은 노드
  let visitedQueue = []; // 탐색종료 노드

  needVisitStack.push(startNode);

  while (notVisitStack.length !== 0) { // 모든 노드가 탐색 완료시 까지
    const node = notVisitStack.pop();
    if (!visitedQueue.includes(node)) {
      visitedQueue.push(node);
      notVisitStack = [...notVisitStack, ...graph[node]];
    }
  }

  return visitedQueue;
};

console.log(dfs(graph, "A"));

// ["A", "C", "I", "J", "H", "G", "B", "D", "F", "E"]

 

참고자료: https://youtube.com/watch?v=_hxFgg7TLZQ&feature=share