무가중 최단 경로
지하철 최소 환승, 두 사람 사이의 지인 단계 수는 모두 무가중 그래프의 최단 경로 문제로, BFS로 풀린다. 탐색 파동이 목적지에 처음 닿는 순간의 경로가 곧 최단 경로다.
격자 미로에서 너비 우선 탐색의 확장 과정과 최단 경로 역추적 시각화.
미로를 직접 그린 뒤 너비 우선 탐색을 실행해, 큐가 같은 거리의 칸을 동심원처럼 넓혀 가고 부모 링크를 되짚어 최단 경로를 복원하는 과정을 단계별로 확인합니다.
너비 우선 탐색은 시작점에서 같은 거리의 셀을 한 겹씩 동심원처럼 확장한다. 가중치 없는 격자에서 goal에 처음 닿는 순간이 곧 최단경로이며, 부모 링크를 거꾸로 따라가면 그 경로가 복원된다.
시간복잡도 O(V + E)
dist(v) = dist(u) + 1
지하철 최소 환승, 두 사람 사이의 지인 단계 수는 모두 무가중 그래프의 최단 경로 문제로, BFS로 풀린다. 탐색 파동이 목적지에 처음 닿는 순간의 경로가 곧 최단 경로다.
친구 추천의 friend-of-friend, 웹 크롤러의 링크 깊이 제한, 네트워크 브로드캐스트 홉 수 계산은 격자가 아닌 그래프 위에서 도는 BFS다. 8방향 이동을 켜면 이웃 정의가 결과를 바꾸는 것이 드러난다.
BFS는 거리 k의 셀을 모두 처리한 뒤에야 k+1로 넘어간다. 이 단조성 때문에 목적지에 처음 도달한 경로가 최단임이 증명된다. 거리 숫자를 켜면 동심원 레이어로 확인할 수 있다.