[AJ/BFS] 너비 우선 탐색(BFS : Breadth First Search)

너비 우선 탐색이란?

 루트 노드 혹은 다른 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법이다.

 

너비 우선 탐색과정 

1. 루트에서 시작한다.

2. 자식 노드들을 큐에 저장한다.

3. 큐에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 큐에 저장한다.

4. 큐에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 큐에 저장한다.

5. 위의 과정을 반복한다.

6. 모든 노드를 방문하면 탐색을 마친다. 

7. 다음과 같이 진행하면 탐색 순서는 0 -> 1 -> 2 -> 3 -> 4 -> 5 가 된다.

 

 

너비 우선 탐색 특징 

 -  DFS로 탐색할 시에는 무한한 길이의 경로에서 영원히 종료하지 못하지만, BFS의 경우는 모든 경로를 동시에 진행하기 때문에 탐색이 가능하다.

 - 한 갈림길에서 연결되는 모든 길을 한번씩 탐색하기 때문에 가중치가 없는 그래프에서는' 시작점에서 끝점까지의 최단경로를 알아낼 수 있다.

 

 

너비 우선 탐색 구현

 - queue를 사용하여 구현한다. 

 - while(큐가 비어있지 않을 동안){

     1. 큐 안에서 가장 앞에 있는 노드 pop

     2. pop한 노드(현재 노드)에 인접한 모든 노드 중 방문하지 않은 노드들을 push

     3. push하고 방문했다고 표시

 

}
* 나무위키 참고