Breadth-First Search

핵심 아이디어

BFS의 동작 원리는 단순하다. 시작 노드를 방문하고, 그 이웃을 모두 큐에 넣는다. 큐에서 노드를 하나씩 꺼내면서 아직 방문하지 않은 이웃을 다시 큐에 넣는다. Queue의 FIFO 특성 때문에, 시작 노드에서 거리 1인 노드를 모두 처리한 뒤에야 거리 2인 노드를 처리하게 된다. 이것이 BFS가 레벨 순서대로 탐색하는 이유다.

위 그래프에서 노드 A부터 BFS를 수행하면, 먼저 A의 이웃인 B와 C를 방문하고, 그 다음에 B와 C의 이웃인 D, E, F를 방문한다. 탐색 순서는 A → B → C → D → E → F가 된다.

알고리즘

function BFS(graph, start) returns visited order
    queue ← empty queue
    visited ← empty set

    visited.add(start)
    queue.enqueue(start)

    while queue is not empty do
        current ← queue.dequeue()
        for each neighbor of current do
            if neighbor not in visited then
                visited.add(neighbor)
                queue.enqueue(neighbor)

핵심은 발견 시점에 visited에 추가한다는 것이다. 큐에서 꺼낼 때가 아니라 큐에 넣을 때 방문 처리를 해야 같은 노드가 큐에 중복으로 들어가는 것을 방지할 수 있다.

탐색 예시

아래 그래프에서 A를 시작으로 BFS를 수행하는 과정을 단계별로 살펴보자. 간선은 모두 비용 1의 무방향 간선이다.

    A
   / \
  B   C
 / \   \
D   E   F

Step 1 — A를 방문하고 큐에 넣는다. 큐: [A].

Step 2 — A를 꺼내고 이웃 B, C를 방문 처리 후 큐에 넣는다. 큐: [B, C].

Step 3 — B를 꺼내고 이웃 D, E를 방문 처리 후 큐에 넣는다. 큐: [C, D, E].

Step 4 — C를 꺼내고 이웃 F를 방문 처리 후 큐에 넣는다. 큐: [D, E, F].

Step 5 — D를 꺼낸다. 미방문 이웃이 없다. 큐: [E, F].

Step 6 — E를 꺼낸다. 미방문 이웃이 없다. 큐: [F].

Step 7 — F를 꺼낸다. 미방문 이웃이 없다. 큐: []. 탐색 종료.

최종 방문 순서: A → B → C → D → E → F. 시작 노드로부터의 거리가 같은 노드들이 묶여서 처리되는 것을 확인할 수 있다 — 거리 0: {A}, 거리 1: {B, C}, 거리 2: {D, E, F}.

Python 구현

from collections import deque
from typing import Optional


def bfs(
    graph: dict[str, list[str]],
    start: str,
    goal: Optional[str] = None,
) -> list[str] | Optional[tuple[int, list[str]]]:
    """Breadth-First Search.

    Args:
        graph: 인접 리스트. {노드: [이웃, ...]}.
        start: 시작 노드.
        goal:  목표 노드 (None이면 전체 탐색).

    Returns:
        goal이 None이면 방문 순서 리스트.
        goal이 주어지면 (최단 거리, 경로) 또는 None.
    """
    visited = {start}
    queue = deque([(start, [start])])
    order = []

    while queue:
        current, path = queue.popleft()
        order.append(current)

        if goal and current == goal:
            return len(path) - 1, path

        for neighbor in graph.get(current, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    if goal:
        return None
    return order

collections.deque의 popleft()가 $O(1)$이므로, 리스트의 pop(0) ($O(n)$)을 사용하는 것보다 효율적이다.

시간 복잡도와 공간 복잡도

BFS는 모든 노드를 한 번씩, 모든 간선을 한 번씩(무방향이면 두 번씩) 탐색하므로 시간 복잡도는 $O(V + E)$이다. 여기서 $V$는 노드 수, $E$는 간선 수다.

공간 복잡도도 $O(V)$이다. 최악의 경우 한 레벨의 모든 노드가 큐에 들어갈 수 있으며, 이는 트리의 가장 넓은 레벨의 너비에 해당한다. 분기 계수(branching factor)가 $b$이고 최적 해의 깊이가 $d$일 때, 큐에 최대 $O(b^d)$개의 노드가 들어갈 수 있다.

최단 경로 보장

BFS가 최단 경로를 보장하는 것은 모든 간선의 비용이 동일할 때에 한한다. BFS는 시작 노드에서 $k$번 이동하여 도달할 수 있는 모든 노드를 $k+1$번 이동하여 도달할 수 있는 노드보다 먼저 탐색한다. 따라서 어떤 노드에 처음 도달했을 때의 경로가 곧 최단 경로가 된다.

간선 비용이 서로 다르면 이 보장이 깨진다. "한 번 이동"이 비용 1일 수도, 비용 100일 수도 있기 때문이다. 이 경우에는 Uniform-Cost Search나 A*처럼 누적 비용을 고려하는 알고리즘이 필요하다.

BFS와 다른 알고리즘의 관계

BFS는 Best-First Search 프레임워크에서 $f(n) = \text{depth}(n)$으로 설정한 것으로 볼 수 있다. 모든 간선 비용이 1이면 $g(n) = \text{depth}(n)$이므로, 이 경우 BFS는 Uniform-Cost Search와 동일하게 동작한다.

Depth-First Search는 BFS와 정반대로, Stack(LIFO)을 사용하여 가장 깊은 노드부터 탐색한다. BFS는 최단 경로를 보장하지만 메모리 사용량이 크고, DFS는 메모리 효율이 좋지만 최단 경로를 보장하지 않는다.

어디에 쓰이는가

BFS는 비가중 그래프에서의 최단 경로 탐색에 가장 널리 쓰인다. 소셜 네트워크에서 두 사용자 간의 최소 연결 단계를 구하거나, 미로에서 최단 탈출 경로를 찾는 것이 대표적이다. 웹 크롤러가 링크를 따라가며 페이지를 수집하는 것도 BFS의 응용이며, 네트워크에서 브로드캐스트 메시지가 전파되는 방식 역시 BFS와 같은 패턴을 따른다. 트리에서의 레벨 순서 순회(level-order traversal)는 BFS 그 자체다.

---

출처

• Cormen, T. H. et al. (2022) Introduction to Algorithms. 4th edn. Cambridge, MA: MIT Press. Chapter 20.2.
• Russell, S. and Norvig, P. (2021) Artificial Intelligence: A Modern Approach. 4th Global edn. Harlow: Pearson. Chapter 3.4.1.