BFS (Breadth First Search) 알고리즘

BFS란 ?

Breadth First Search라는 의미로, 너비 우선 탐색이라고도 한다.

즉, 시작점을 기준으로 DFS와 마찬가지로 가장 아래까지 이동하면서 탐색하는 방식이다.

하지만 BFS는 깊이 탐색이 아닌 같은 칸만큼 움직인 것(말이 조금 이상하니 그림을 통해 확인하도록 한다.) 들에 대한 탐색으로써

DFS와는 조금 다르다.

 

이 탐색 알고리즘은 큐를 이용하여 푸는 방식으로, 

큐에 값을 넣어주고. 그 값을 통해 확인하며 종료 조건은 스택이 비어있을 때이다.

BFS 또한 DFS와 마찬가지로 그림을 참조해서 확인하면 좀더 쉽게 알 수 있다. 

BFS 탐색 알고리즘 코드는 http://www.crocus.co.kr/519 이 링크에서 확인해 볼 수 있다.

 DFS와 똑같은 그래프로 확인해 보자.

  1을 먼저 방문하면 큐에 1이 쌓인다.

 그다음 1이 큐에 쌓여있으니 1을 빼며 2로 탐색을 한다.

 1에 있는 나머지를 for문을 통해 다 방문한다 즉, 2,3,4를 방문하는 과정이다.

 이렇게 1에대해 인접해 있는 모든 노드를 방문한 후에 다시 큐를 확인한다.

 이번엔 2를 큐에서 확인해 보지만 2는 인접한 노드가 1밖에 없다.

 1은 이미 방문한 상태이기에 2는 그대로 큐에서 빠져나온다.

그리고 3을 보면 3은 5부터 방문할 수 있게 된다.

 

 5및 6을 for문으로 마찬가지로 방문한다. (3에 대한 인접한 노드들을 방문하며 큐에 넣는다.)

 큐에 4,5,6이 쌓여있었는데 4,5는 확인할 노드가 없으니 큐에서 그대로 빠지고,

 6은 7을 방문할 수 있으니 6을 큐에서 빼주며 7을 동시에 큐에 넣어준다.

 7을 빼주면서 8,9를 큐에 넣고, 마지막 10까지 이전에 했던대로 처리한다.

이렇게 10까지 빠지게 되면 큐가 텅 비게 되어 이 탐색 알고리즘은 끝이나게된다.

방문 순서는 결과적으로

1->2->3->4->5->6->7->8->9->10 순서이다.