너비 우선 탐색과 최단 거리

 

 

너비 우선 탐색과 최단 거리

 

 

 

 

깊이 우선 탐색과 달리 너비 우선 탐색은 대개 그래프에서의 최단 경로 문제를 풀 때의 용도로 사용된다.

 

그래서 깊이 우선 탐색에서는 모든 정점을 검사하면서 탐색을 수행하는 작업을 하지만,

너비 우선 탐색에서는 시작점으로부터 다른 정점들까지의 거리만 구하면 된다.

 

 

●최단 경로 문제

두 정점을 연결하는 경로 중 가장 길이가 짧은 경로를 찾는 문제

경로의 길이 = 경로에 포함된 간선의 개수

 

 

너비 우선 탐색 스패닝 트리를 보면, 각 정점으로부터 트리의 루트인 시작점으로 가는 경로가 그래프에서의 최단 경로임을 볼 수 있다. 그래서 함수 두개가 필요하다.

1. 각 정점까지의 최단 거리와 너비 우선 탐색 스패닝 트리를 계산하는 함수

2. 너비 우선 탐색 스패닝 트리를 입력받아 실제 최단 경로를 계산하는 함수

 

시작점으로부터의 최단 경로 = 너비 우선 탐색 스패닝 트리에서 루트로 가는 경로

각 정점이 부모의 번호를 갖고 있게 하면 쉽게 최단 경로 계산이 가능

 

 

 

구현    (알고리즘 문제해결전략 p885~886)

vector<vector<int>> adj;
 
// start에서 시작해 그래프를 너비우선탐색하고 시작점부터 각 정점까지의
// 최단 거리와 너비 우선 탐색 스패닝 트리를 계산
// distance[i] = start부터 i까지의 최단 거리
// parent[i] = 너비우선탐색 스패닝 트리에서 i의 부모의 번호. 루트인 경우 자신의 번호
void bfs(int start, vector<int>& distance, vector<int>& parent) {
    distance = vector<int>(adj.size(), -1);
    parent = vector<int>(adj.size(), -1);
    // 방문할 정점 목록을 유지하는 큐
    queue<int> q;
    distance[start] = 0;
    parent[start] = start;
    q.push(start);
    while (!q.empty()) {
        int here = q.front();
        q.pop();
        // here의 모든 인접 정점 검사
        size_t size = adj[here].size();
        for (size_t i = 0; i < size; ++i) {
            int there = adj[here][i];
            // 처음 보는 정점이면 방문 목록에 집어넣는다
            if (distance[there] == -1) {
                q.push(there);
                distance[there] = distance[here] + 1;
                parent[there] = here;
            }
        }
    }
}
 
// v로부터 시작점까지의 최단 경로를 계산
vector<int> shortestPath(int v, const vector<int>& parent) {
    vector<int> path(1, v);
    while (parent[v] != v) { // root가 아닐때
        v = parent[v];
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

 

 

이전에 보았던 너비우선탐색과의 차이점은

1. distance로 거리를 저장함

2. parent로 부모를 저장함

3. shortestPath로 부모를 쭉 찾아가 최단경로 계산

 

 

위 코드를 보면 here과 there라는 것을 아주 잘 사용하는 것 같다.

현재는 here. 내가 볼 정점은 there.

here과 there를 사용해 distance[there] = distance[here] + 1; 하는 것을 보고 감탄했다.

부모를 저장할 때도 마찬가지이다.