Prim algorithm (프림 알고리즘)

Prim algorithm (프림 알고리즘)

프림 알고리즘은 greedy algorithm의 일종이며, 최소신장트리 문제를 해결하기 위한 알고리즘이다.  Greedy algorithm과 최소신장트리에 관한 개념은 앞 글에서 다루었다.

 

앞에서 그래프를 G=(V,E)로, 신장 트리를 T=(V,F)로 표기하기로 했다. 우리는 최소신장트리가 되는 F를 찾는 것이 목표다. 그래프 G는 다음과 같다.

그래프 G

프림 알고리즘은 한 점에서 시작하여 계속 최적의 선택을 해나간다. 그 시작점을 v1이라고 해보자. v1을 담고있는 새로운 집합 Y(최소신장트리의 vertex를 담는다.)를 만들고, 집합 F(최소신장트리의 edge를 담는다.) 는 공집합으로 초기화를 해준다.

앞으로 최적의 선택을 해가며 Y와 F를 채워나갈 것이며, 집합 Y가 집합 V (G의 vertex 집합)와 같아지면 멈춘다.

Y	{v1}
F	{}

v1에서 가장 가까운 그래프는 v2이다. Y 집합에 v2를 추가하고, F 집합에는 v1과 v2를 잇는 edge를 추가한다.

Y	{v1, v2}
F	{(v1, v2)}

이번에는 v1과 v2에서 가장 가까운 점을 찾는다. (가장 가까운 edge가 여러개라면 랜덤하게 하나를 선택하면 된다.) 이 경우에는 v3가 가장 가깝다. 또 Y와 F 집합에 추가한다.

Y	{v1, v2, v3}
F	{(v1, v2), (v1, v3)}

이런 식으로 Y가 V와 같아질 때까지 이 방법을 반복한다. 마지막에는 다음과 같은 최소신장트리를 얻을 수 있을 것이다. (다른 최소신장트리가 존재하기 때문에 아래 그림이 유일한 것은 아니다.)

그래프 G에서 얻은 최소신장트리

Y	{v1, v2, v3, v4, v5}
F	{(v1, v2), (v1, v3), (v3, v4), (v4, v5)}

 

프림 알고리즘 구현하기 (C++)

위에 그린 그래프를 이용하여 최소신장 트리 만들기 코드를 구현했다.

• 문제: 노드 1에서 시작하는 최소신장트리(MST) 만들기
• weight matrix는 그래프의 가중치를 나타낸 adjacency matrix이다.
• F는 최소신장트리의 edge들을 담을 배열이다. (처음에는 아무것도 담아두지 않는다.)
• vnear: F에 있는 edge들에서 가장 가까운 거리에 있는 노드의 index
• nearest: 인덱스별로 가장 가까운 노드의 index를 담아둔다. (2-n)
• distance: 인덱스별로 가장 가까운 노드와의 거리를 담아둔다. (2-n)

/* Problem: Make minimum spanning tree startin from node 1 */
#include <iostream>
#include <string>
using namespace std;
#define INF 9999

struct edge {
	int x1;
	int x2;
};

void prim(int n, int W[][5], edge* F) {
	int vnear;
	int min;
	int i, j;
	int f_size = 0;
	
	// the nearest node from the index (2-n)
	// 0, 1 index is ignored. It's just for readibility.
	int* nearest = new int[n+1];
	// distance of the index and the nearest node (2-n)
	int* distance = new int[n+1];

	for (i = 2; i <= n; i++) {
		nearest[i] = 1;
		distance[i] = W[0][i-1];
	}

	for (i = 0; i < n; i++) {
		min = INF;
		for (j = 2; j <= n; j++) {
			if (distance[j] < min && distance[j] >= 0) {
				min = distance[j];
				vnear = j;
			}
		}

		edge new_edge;
		new_edge.x1 = vnear;
		new_edge.x2 = nearest[vnear];

		F[f_size] = new_edge;
		f_size++;

		distance[vnear] = -1;

		for (j = 2; j <= n; j++) {
			if (W[j-1][vnear-1] < distance[j]) {
				distance[j] = W[j-1][vnear-1];
				nearest[j] = vnear;
			}
		}
		
	}
}

int main() {
	int weigth_matrix[5][5] = 
	{	{0, 1, 3, INF, INF},
		{1, 0, 3, 6, INF},
		{3, 3, 0, 4, 2},
		{INF, 6, 4, 0, 5},
		{INF, INF, 2, 5, 0} };

	// MST's maximum edge number is n-1
	edge* F = new edge[4];

	prim(5, weigth_matrix, F);

	int i;
	for (i = 0; i < 4; i++) {
		cout << F[i].x1 << "," << F[i].x2 << endl;
	}
	
}

 

결과

2,1
3,1
5,3
4,3