[알고리즘 : 그래프 이론] 그림으로 보는 BFS 기본, 개념, 설명

BFS(Breadth First Search, 너비우선탐색)

그래프 이론 DFS와 BFS 중 BFS는 그래프를 가까운 정점부터 순서대로 탐색하는 그래프 탐색 알고리즘이랍니다. 그래프에서 탐색 시 아주 많이 사용되는 탐색기법이지요. 우선 다음과 같은 무향그래프가 있다고 가정해보겠습니다. 

우선 그래프 탐색을 하기 전에 조건이 있습니다.

1. 처음 정점 0부터 시작한다고 칩시다.

2. 정점을 방문한 적이 있다면 다시 방문하지 않는다.

3. 방문해야 할 정점이 여러 개일 경우 가장 번호가 낮은 정점부터 방문한다.

BFS로 위 그래프를 탐색하는 과정을 보겠습니다 

1. 0을 방문한다.

2. 0과 가장 가까운 정점을 찾는다 ( 1, 5, 6).

3. 1이 방문되지 않았으므로 1을 방문한다.

4. 5가 방문되지 않았으므로 5를 방문한다.

5. 6이 방문되지 않았으므로 6을 방문한다.

6. 1에서 가장 가까운 정점을 찾는다 (0, 2, 3).

7. 0은 이미 방문했으므로 skip한다.

8. 2는 방문되지 않았으므로 2를 방문한다.

9. 3이 방문되지 않았으므로 3을 방문한다.

10. 5에서 가장 가까운 정점을 찾는다 (0, 6).

11. 0과 6은 방문됐으므로 skip한다.

12. 6과 가장 가까운 정점을 찾는다 (0, 5).

13. 0과 5는 이미 방문됐으므로 skip한다.

14. 2와 가장 가까운 정점을 찾는다 (1, 4). 

15. 1은 이미 방문됐으므로 skip한다.

16. 4는 방문되지 않았으므로 4를 방문한다.

17. 모든 정점을 지나쳤으므로 종료한다.

이제 방문된 점을 차례대로 나열해본다면  0 - 1 - 5 - 6 - 2 - 3 - 4 로 방문이 되는 것을 확인 할 수 있습니다. 코드로 표현하면 어떻게 될까요? 아래 C++ 소스코드로 BFS를 구현해보았습니다.

#include <cstdio>
#include <vector>
#include <queue>
#define V 7
using namespace std;

int g[V][V] = {
	{0,1,0,0,0,1,1},
	{1,0,1,1,0,0,0},
	{0,1,0,0,1,0,0},
	{0,1,0,0,0,0,0},
	{0,0,1,0,0,0,0},
	{1,0,0,0,0,0,1},
	{1,0,0,0,0,1,0}
};

vector
 bfs(int start) {
	vector discovered(V, false);
	queue next;

	vector order;

	visited[start] = true;

	next.push(start);
	while (!next.empty()) {
		int from = next.front();
		next.pop();

		order.push_back(from);

		for (int to = 0; to < V; to++) {
			if (g[from][to] == 1 && !visited[to]) {
				next.push(to);
				visited[to] = true;
			}
		}
	}
	return order;
}
int main() {

	vector bfsOrder = bfs(0);
	for (int i = 0; i < V; i++)
		printf("%d ", bfsOrder[i]);
}

이 코드가 어떻게 동작이 되는 지 하나하나 살펴봅시다. 그 전에 준비물이 있습니다. 바로 자료구조 큐를 준비해야 된다는 겁니다. 큐를 통해서 어떻게 BFS가 구현될까요? 다음과 같이 하늘색 상자는 큐를 나타낸다고 하겠습니다. 0부터 노드가 방문되기 때문에 큐 안에는 0이 저장되어 있습니다.

이 후 0은 방문될때 큐에서 꺼내어 집니다. 그 다음에 0에서 가장 가까운 정점 중에 방문되지 않은 정점을 큐에 저장합니다. 이렇게 말입니다.

0을 방문합니다. 0은 큐에서 꺼내어 지고 0과 가장 가까운 정점 1 5 6이 큐에 저장됐습니다. 그 후에는 다시 1을 큐에서 꺼내오고 1과 가장 가까운 정점을 큐에 집어 넣습니다.

단, 방문되지 않은 녀석들로요.

1은 방문이 되어 큐에서 나오고 2와 3이 추가 돼었군요. 역시 과정은 계속 반복됩니다. 다음 5가 방문될 차례입니다. 5를 꺼내고 5와 가장 가까운 정점을 추가합니다.

5와 가장 가까운 정점 0과 6이 있는데, 6은 아직 큐에 존재하니까 방문하지 않은 걸로 간주합니다. 그래서 6을 다시 큐에 집어 넣습니다. 다음 6을 방문합니다. 

6과 가장 가까운 정점 0과 5는 이미 방문된 상태랍니다. 그래서 큐에 집어 넣지 않습니다. 다음 2를 방문합니다. 

2과 가장 가까운 정점은 1, 4로 1은 이미 방문된 상태로 넘어가고 4는 큐에 들어갑니다. 왜냐면 방문될 정점으로 큐에 아직 존재하니까요. 다음 3을 방문합니다.

3과 가장 가까운 정점 1은 이미 방문된 상태라 넘어갑니다. 다음 4를 방문합니다.

4와 가장 가까운 정점 2는 이미 큐에서 나와 방문이 되었습니다. 어느 정점하나 큐에 들어가지 않습니다. 이제 큐에 남아있는 방문될 정점 6과 4는 이미 방문이 되었으므로 큐에서 그냥 빠져나옵니다. 방문되지 않는 다는 뜻입니다. 버립니다.

이로써 큐는 모두 비워졌습니다. 큐가 비워졌으니 더 이상 방문할 정점이 없으니 BFS과정은 끝나게 됩니다. 이로써 BFS가 어떻게 동작하는 지 살펴보았습니다. BFS는 그럼 도대체 언제 사용하게 될까요? 그건 다음에 알아보도록 하겠습니다.