[알고리즘] Graph(1) - BFS(Breadth-First Search)

1. Graph 주요 용어

• vertex : 정점
• edge : 간선 (정점과 정점을 연결한 선)
• color : 정점에 색깔을 부여하여 방문 상태를 확인하는 용도

• white vertex   : 아직 방문된 적이 없는 정점

• gray vertex    : 방문은 되었지만 인접한 정점들 중에 white vertex가 존재, 즉 더 이상 탐색이 가능한 정점의 상태

• black vertex   : 인접한 모든 정점 중 white vertex가 없음, 즉 더 이상 탐색이 불가능한 정점의 상태

• 선행자( π )       : 부모 정점을 저장하는 용도

• d ( distance )     : 정점까지의 거리

• 큐 ( queue )      : 회색정점의 집합을 관리

2. BFS( Breadth-First Search )

BFS는 출발 정점(start vertex 또는 root vertex)에 대해  조건에 맞는 인접한 정점들을 연결합니다.

그리고 이 정점들에 대해서도 인접한 정점들을 연결하는 과정을 반복하여, 출발 정점으로부터 모든 각 정점까지의 거리가 저장된 하나의 트리를 만드는 것이 목적입니다.

BFS의 이해를 돕기 위해 그림으로 과정을 살펴보고, 수도코드를 분석해보도록 하겠습니다.

초기화된 상태입니다.

시작을 v1 정점으로 합니다.

v1정점을 방문을 한 것이니 gray가 되고, 큐에 추가합니다.

또한 자기 자신은 거리가 0 입니다.

Step2의 큐에서 dequeue되는 것은 v1이므로, v1의 인접 정점들을 확인합니다.

v2, v5 두 정점의 상태가 white이므로, 두 정점을 방문합니다.

v1으로부터 거리가 1이므로 업데이트를 하고, 상태를 gray로 바꾸고, 두 정점을 큐에 추가합니다.

이 때 큐에 추가되는 정점의 순서는 상관이 없습니다.

구현하기 나름이며, 어떤 순서로 하든 결과는 같습니다.

v1은 이제 더 나아갈 정점이 없으니 상태를 black으로 바꿉니다.

Step3의 큐에서 dequeue되는 것은 v2이므로, v2의 인접 정점들을 확인합니다.

v3, v4 두 정점의 상태가 white이므로, 두 정점을 방문합니다.

v1으로부터 거리가 2이므로 업데이트를 하고, 상태를 gray로 바꾸고, 두 정점을 큐에 추가합니다.

v2은 이제 더 나아갈 정점이 없으니 상태를 black으로 바꿉니다.

Step4의 큐에서 dequeue되는 것은 v5이므로, v5의 인접 정점들을 확인합니다.

그런데 v4의 상태는 gray이기 때문에 방문을 하지 않으며,

인접한 다른 정점 중에서 white 상태인 v6정점을 방문합니다.

v5은 이제 더 나아갈 정점이 없으니 상태를 black으로 바꿉니다.

이후의 과정은 위와 같으므로 생략하도록 하겠습니다.

이 그림은 위의 그래프의 모든 정점들과 연결된 간선들을 트리로써 표현해본 것입니다.

BFS는 너비를 우선으로 하는 검색입니다.

즉, 시작정점으로 부터 각 정점들이 얼마나 떨어져 있는지 표현하는 것이죠.

2. 수도코드

다음으로 수도코드를 살펴보도록 하겠습니다.

1) line 1 ~ 4

초기화 작업입니다. s를 제외한 모든 정점의 color를 white로, 거리를 무한대로, 선행자를 NIL로 초기화 합니다.

위의 그림에서 선행자를 언급하지 않았는데, 선행자란 예를들어 v1이 v2를 방문했을 때 v2의 선행자는 v1이 됩니다.

2) line 5 ~ 9

시작 정점 s의 color를 gray로, 거리를 0으로, 선행자를 NIL로 초기화 합니다.

그리고 큐(Q)에 s를 추가합니다.

3) line 10 ~ 18

Q가 비어있게 될 때 까지 반복문을 수행하며, 매 수행마다 큐에서 정점을 하나씩 dequeue합니다.

그리고 그 정점에 대해 모든 인접한 정점들을 방문할 예정입니다.

인접한 정점의 상태가 white이면 상태를 gray로 바꾸고, 거리를 이전 정점(u)의 거리에서 +1을 하고, 선행자를 이전 정점으로 합니다.

만약 인접한 정점의 상태가 white가 아니라면 아무일도 일어나지 않고 다음 인접한 정점을 검사합니다.

모든 인접한 정점을 확인했으면, u는 더 이상 방문할 정점이 없으므로 상태를 black으로 바꿉니다.

4) 시간복잡도

BFS의 시간복잡도는 12행 내부에 의해 결정됩니다.

13행의 조건문은 최대 |E| (간서의 개수) 만큼 수행되고, 그 내부는 |V|만큼의 시간이 걸립니다.

( 13행의 2|E|는 방향 그래프일 때이며, |E|는 무방향 그래프일 때를 의미합니다. )

따라서 θ( |V| + |E| ) 만큼의 시간복잡도가 됩니다.

이상으로 넓이 우선 탐색 BFS에 대해 알아보았습니다.

BFS는 인접한 정점들을 연결할 때, color로 상태를 확인하며, 또 gray color의 정점들을 저장하는 자료구조 큐가 사용되었습니다.