BFS와 BFS 스패닝 트리 구현

(출처: 종만북)

 

너비 우선 탐색(Breadth-First Search, BFS)으로 한 정점에서 다른 정점까지의 최단 경로를 계산할 수 있습니다.

 

Fig 1. BFS 스패닝 트리 예시

BFS를 수행하면서 새 정점을 발견했을 때 사용한 간선만 모은 트리를 BFS 스패닝 트리(BFS Spanning tree)라고 합니다.

예시로 Fig 1.의 그래프를 만들어봤는데요, 간선이 이전에 방문했던 정점을 발견할 때 사용되었다면 스패닝 트리에 넣지 않습니다. [c, e], [d, g]의 간선이 스패닝 트리에 들어가지 않는 간선의 예입니다.

 

시작 노드로부터 각 정점까지 최단경로를 구했는데, 이때 각 노드에서 부모의 인덱스를 저장하게 하면 스패닝 트리를 만들 수 있고, 이 스패닝 트리를 사용해 시작점부터 각 정점까지의 최단경로를 계산할 수 있습니다.

 

// start에서 시작해 그래프를 너비우선탐색하고
// 시작점부터 각 정점까지 최단거리와 bfs 스패닝 트리를 계산
// dist[i]: start부터 i까지의 최단거리
// parent[i]: bfs 스패닝 트리에서 i의 부모의 번호. 루트인 경우 자신의 번호
void bfs(int start, vector<int>& dist, vector<int>& parent) {
	dist = vector<int>(adj.size(), -1);
	parent = vector<int>(adj.size(), -1);

	queue<int> q;
	dist[start] = 0;
	parent[start] = start;
	q.push(start);

	while (!q.empty()) {
		int current = q.front();
		q.pop();

		// 현재 노드의 모든 인접 정점을 검사
		for (auto& next : adj[current]) {
			// 방문하지 않은 노드인 경우 큐에 넣음
			if (dist[next] == -1) {
				q.push(next);
				dist[next] = dist[current] + 1;
				parent[next] = current;
			}
		}
	}
}

// v로부터 시작점까지의 최단경로 계산
vector<int> shortestPath(int v, const vector<int>& parent) {
	vector<int> path(1, v);
	
	while (parent[v] != v) {
		v = parent[v];
		path.push_back(v);
	}
	reverse(path.begin(), path.end());

	return path;
}