BFS (너비 우선 탐색)

그래프 시작 정점으로부터 가까운 정점부터 순차적으로 방문해나가는 탐색 알고리즘이다.

인접한 정점들을 먼저 방문하고, 그 다음 그들의 인접 정점을 방문하는 방식으로 진행된다.

즉, 최단 경로를 찾을 때 많이 사용한다.

 

💡 BFS의 정당성

✅ 시작정점에서 도달 가능한 모든 정점을 정확히 한 번씩 방문한다.

1. Queue에서 정점 u를 꺼낸다.

2. u에 인접한 모든 정점 v를 확인한다.

3. 방문❌ 정점 v는 방문 표시를 하고, 큐에 삽입한다.

즉, 한 번 방문한 정점은 다시 큐에 삽입❌ → 정점은 정확히 한 번 방문한다.

 

💡 BFS의 최단 경로성

✅ BFS는 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는다.

- 시작 정점 s에서 각 정점까지의 거리 : d(v) (= 간선의 수)

- BFS는 항상 거리가 적은 정점부터 큐에 들어가게 되어 있다.

1. d(s) = 0 (시작 정점의 거리 = 0)

2. s에 인접한 모든 정점의 거리는 1

3. 거리 1인 정점들이 모두 처리⭕ → 거리 2인 정점들 방문

 

즉, ⭐거리가 k인 정점들이 처리되어야 k+1 정점들이 처리된다.따라서, BFS는 거리가 짧은 정점부터 탐색을 확장하기에 시작 정점 s에서 어떤 정점 v까지 도달할 때, 항상 최소 간선 수로 도달하게 된다.

 

🌐 시간복잡도 : O(|V|+|E|)

* V : 정점 수

* E : 간선 수