넓이 우선 탐색_BFS

이전에 포스팅 했던 깊이우선 탐색(DFS)와 또 다르게 널리 이용되는 탐색 이론이다.

 

DFS가 이름 처럼 하나의 노드에서 도달 가능한 깊은 노드까지 먼저 탐색한다면, 넓이우선 탐색 BFS는 하나의 노드로부터 주변의 모든 노드로 뻗어나가며 탐색하는 방법이다.

 

넓이 우선 탐색은 큐 자료구조를 이용한다.

큐의 선입선출 특성을 이용하는데, 큐의 가장 첫 번째 노드와 연결된 노드를 큐에 집어넣고, 첫 번째 노드를 큐에서 빼낸 후 방문처리를 하는 것을 반복한다.

 

아래와 같은 그래프가 있고 1번 노드로부터 BFS를 이용해 탐색을 시작한다고 하자.

+) 탐색을 시작하는 노드는 어디로 해도 상관없지만 숫자가 작은 노드부터 오름차순으로 하는 것이 편하고 또 그것을 관례적으로 따르기도 한다.

 

시작 노드인 1번 노드를 큐에 집어넣고 방문여부를 표시한다.(필자의 실수로 방문 여부 표를 그리지 않았다 ㅠㅠ)

 

큐의 제일 앞에 있는 1번 노드를 꺼낸다.

1번 노드와 연결된 2, 3, 8번 노드를 큐에 집어넣고 방문처리한다. 이 또한 관례적으로 오름차순으로 진행한다.

 

큐의 제일 앞에 있는 2번 노드로 옮겨 탐색을 진행한다.

2번 노드를 꺼내고 2번 노드의 인접 노드 중 방문여부가 체크되어 있지 않은 7번 노드를 큐에 삽입 후 방문여부를 체크한다.

이후의 과정은 모두 동일하게 큐의 맨 앞 데이터를 보고 탐색할 노드를 결정 한 후 탐색을 진행하면 된다.

 

3번 노드가 큐의 가장 앞에 있으므로 3번 노드를 큐에서 빼낸 후 3번 노드와 인접하지만 방문여부가 체크되지 않은 노드를 큐에 삽입한다.

위 그래프에서는 4번, 5번 노드가 큐에 새로 삽입되었다.

 

다음엔 8번 노드가 큐의 가장 앞에 있으므로 8번 노드를 꺼낸다.

8번 노드의 인접 노드는 모두 방문한 것으로 처리되어 있으므로 따로 인접 노드를 큐에 삽입하지 않고 다음 탐색을 진행한다.

 

큐의 첫 번째 노드는 7이므로 7노드의 인접 노드 중 아직 방문하지 않은 6노드를 방문체크하고 큐에 삽입한다. 이로써 모든 노드의 탐색이 끝났다.

 

남은 6, 5, 4노드의 인접 노드는 모두 방문처리가 이미 되어있으므로, 차례대로 큐에서 나가게 된다.