BFS는 왜 항상 최단거리를 보장할까?

1. 전제

BFS는 모든 간선의 가중치가 동일한 그래프에서만 최단거리를 보장한다.

 

2. BFS가 동작하는 방식

BFS는 시작 정점에서부터 거리 순으로 탐색한다

- 0 거리 -> 시작점

- 1 거리 -> 시작점과 인접한 점들

- 2 거리 -> 거리 1 점들의 인접점들

   (A)
  /   \
(B)   (C)
 |     |
(D)   (E)
 \     /
   (F)

1) A에서 시작 (거리 0)

2) B, C 방문 (거리 1)

3) D, E 방문 (거리 2)

4) F 방문 (거리 3)

즉, A에서 F까지의 최단 경로는 A-B-D-F 또는 A-C-E-F, 거리 3이다. 

from collections import deque

def bfs_shortest_distance(graph, start):
    visited = set()
    distance = {start: 0}
    queue = deque([start])
    
    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                distance[neighbor] = distance[current] + 1
                queue.append(neighbor)
    
    return distance

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

distances = bfs_shortest_distance(graph, 'A')
print(distances)

3. 왜 최단거리일까?

BFS는 큐를 사용해 다음 점을 가까운 순서대로 방문한다.

즉, 어떤 점을 방문했을때 그 정점까지 도달한 경로는, 그 정점을 가장 먼저 방문한 경로이기 때문에 최단거리이다.

이후에 다시 그 점을 방문하게 된다면, 이미 더 짧은 경로로 방문했기 때문에 무시된다.