dfs가 선위 순회와 비슷하다면 bfs는 레벨 순회와 유사하다.
bfs는 순회 출발 정점의 부착간선들부터 우선 방문하는 것이 bfs와의 차이점이다. bfs는 dfs가 해결하는 문제들과 매우 비슷하다.
너비우선탐색(Breadth-First Search)
bfs 의사코드
for each v from G.vertex()
if(l(v) = fresh){
bfs(v)
}Alg bfs(v)
input graph G, start vertex v
output labeling of edges of G in connected component of v
as tree & cross edges
i = 0
L[i] <- empty list
L[i].add(v)
l(v) <- visit
while(!L[i].isEmpty()) {
L[i+1] <- empty list
for each v from L[i] {
for each e from G.incidentEdges(v) {
if(l(e) = fresh){
w <- G.opposite(v, e)
if(l(w) = fresh) {
l(e) <- tree
l(w) <- visit
L[i+1].add(w)
} else {
l(e) <- cross
}
}
}
}
i++
}
returnbfs는 외부 메모리를 사용하고 dfs와 달리 재귀 호출을 하지 않는다. i는 0부터 시작하고 i번째 리스트에 정점들을 차곡차곡 담아 i번째 리스트에 들어있는 정점들을 모두 검사하면 i+1번째를 검사한다.
먼저 출발 정점 v를 i(현재 0)번째 리스트에 담고 반복문을 탄다.
L[i]에 들어 있는 모든 정점을 추출해 해당 정점에 대한 부착간선을 모두 검사한다.
부착간선 e가 fresh고 opposite 정점 w도 fresh면 e는 tree, w는 visit 표시 후 w를 L[i+1]에 삽입한다.
부착간선 e가 fresh고 opposite 정점 w가 visit이면, e에 cross 표시 후 v의 다음 부착간선을 검사한다.
부착간선 e가 fresh가 아니면, 다음 부착간선을 검사한다.
그림의 예시로 bfs의 이해를 도와보자.
bfs 그림 수행 예시
정점과 간선의 초기화를 다 한 후 A부터 bfs를 수행한다고 가정하자.
L[0]에 A를 담고 시작한다. A에 대한 모든 부착간선의 검사를 수행하면 L[1] = {B, C, D}가 될 것이고 간선들은 tree 표시가 된다.
A에 대한 검사를 마치면 L[0]의 모든 정점을 검사했기 때문에 i가 1 증가해 반복문은 L[1]을 바라 본다. L1이 비어 있지 않아 B를 먼저 추출해 B의 부착간선을 본다.
(B, A) 간선은 tree 상태이고 (B, C)의 간선은 fresh이지만 C가 visit이기 때문에 간선에 cross를 표시한다. (B, E) 간선은 fresh 상태이고 E도 fresh이기 때문에 L[2]에 정점 E를 추가한다.
이렇게 쭉쭉 수행하면 최종 그래프가 완성이 되고 cross를 지우면 A를 루트로 하는 것 같은 신장트리가 완성된다. 예시 그래프는 연결그래프이기 때문에 모든 정점을 취급할 수 있다.
완성된 bfs에 각 리스트를 넘버링하게 되면 위의 형태가 된다. 리스트의 넘버는 출발 정점 A에서 도착 정점까지는 최소한 도착 정점이 속한 리스트의 넘버만큼의 간선이 필요하다는 의미가 된다.
비트리간선
dfs에서는 back이라는 후향 간선 처리를, bfs는 cross라는 교차 간선 처리를 한다.
후향 간선은 출발 정점을 향해 올라가는 액션을 취한다. 출발 정점을 루트라 했을 때, 후향 간선은 부모 노드로 향하는 간선이 된다.
교차 간선은 출발 정점을 루트라 했을 때, 형제 노드나 조카 노드로 향하는 간선이 된다.
bfs 성능
dfs와 마찬가지로 정점, 간선 라벨 수정에는 상수 시간이 표시된다. 각 정점은 fresh로 1번, visit으로 1번하여 총 2번 수정을 거치고 각 간선은 fresh로 1번 이외의 것으로 1번하여 총 2번 수정한다.
그래프가 인접리스트로 표현된 경우에 bfs는 O(n+m)에 수행한다.
bfs는 이후 포스팅에서 다루게 될 최단경로를 구하는 알고리즘으로 확장된다.
참고 : 국형준. 알고리즘 원리와 응용. 21세기사, 2018.
