(출처: 종만북)
너비 우선 탐색(Breadth-First Search, 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;
}
반응형
'알고리즘 > 그래프' 카테고리의 다른 글
다익스트라(Dijkstra)의 최단 경로 알고리즘 (0) | 2020.06.19 |
---|---|
양방향 탐색(Bidirectional Search) (0) | 2020.05.19 |
무향 그래프에서 DFS를 이용해 오일러 회로 찾기 (0) | 2020.05.13 |
위상 정렬 (Topological Sort) (0) | 2020.05.13 |
해밀턴 경로(Hamiltonian Path), 해밀턴 회로(Hamiltonian Circuit) (0) | 2020.04.06 |