문제해결 전략 - 29. 그래프 너비 우선 탐색

BFS vs DFS visualization (credit:  https://github.com/kdn251/interviews ).

그래프 너비 우선 탐색

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

구현 방법

• 각 정점을 방문할 때 마다 모든 인접 정점들을 검사한다.
• 이중 처음 보는 정범을 발견하면 이 정점을 방문 예정이라고 기록한 뒤 별도의 위치에 저장한다.
• 인접한 정점을 모두 검사하고 나면 지금까지 저장한 목록에서 다음 정점을 꺼내서 방문한다.
• 정점의 목록에서 어떤 정점을 먼저 꺼내는지에 의해 결정된다.

특징

• 깊이 우선 탐색과 달리 너비 우선 탐색에서는 발견과 방문이 같지 않다.
• 모든 정점은 아래와 같은 세 상태를 순서대로 거친다.
  1. 아직 발견되지 않은 상태
  2. 발견되었지만 아직 방문되지 않은 상태(정점들의 목록이 큐에 저장되어 있음)
  3. 방문된 상태

시간 복잡도

• 깊이 우선 탐색과 같다. 
• 모든 정점을 한 번씩 방문하며, 정점을 방문할 때마다 인접한 모든 간선을 검사한다.
• LinkedList로 구현되었을 시 O(|V|+|E|),
• 인접 행렬로 구현했을 시 O(|V|^2) 

최단 거리

• 너비 우선 탐색은 딱 하나의 용도로 사용된다 : 최단 경로 문제
• 두 정점을 연결하는 경로 중 가장 길이가 짧은 경로를 찾는 문제
• 그래프 이론의 가장 고전적인 문제
• 모든 정점에 대해 시작점으로 부터 거리 distance[]를 계산해 보자
• (u, v)를 통해 정점 v를 처음 발견 해 큐에 넣었다고 가정한다.
• 이때 시작점으로 부터 v까지의 최단거리 distance[v]는 시작점으로 부터 u까지의 최단거리 distance[u]+1 이다.
• 증명은 아래와 같다.
  1. distance[v] 가 distance[u]+1보다 클 수 없다.
  2. distance[v]가 distance[u]+1보다 작을 수 없다.
• 결국 시작점으로 부터 다른 모든 정점까지의 최단 경로는 
  너비 우선 탐색 스패닝 트리 위에서 찾을 수 있다.
• 최단경로 : 각 정점으로 부터 트리의 루트인 시작점으로 가는 경로가 실제 그래프 상에서 최단 경로임을 알 수 있다.

*그래프 전체 구조에 관한 정보를 얻기 위해 사용되는 깊이 우선 탐색과 달리 너비 우선 탐색은 대게 시작점으로 부터 다른 정점까지의 거리를 구하기 위해 사용된다. 

*너비 우선 탐색은 모든 정점을 검사하면서 탐색을 수행하는 작업은 하지 않는다.