너비 우선 탐색을 통한 최단거리 구해보기

너비 우선 탐색(BFS) 은 그래프에서의 최단 경로 문제를 푸는 용도로 사용 된다. 최단 경로 문제는 두 정점을 연결하는 경로 중 가장 길이가 짧은 경로를 찾

는문제 이다.

코드 ( C ++ )

#include <iostream>

#include <algorithm>

#include <vector>

#include <queue>

using namespace std;

vector<vector<int>> adj;

// start에서 시작해 그래프를 너비 우선 탐색하고 시작점부터 각 정점까지

// 최단 거리와 너비 우선 탐색 스패닝 트리 계산

// distance[i] = start부터 i까지의 최단 거리

// parnet[i] = 너비 우선 탐색 스패닝 트리에서 i 의 부모의 번호, 루트일 경우 자신의 번호

void bfs2(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();

for (int i = 0; i < adj[here].size(); ++i)

{

int there = adj[here][i];

if (distance[there] == -1) {

distance[there] = distance[here] + 1;

parent[there] = here;

q.push(there);

}

}

}

}

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;

}

int main()

{

//정점의 수

int V = 9;

adj = vector<vector<int>>(V, vector<int>());

adj[0].push_back(1);

adj[0].push_back(3);

adj[0].push_back(4);

adj[0].push_back(8);

adj[1].push_back(0);

adj[1].push_back(2);

adj[1].push_back(3);

adj[2].push_back(1);

adj[2].push_back(5);

adj[2].push_back(6);

adj[3].push_back(0);

adj[3].push_back(1);

adj[3].push_back(6);

adj[4].push_back(5);

adj[4].push_back(0);

adj[5].push_back(4);

adj[5].push_back(2);

adj[6].push_back(2);

adj[6].push_back(3);

adj[6].push_back(7);

adj[7].push_back(6);

adj[8].push_back(0);

vector<int> distance;

vector<int> parent;

bfs2(0, distance, parent);

vector<int> shortestWay;

// 7로 부터 시작점까지의 최단 경로 계산

shortestWay = shortestPath(7, parent);

// 방문 순서

for (int i = 0; i < shortestWay.size(); ++i)

cout << shortestWay[i] << " ";

return 0;

}

참고 문헌: 알고리즘 해결 전략