BFS(Breadth-First Search) 너비 우선 탐색 개념

루트부터 시작하여 인접한 노드를 먼저 탐색하고 그 다음으로 깊이 방향으로 진행.

 

즉, 깊에 탐색하기 보다는 넓게 탐색 하는 방법

  * 깊게 탐색하는 방법 : DFS(Depth First Search)

  

인접한 노드를 모두 탐색하고 깊게 나아가기 때문에 queue를 활용하여 구현이 가능한다.

  - 루트부터 시작하여, 방문할 때 마다 해당 노드를 enqueue하고 인접한 노드를 모두 enqueue한다.

  - 더이상 방문할 인접 노드가 없으면, queue에서 head를 dequeue한다.

  - 해당 노드와 인접한 노드를 방문 및 enqueue한다.

  - 모두 방문할 때 까지 계속 반복.

  - 즉 enqueue, dequeue를 계속 반복한다.

 

아래 순서를 따가 구체적인 사례를 보자.

 

1. 탐색 순서

1) 루트부터 시작. 0부터 방문하자. Queue에 0을 enqueue.

 

2) 0을 dequeue하자.

 

3) 0과 인접한 노드를 하나 씩 방문 및 enqueue.

4) depth가 1인 인접 노드의 탐색이 끝났다. queue에서 하나를 dequeue하여 해당 노드에 인접한 노드를 탐색해보자.

5) 1에 인접한 노드를 하나 씩 방문하자. 0은 이미 방문했으니 제외하자.

 

6) 1에 인접한 노드를 모두 방문했다. 다음은 queue의 head를 dequeue하자.

7) 2에 인접한 노드를 방문하자. 0은 이미 방문했으니 제외.

8) depth가 2인 노드의 탐색이 끝났다. 다음은 queue에서 head를 dequeu하자. 

9) 3과 인접한 노드를 방문하자. 1은 방문했으니 제외.

10)head를 dequeue하고, 방문할 0인접 노드를 enqueue한다.

   4의 입장에서 1, 5, 2 모두 이미 방문했으니 제외.

11)head를 dequeue하고, 방문할 0인접 노드를 enqueue한다.

   5의 입장에서 4, 2는 이미 방문했으니 제외.

12) head를 dequeue하고, 방문할 0인접 노드를 enqueue한다.

   6의 입장에서 2는 이미 방문했으니 제외.

12) head를 dequeue하고, 방문할 0인접 노드를 enqueue한다.

   7의 입장에서 3는 이미 방문했으니 제외.