3. 그래프의 너비 우선 탐색

3.1 너비 우선 탐색 (Breadth First Search, BFS) 란?

깊이 우선 탐색과 함께 그래프 탐색 방식의 두 축을 이루는 탐색 방법

• 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘

BFS EX)

• 너비 우선 탐색 스패닝 트리 (BFS Spanning Tree) : 너비 우선 탐색에서 새 정점을 발견하는 데 사용했던 간선들만 모은 트리

• a에서 부터 최소 몇개의 간선을 지나야 도달할 수 있는 가를 기준으로 그래프의 정점을 나눔

• $H_i$ : 간선을 i 개 지나야 도착할 수 있는 정점의 집합

1. $H_0$에 속한 a를 가장 먼저 방문
2. $H_1$, $H_2$, $H_3$에 속한 정점들을 순서대로 방문
3. 각 정점과 시작점 사이에 경로가 두 개 이상인 경우, 그중 최단 경로가 방문 순서를 결정 EX) b나 d → a와 길이 1인 경로로도 연결되어 있고, 2인 경로로도 연결되어 있지만 $H_1$에 속함

• 너비 우선 탐색은 각 정점을 방문할 때마다 모든 인접 정점들을 검사
• 처음 보는 정점을 발견하면 방문 예정이라고 기록 ➡ 별도의 위치에 저장