Graph(BFS 너비우선탐색)

지난 시간 DFS(깊이우선탐색)에 이어 BFS(너비우선탐색)에 대해서 알아보자.

 

BFS(너비우선탐색)

• 시작 정점에서 가까운 정점이 먼 정점보다 먼저 방문되도록 하는 방식
• 시작 정점 v를 방문
• v에 인접한 모든 정점들을 방문
• 새롭게 방문한 정점들에 인접하면서 과거에 방문하지 않은 정점들을 모두 방문
• Queue를 이용
• 다음 탐색을 위해서는 Queue에서 dequeue를 하고 dequeue를 한 노드에서 시작한다.

이제 G7 그래프를 가지고 BFS 알고리즘에 대해서 알아보자.

위와 같은 G7 그래프가 있다. 이전 DFS 알고리즘과 같은 그래프를 가지고 BFS 알고리즘은 어떤 경로를 따라 최단경로를 찾는지 비교하면서 살펴보자.

 

 

Queue

 

 

 

 

 

 

1) 시작정점 A에서 BFS 알고리즘을 시작한다.

2) 정점 A에서 방문하지 않은 모든 인접 정점 B와 C를 한꺼번에 방문한다.(Queue에 B,C를 enqueue)

Queue

B

C

 

3) 다음 탐색을 위해 Queue에서 B를 dequeue하고 B의 위치에서 방문하지 않은 인접 정점 D와 E를 모두 방문한다.

(Queue에서 B를 dequeue, Queue에 D와 E를 enqueue)

Queue

C

D

E

 

4) 다음 탐색을 위해 Queue에서 C를 dequeue하고 C의 위치로 이동(Queue에서 C를 dequeue)

Queue

D

E

 

5) C의 인접정점 중 과거에 방문하지 않은 정점이 없으므로 다시 Queue에서 D를 dequeue하고 D의 위치로 이동(Queue에서 D를 dequeue)

Queue

E

 

6) D에서 D의 인접정점 G로 이동(Queue에서 G를 enqueue)

Queue

E

G

 

7) 다음 탐색을 위해 Queue에서 E를 dequeue하고 E의 위치로 이동

G

 

8) 다음 탐색을 위해 Queue에서 G를 dequeue하고 G의 위치로 이동한 후 G의 인접 정점 F로 이동

(Queue에서 G를 dequeue, Queue에서 F를 enqueue)

F

 

9) 마지막 정점 F에 도달하였으므로 Queue에서 F를 dequeue -> Queue가 공백이므로 너비 우선 탐색(BFS)를 종료

 

결론 : Queue의 dequeue순서 B,C,D,E,G,F이고 방문 정점 순서 역시 A-B-C-D-E-G-F로 dequeue순서와 방문 정점 순서가 동일한 것을 확인할 수 있다.

 

BFS 알고리즘 sudo 코드는 이와 같이 나타낼 수 있다.

 

bfs(G, v)

        Q ← createQueue()

        G.visited[v] ← TRUE

        enqueue(Q, v)

        visit(v)

        while (not isEmpty(Q)) do

            v ← dequeue(Q)

            for all w ∈ (v의 인접 정점) do

            if w가 방문되지 않았으면 then

                  enqueue(Q, w.vertex)

                  G.visited[w.vertex] ← TRUE

                  visit(w.vertex)

end bfs()