'prim alogirhm'에 해당되는 글 1건

프림 알고리즘(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;
	}
}

#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에서 정점 쌍을 꺼내 출력하면 됩니다.