너비 우선 탐색: 가까운 정점부터 방문하는 큐의 역할
너비 우선 탐색은 출발 정점에서 간선 한 개로 도달하는 정점들, 두 개로 도달하는 정점들처럼 거리 층을 넓혀 가는 방법이다. 모든 간선의 비용이 같을 때 최소 간선 수 경로를 구할 수 있다. 핵심 도구는 먼저 발견한 정점을 먼저 처리하는 큐다.
왼쪽 이웃을 먼저 넣는 이 예시의 방문 순서는 A·B·C·D·E다.
발견한 순간에 방문 표시하기
출발점의 거리를 0으로 놓고 큐에 넣는다. 정점을 꺼낼 때 아직 발견하지 않은 이웃의 거리를 현재 거리+1로 정하고 큐에 넣는다. 큐에 넣을 때 방문을 표시해야 여러 부모가 같은 이웃을 중복 추가하는 것을 막는다.
A가 B,C와 연결되고 B가 D, C가 E와 연결되면 A를 처리한 뒤 큐는 B,C다. B가 D를 추가해도 D는 C 뒤에 있으므로 같은 거리 층이 먼저 처리된다. 큐에는 거리가 앞쪽보다 갑자기 작아지는 정점이 들어오지 않는다.
from collections import deque
def shortest_hops(graph, source):
distance = {source: 0}
predecessor = {source: None}
pending = deque([source])
while pending:
current = pending.popleft()
for neighbor in graph[current]:
if neighbor in distance:
continue
distance[neighbor] = distance[current] + 1
predecessor[neighbor] = current
pending.append(neighbor)
return distance, predecessor
위 코드는 그래프의 목록에 이웃 정점만 저장한다고 가정한다. predecessor를 따라 목적지에서 출발점 쪽으로 되짚고 뒤집으면 실제 경로를 복원할 수 있다. 도달하지 못한 정점은 distance에 나타나지 않는다.
처음 발견한 거리가 왜 최소인가
거리 d인 정점이 처리될 때 그보다 가까운 정점의 이웃은 이미 검사됐다. 아직 발견하지 않은 이웃으로 가는 더 짧은 경로가 있었다면 그 경로의 직전 정점이 먼저 처리하여 발견했어야 한다. 따라서 최초 거리 d+1이 최소라는 논리가 성립한다.
인접 리스트에서는 방문한 정점과 간선을 한 번씩 확인하여 O(V+E)이고, 거리·부모·큐는 O(V) 공간이 필요하다. 인접 행렬에서는 이웃 확인에 행 전체를 읽으므로 비용이 O(V²)로 달라질 수 있다.
가중치가 서로 다르면 최소 간선 수가 최소 비용을 뜻하지 않는다. 직접 간선 비용이 100이고 두 단계 경로가 2+2라면 BFS가 먼저 발견한 한 단계 경로는 최저 비용이 아니다. 가중치 조건에 맞는 다른 알고리즘을 써야 한다.
모든 연결 요소를 방문하려면 미방문 정점마다 탐색을 시작해야 한다. 단일 출발점 BFS는 그 출발점에서 도달 가능한 범위만 본다. 이웃 순서에 따라 같은 길이의 경로 중 하나가 선택될 수 있지만, 최소 거리 보장은 유지된다.