Breadth-First Search(BFS): 레벨 단위 그래프 탐색

BFS는 시작점과 가까운 정점부터 순서대로 탐색하는 알고리즘입니다.

Level 0
Level 1
Level 2
...

FIFO 방식의 Queue를 사용합니다.

JavaScript

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

  while (head < queue.length) {
    const current = queue[head++];

    order.push(current);

    for (const next of graph[current] ?? []) {
      if (visited.has(next)) continue;
      visited.add(next);
      queue.push(next);
    }
  }

  return order;
}

정점은 Queue에 넣는 순간 visited 처리하는 것이 좋습니다.

무가중 최단 경로

BFS는 간선 개수가 적은 정점부터 방문하므로 최초 발견 거리가 최소 간선 거리입니다.

parent를 저장하면 실제 경로도 복원할 수 있습니다.

BFS와 DFS

BFS는 Queue와 레벨 탐색을 사용합니다. DFS는 Stack 또는 recursion으로 깊게 탐색합니다.

Grid와 Maze

각 Cell을 Vertex, 이동을 Edge로 모델링하면 동일 비용 이동에서 최소 이동 횟수를 찾을 수 있습니다.

Multi-Source BFS

여러 Source를 distance 0으로 동시에 Queue에 넣습니다.

Bidirectional BFS

Start와 Target이 모두 알려진 경우 양쪽에서 탐색해 상태 공간을 줄일 수 있습니다.

0-1 BFS

Weight가 0 또는 1뿐이라면 Deque 기반 0-1 BFS를 사용할 수 있습니다.

활용

• Social Network
• Maze/Grid
• Web Crawling
• Connected Components
• Bipartite Check
• Minimum Moves

복잡도

시간: O(V + E)
공간: O(V)

정리

무가중 그래프의 최단 거리, 가장 가까운 상태, 최소 이동 횟수, Level Order가 필요하면 BFS를 우선 고려할 수 있습니다.