[알고리즘/C++] 그래프 순회 - 너비 우선 탐색(BFS)

깊이 우선 탐색 이외에도 너비 우선 탐색(BFS)라는 기법이 있다. 

 

BFS는 노드를 순회할 때 리프 노드까지 먼저 가는 것이 아니라 같은 레벨(level)에 있는 노드를 먼저 순회하고

 

그 다음 레벨에 있는 노드를 순회하는 순서로 그래프를 순회한다. 

 

좌측이 너비 우선 탐색(BFS)

void bfs(vector<vector<pair<int, int>>> adj, vector<bool>& visited, int start) {
	visited[start] = true;
	queue<int> q;
	q.push(start);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		cout << now << "!!\n";
		for (int i = 0; i < adj[now].size(); i++) {
			if (visited[adj[now][i].first]) {
				continue;
			}
			visited[adj[now][i].first] = true;
			q.push(adj[now][i].first);
		}
	}
}

재귀 함수로 간단히 구현이 가능한 깊이 우선 탐색과는 달리, 너비 우선 탐색은 재귀 없이 구현해야하기 때문에 

 

그 방법이 더 복잡한데, 그 메커니즘에 대해서 알아보자. 

	visited[start] = true;
	queue<int> q;
	q.push(start);

BFS도 DFS와 마찬가지로 visited 함수가 필요한데, 한번 방문한 노드를 다시 방문하지 않기 위함이다. 

 

BFS는 레벨 순으로 내려가면서 노드를 순회하는데 visited가 필요한가? 라고 물을 수 있지만 

 

'사이클이 있는 그래프'인 경우, visited를 사용하지 않는다면 BFS에서 무한 루프에 빠질 수 있다. 

 

그리고 큐(queue) 자료구조를 사용하는데, 먼저 접한 레벨의 노드들을 먼저 다 순회해야하기 때문에

 

선입선출(FIFO) 구조인 큐를 사용하는 것이 적절하다. 

 

	while (!q.empty()) {
		int now = q.front();
		q.pop();
		cout << now << "!!\n";
		for (int i = 0; i < adj[now].size(); i++) {
			if (visited[adj[now][i].first]) {
				continue;
			}
			visited[adj[now][i].first] = true;
			q.push(adj[now][i].first);
		}
	}

 그리고 큐의 값들을 하나씩 pop하면서 노드를 순회한다. 

 

현재 순회중인 노드의 자식 노드들을 살펴보면서 나중에 아래 레벨에 도달했을 때 순회하기 위해 큐에 push해준다. 

 

자식 노드들을 큐에 push하면서 visited 처리해준다. 

	vector<vector<pair<int, int>>> adj;
	initTree(adj);
	vector<bool> visited(adj.size(), false);
	bfs(adj, visited, 1);

1
2
3
4
5
6
7
8
9
10
11