BFS (너비 우선 그래프 순회)

해당 내용은 UDEMY의 알고리즘 ∙ 자료구조 강의를 수강 후 정리한 내용입니다.

너비 우선은 주어진 노드의 인접점을 모두 방문하고 아래로 내려가거나 인접점의 인접점을 보는 형식을 의미합니다.

너비 우선에서 가장 중요한 점은 ‘주어진 점에 대해 모든 인접점을 우선적으로 처리하는 것’입니다.

BFS 만들기

DFS와 BFS의 차이점은 다른 종류의 데이터 구조를 사용해, BFS는 큐(queue)를 쓴다는 것입니다. 이로 인해 먼저 들어갔던 것들이 먼저 나오게 됩니다. 코드로는 아래와 같습니다.

breadthFirst(start) {
  const queue = [start];
  // queue에 처음에 들어오는 값을 대입
  const result = [];
  // 결과로 사용될 배열
  const visited = {};
  // 방문했음을 알려주는 객체
  let curVertex;
  // 현재 노드의 정보

  visited[start] = true;
  // start 변수는 이미 방문된 것으로 처리되기에 visited에 넣어줌
  while (queue.length) {
  // while 문을 돌면서 설정된 queue에 아무 값이 없을 경우 순환을 끝냄
    curVertex = queue.shift();
    // BFS에서 가장 중요한 부분으로, 들어간 값들의 가장 앞부분부터 빼냄
    result.push(curVertex);

    this.graph[curVertex].forEach((nextVertex) => {
    // 이웃 값들에 대해 방문하지 않았을 시 방문하기 위해 queue에 넣어줌
      if (!visited[nextVertex]) {
        visited[nextVertex] = true;
        queue.push(nextVertex);
      }
    });
  }

  return result;
}

{
  A: [ 'B', 'C' ],
  B: [ 'A', 'D' ],
  C: [ 'A', 'E' ],
  D: [ 'B', 'E', 'F' ],
  E: [ 'C', 'D', 'F' ],
  F: [ 'D', 'E' ]
}
// graph

[ 'A', 'B', 'C', 'D', 'E', 'F' ]
// result

위 그림과 같은 순서로 진행되게 되며, DFS 중에서도 반복을 통한 순회와 같은 방식으로 코드가 진행된다는 것을 볼 수 있습니다. 차이점은 앞서 말한 바와 같이 데이터 구조 사용 시 stack이 아닌 queue를 써야 한다는 사실만 주의하면 BFS를 통한 순회를 하는 데에는 큰 문제가 없습니다.

GITHUB  EMAIL