[자료구조] 15. BFS

Breadth First Search(BFS)는 그래프 탐색 방식중 하나이다. BFS는 시작 정점을 기준으로 가까운 정점부터 차례대로 방문하는 방식이다. 이런 특성을 통하여 가중치가 없는 간선 그래프에서 가장 가까운 경로를 발견할때 사용할 수 있다.

구현

시작 정점 v에서 출발하고, 큐 Q에 시작 정점을 추가하고 VISITED 상태로 만든 후 다음 과정을 반복한다.

1. Q가 비었다면 종료한다. 정점이 있다면 해당 정점 v에 대하여 다음을 실행한다

2. v에 인접한 정점중 UNVISITED인 정점을 큐에 삽입하고, VISITED상태로 변경한다.

용어

unvisited vertex: 아직 방문하지 않은 정점

visited vertex: 방문한 정점

unexlored edge: 아직 방문하지 않은 간선

discovery edge: 방문한 간선으로, 해당 간선으로 진행하여 새로운 정점을 찾은 경우.

cross edge: 방문한 간선으로, 해당 간선으로 진행하였지만, 이미 방문한 정점이였던 경우. 이때 BFS의 특성에 따라서 cross edge는 같거나 1 낮은 level을 가지는 정점으로만 연결된다.

효율

정점과 간선에 접근하고, VISITED인지 확인하거나 VISITED로 라벨을 변경하는것에 O(1) 시간이 소요된다.

즉, n개의 정점과 m개의 간선을 가진 그래프에서 BFS는 O(n + m)의 시간 복잡도를 가진다.

응용

최적 경로찾기