'최소 스패닝 트리'에 해당되는 글 2건

프림 알고리즘(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에서 정점 쌍을 꺼내 출력하면 됩니다.

최소 스패닝 트리(Minimum Spanning Tree)

최소 스패닝 트리를 이야기하기 전에 우선 스패닝 트리란 무엇인지 알아보도록 할게요.

우선 어떤 무향 그래프가 있다고 해보도록 가정하겠습니다. 스패닝 트리는 말 그대로 그래프에서 트리의 상태를 유지해야합니다. 그러니 사이클이 있으면 안되지요. 반드시 부모와 자식 관계로 이루어져 있지 않아도 됩니다.

다음의 그림은 올바른 스패닝 트리와 그렇지 않은 스패닝 트리를 보여줍니다.

왼쪽의 그림의 선택된 간선(굵은 선)은 사이클을 이루지 않지요.

반면 오른쪽 그림은 빨간선 때문에 사이클을 이루게 됩니다.

어때요? 간단하지요?

스패닝 트리는 그래프에서 여러개가 존재할 수도 있지만 우리가 눈여겨 볼 것은 스패닝 트리의 간선들이 가장 최소의 값을 갖는 것으로 바로 최소 스패닝 트리(Minimum Spanning Tree)라고 합니다.

대표적인 알고리즘에는 대표적으로 크루스칼(Kruskal)과 프림(Prim) 알고리즘이 있는데요. 이 두가지 알고리즘을 함께 보도록 하지요.

크루스칼 알고리즘 개념(Kruskal's Algorithm Concept)

우리는 아래의 그래프의 최소 스패닝 트리를 구할 겁니다. 이제 이 그래프를 가지고 크루스칼 알고리즘이 어떻게 동작하는지를 확인해 보도록 할게요.

원리는 이렇습니다.

우리는 위의 조건들을 가지고 최소 스패닝 트리를 찾는 겁니다.

우선 가장작은 간선의 값인 1, 즉 3-5의 간선을 봅니다. 현재 선택된 간선은 없으므로 3-5의 간선을 추가합니다. 그 다음 작은 간선을 보면 2인데, 이 간선은 현재 추가된 간선이 없으므로 2-4의 간선도 추가합니다.

이제 추가된 간선은 3-5, 2-4의 간선(파란색)입니다. 그 후 가장 작은 간선을 보면 1-2인데 이 간선은 추가된적이 없으므로 추가합니다. 그 후 역시 3인 간선이 있는데요. 이 간선을 추가하게 되면 사이클을 이루게 됩니다. 그러니까 다음 간선으로 넘어가게 되지요.

그 다음 작은 간선은 2-3입니다. 값은 4인데, 이 간선은 현재 추가한적이 없지요?(파란색 간선이 추가한 간선입니다.) 그러니 이 간선을 포함시키도록 합니다.

그 후 4-5 간선을 보게 되면 현재 선택되지는 않았지만 추가하게 되면 사이클을 이루게 됩니다. 그러니 넘어가죠.

이후 간선 0-1의 간선을 추가합니다. 다음으로 큰 수가 5이니까요.

이제 모든 정점이 트리에 포함되었으니 종료합니다.

따라서 최종 최소 스패닝 트리는 아래의 그림과 같습니다.

어떻습니까??

가장 최소의 값으로 스패닝 트리를 완성했다는 것을 알 수 있습니다.

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

이번에는 최소 스패닝 트리의 다른 알고리즘, 프림 알고리즘을 보도록 하지요. 프림 알고리즘은 트리에 연결된 간선 중 가장 작은 것을 차례차례 선택해나갑니다. 크루스칼 알고리즘과 같은 점은 역시 사이클을 이루는 간선을 선택하지 않는다는 것이죠.

어느 정점에서 시작하든 상관없습니다. 우리는 3번의 정점부터 계속 트리에 정점을 추가할 것입니다. 3과 가장 가까운 정점은 5가 되겠네요. 3과 5를 트리에 추가합니다. 3, 5 정점 중 가장 작은 간선은 2-3과 4-5네요. 구현에 따라 다를수 있으므로 둘 중에 아무거나 선택하면 됩니다. 2-3의 간선을 선택하지요. 따라서 트리에는 2가 추가가 됩니다.

이제 2, 3, 5에 붙어 있는 간선 중 가장 작은 간선 2-4를 선택합시다. 

그렇다면 현재 트리에는 2, 3, 4, 5가 됩니다. 이제 이 정점에서 가장 작은 간선을 선택해보도록 하지요. 후보는 1-2 간선과 1-4 간선이 됩니다. 아무거나 선택합시다. 

1-2의 간선을 선택하지요.

그 후 트리에 속해있는 정점과 붙어있는 가장 작은 간선은 1-4의 간선이 되는 군요. 하지만 선택할 수 없습니다. 사이클을 이루니까요. 그러니 버립시다.

다음 가장 작은 간선은 4-5의 간선입니다. 이것 역시 사이클을 이루게 되죠? 그러니 그냥 버리도록 합시다.

다음으로 가장 작은 간선은 0-1의 간선입니다. 이 간선을 포함해도 사이클을 이루지 않으니 선택하도록 하지요.

그렇다면 이제 모든 정점이 트리에 포함되어 있습니다. 여기서 종료합니다.

프림 알고리즘과 크루스칼 알고리즘이 동작하는 방식은 다르나 최소 스패닝 트리를 구할 수 있다는 것을 알 수 있습니다. 두 알고리즘 다 15의 값을 갖는 최소 스패닝 트리를 만들어 낼 수 있었습니다. 최소 스패닝 트리는 여러개 존재할 수는 있지만 그 값은 같다는 것을 잊지마세요.