[알고리즘] BFS 너비 우선 탐색 - 자바스크립트 코드 포함 간략한 설명

너비 우선 탐색 (BFS, Breadth-first search) 시작 정점에서 시작하여 인접한 모든 정점을 방문하는 방법이다. 

재귀호출을 사용하는 DFS와 다르게 자료 구조 큐 Queue를 사용하는 방식이 일반적이다.

정점에 연결되는 모든 갈림길을 탐색을 하다보니 어떠한 시작점과 끝점이 주어졌을때 그 둘 사이의 최단 거리 구하기에 용이하다.

 

아래 그림을 보며 살펴보자. 그림에선 시작 정점을 ㄱ으로 본다. 

 

시작 정점을 기준으로 인접한 정점은 ㄴ,ㄷ,ㄹ이다.

그리하여, ㄴ,ㄷ,ㄹ 정점을 방문한다. 

그 후, ㄴ에 인접한 ㅁ,ㅂ,ㅅ 정점을 방문하고, ㄷ,ㄹ도 마찬가지로 인접한 정점을 차례대로 방문한다. 

 

 

DFS와 달리 너비를 기준으로 순회하는 방식이다. 

 

 

다음 그림의 트리를 너비 우선 탐색으로 순회하여 값을 프린트해보자.

function solution() {
  let answer = "";
  let queue = [];
  queue.push(1);
  while (queue.length) {
    let v = queue.shift();
    answer += v + " ";
    for (let x of [v * 2, v * 2 + 1]) {
      if (x > 7) continue;
      queue.push(nv);
    }
  }
  return answer; // 프린트: 1 2 3 4 5 6 7
}

 

위의 코드와 같이 for 문을 이용해 현재 위치 정점 v에 인접한 v*2, v*2+1에 방문한다. 

자료 구조 queue를 이용하여 방문한 정점을 기록한다. 

방문할 정점이 더는 없을때 즉, queue의 길이가 0이 될때까지 동작한다.