DFS(깊이 우선 탐색)과 함께 그래프 탐색 알고리즘의 기본이자 대표격이라 할 수 있는 BFS(너비 우선 탐색)에 대해 알아보자

너비 우선 탐색(BFS)

Breadth First Search, 너비 우선 탐색이란 말 그대로 너비를 우선시하여 그래프를 탐색하는 방법이다. 한 노드와 연결되어 있는 모든 노드를 살펴본 후에, 그 다음 깊이로 이동하여 과정을 반복한다.

BFS는 다음의 규칙으로 진행된다.
1. 노드와 연결된 이웃 노드들을 모두 큐에 넣는다.
2. 큐에서 꺼낸 노드와 연결된 이웃 노드들을 모두 큐에 넣는다.
3. 큐가 소진될 때까지 반복한다.

그림으로 나타내면 다음과 같다.

• 시작 노드는 1번으로 한다. 1번 노드와 인접해 있는 2, 3번 노드를 큐에 삽입한다.
• 큐에서 노드 하나를 꺼낸다. 그 노드를 방문한다. 위의 그림의 경우 2가 해당될 것이다. 또다시 2번 노드와 인접해 있는 4, 5번 노드를 큐에 삽입한다.
• 위 과정을 반복하면 3을 꺼내고, 6, 7을 넣고, 다시 4를 꺼내고 8을 넣고... 이런 식으로 반복하여 진행한다.

이리 하여 너비 우선 탐색을 완료했다.

BFS의 구현

앞에서도 언급하였지만 큐 자료구조를 사용한다. DFS의 경우 가장 마지막에 넣은 값을 바로 다시 사용할 수 있어야 하므로 스택 자료구조로 구현하였지만, BFS의 경우 먼저 들어간 노드 (먼저 이웃한 노드)가 뒷 노드보다 먼저 탐색되어야 하므로 선입선출(FIFO) 구조를 가지고 있는 큐를 사용한다.

위 그림에서 큐에 숫자가 담기고 빠지는 과정을 나타내보면 다음과 같다. (인접한 노드가 여러 개일 경우 숫자가 작은 노드부터 먼저 넣기로 하자)

• 1과 인접한 2, 3을 큐에 넣는다. (큐 : [2, 3])
• 2를 빼고, 방문한다. (큐 : [3])
• 2와 인접한 4, 5를 큐에 넣는다. (큐 : [3, 4, 5])
• 3을 빼고, 방문한다. (큐 : [4, 5])
• 3과 인접한 6, 7을 큐에 넣는다. (큐 : [4, 5, 6, 7])
• 4를 빼고, 방문한다. (큐 : [5, 6, 7])
• 4와 인접한 8을 큐에 넣는다. (큐 : [5, 6, 7, 8])
• 5를 빼고, 방문한다. (큐 : [6, 7, 8])
• 5와 인접한 노드 중 큐에 넣은 적이 없는 노드가 없으므로, pass
• 6, 7, 8을 차례로 뺀다. 세 노드 모두 인접한 노드에서 새로 넣을 노드가 없다.

즉 탐색 순서는 1→2→3→4→5→6→7→8 이다.