[알고리즘] 프림 알고리즘(Prim's Algorithm) 구현과 코드 분석

프림 알고리즘(Prim's Alogorithm)

최소 스패닝 트리의 크루스칼 알고리즘과 프림 알고리즘의 동작 방법을 알아보았으니 이제 코드로 구현해 볼 차례입니다.

그때 썼던 그래프를 다시 가져다가 써보도록 하죠.

우리는 이 그래프의 최소 스패닝트리를 프림알고리즘으로 구하는 원리는 알고 있으니 위의 그래프를 코드로 구해보도록 합시다. 여기서는 C++을 사용하여 보다 쉽게 구현할 겁니다.

int prim(vector<pair<int, int> > &selected) {
	selected.clear();

	vector<bool> added(V, false);
	vector<int> minWeight(V, INF), parent(V, -1);

	int ret = 0;
	minWeight[0] = parent[0] = 0;
}

우선 필요한 변수들을 선언했습니다. 

selected 변수에는 우리가 선택한 간선의 정점 정보가 저장될 겁니다. 일단 selected.clear()로 벡터를 비워주도록 합시다.

added변수는 현재 트리에 어떤 정점이 있는지 체크하기 위한 변수입니다. 

만약 정점 3이 트리에 포함되어 있다면 added[3]=true이지요. 처음에는 어떤 정점도 트리에 포함되지 않으므로 added 벡터는 전부 false로 초기화가 됩니다.

minWeight에는 트리에 붙어있는 정점 중 가장 가까운 정점이 들어있습니다. 초기에는 선택된 정점이 아직 없으므로 가장 큰 값을 설정합니다.

parent에는 정점의 부모를 나타냅니다. 만일 어떤 정점 u가 있다면 그 부모 정점은 parent[u]가 되는 것이죠.

ret는 최소 스패닝 트리의 모든 간선의 값을 나타냅니다.

이제 우리는 정점 0을 기준으로 트리를 만들어 나갈건데 0의 부모는 자기 자신이고, 자기 자신까지의 거리는 0입니다.

for (int iter = 0; iter < V; iter++) {
		
}

위의 for 루프는 모든 정점까지 반복하는 루프입니다. 이 안이 우리가 구현해야 할 부분이지요.

이제 이 for루프를 구현해보도록 하죠.

int u = -1;
for (int v = 0; v < V; v++) {
	if (!added[v] && (u == -1 || minWeight[u]>minWeight[v]))
		u = v;
}

if (parent[u] != u)
	selected.push_back(make_pair(parent[u], u));

u라는 변수는 초기에 -1을 지정합니다. 이미 트리에 저장되지도 않았고, 트리의 가장 가까운 정점을 찾는 것이죠.

만약 u의 부모가 u가 아니라면 u의 부모와 u로 구성된 정점 쌍을 selected에 저장합니다. 

u==-1일 경우에는  언제일까요? u가 첫 시작점(첫 스타트를 끊었을때)일 때 -1이라는 것이죠. 가장 처음으로 시작하기 때문에 아직 추가된 정점이 없고, 가장 처음에 시작했기 때문에 u==-1이지요. 

ret += minWeight[u];
added[u] = true;

추가를 했으니 ret에 값을 추가하고 트리에 추가되었다는 표시를 해야되겠죠??

for (int i = 0; i < adj[u].size(); i++) {
	int v = adj[u][i].first, weight = adj[u][i].second;
	if (!added[v] && minWeight[v]>weight) {
		parent[v] = u;
		minWeight[v] = weight;
	}
}

이제 다음 후보 정점들을 찾아야하는데요. v에는 u와 인접한 정점이 저장되고 weight에는 그 정점과 u까지의 간선 값을 나타냅니다.

이미 추가된 정점이면 추가하면 안되겠죠? 사이클이 발생하니까요.

그림을 보면서 이 코드를 더 자세히 보도록 합시다.

만일 u와 인접한 정점 v3가 있다고 칩시다. 이 정점은 트리에 추가되지도 않았을 뿐더러 minWeight[v3]=3 입니다. 하지만 u와는 2의 거리에 놓여있으므로 minWeight[v3]=2로 수정해주는 것이죠. 그리고 v3의 부모는 u가 되는 것입니다.

이제 끝났습니다. ret를 반환하면 최소 스패닝 트리의 값이 나오게 되지요.

전체 소스코드

아래는 프림알고리즘을 CPP로 구현한 전체 소스코드랍니다.

#include <iostream>
#include <vector>

using namespace std;

const int MAX_V = 100;
const int INF = 987654321;

int V=6;

vector<pair<int, int> > adj[MAX_V];

int prim(vector<pair<int, int> > &selected) {
	selected.clear();

	vector<bool> added(V, false);
	vector<int> minWeight(V, INF), parent(V, -1);

	int ret = 0;
	minWeight[0] = parent[0] = 0;
	for (int iter = 0; iter < V; iter++) {
		int u = -1;
		for (int v = 0; v < V; v++) {
			if (!added[v] && (u == -1 || minWeight[u]>minWeight[v]))
				u = v;
		}

		if (parent[u] != u)
			selected.push_back(make_pair(parent[u], u));

		ret += minWeight[u];
		added[u] = true;

		for (int i = 0; i < adj[u].size(); i++) {
			int v = adj[u][i].first, weight = adj[u][i].second;
			if (!added[v] && minWeight[v]>weight) {
				parent[v] = u;
				minWeight[v] = weight;
			}
		}
	}
	return ret;
}

int main() {
	adj[0].push_back(make_pair(1, 5));
	adj[1].push_back(make_pair(0, 5));

	adj[1].push_back(make_pair(2, 3));
	adj[2].push_back(make_pair(1, 3));

	adj[2].push_back(make_pair(3, 4));
	adj[3].push_back(make_pair(2, 4));

	adj[1].push_back(make_pair(4, 3));
	adj[4].push_back(make_pair(1, 3));

	adj[0].push_back(make_pair(3, 7));
	adj[3].push_back(make_pair(0, 7));

	adj[2].push_back(make_pair(4, 2));
	adj[4].push_back(make_pair(2, 2));

	adj[3].push_back(make_pair(5, 1));
	adj[5].push_back(make_pair(3, 1));

	adj[4].push_back(make_pair(5, 4));
	adj[5].push_back(make_pair(4, 4));

	vector<pair<int, int> > selected;
	int mst=prim(selected);
	printf("mst:%d\n", mst);
	for (int i = 0; i < selected.size(); i++) {
		printf("%d-%d\n", selected[i].first, selected[i].second);
	}
	printf("\n");
}

main함수에서는 각 간선을 연결해주고 weight도 부여합니다. 

예를 들어

adj[4].push_back(make_pair(5,4))

adj[5].push_back(make_pair(4,4))

라는 것은 4와 5의 정점을 연결하는데 그 간선의 weigt는 4라는 것입니다. 또한 그래프가 무향 그래프이기 때문에 거꾸로도 연결해야하는 것이죠.

그래서 각각 짝을 맞추어서 간선을 연결해주어야합니다.

mst는 최소스패닝트리의 간선값의 합을 나타냅니다. 따라서 단지 최소스패닝트리의 값만 보고 싶다면 mst를 쓰면 되구요.

경로를 보고 싶다면 selected에서 정점 쌍을 꺼내 출력하면 됩니다.

이 코드는 구종만의 알고리즘 문제해결 전략2를 가져왔습니다.