<Prim의 MST 알고리즘> 기본개념과 알고리즘

# Prim의 MST 알고리즘

---

 최소 비용 신장 트리(MST: minimum spanning tree)는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장트리를 말한다. 최소 비용 신장 트리를 이용하면, 도로 건설이나 전기 회로설계, 통신 인프라 구축 등의 문제를 가장 효율적으로 처리할 수 있게 된다.

 Prim의 알고리즘은 시작 정점에서부터 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법을 사용한다. 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함된다. Prim은 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장한다. 이 과정은 트리가 n - 1개의 간선을 가질 때까지 계속된다.  // n개의 정점을 가지는 신장 트리의 간선은 n - 1개이기 때문이다.

 Prim의 알고리즘은 정점 선택을 기반으로 하는 알고리즘이며 이전 단계에서 만들어진 신장 트리 정보를 활용하므로 그 정보를 저장할 필요가 있다. 아래의 그래프를 Prim 알고리즘으로 해결하는 과정을 살펴보자.

 Prim 알고리즘을 이해하는 첫 단추는 프로그래밍 언어가 아닌 손으로 풀어가는 과정을 겪는 것이다. 아래의 과정을 직접 그려보는 것이 Prim 알고리즘을 이해하는 데 도움을 줄 것이다.

 #1 시작점을 0번 정점으로 설정해둔 후에 각 정점까지의 거리가 얼마인지 적는다. 무한대로 표시되어 있는 것은 바로 가는 경로가 없고 어딘가를 거쳐서 가야함을 뜻한다. 우리는 직접적으로 연결되어 있는 정점의 거리만 표시한다. 표시한 거리 중 가장 짧은 거리는 0번 정점과 4번 정점의 거리인 3이다. 따라서 첫 번째 경로인 0 - 4 경로(간선)을 찾았다.

 #2 기존의 경로인 0 - 4를 기준으로 두고 생각해보자. 4번 정점을 기준으로 새롭게 나아갈 수 있는 곳들의 거리를 표시해보자. 4번정점에서는 1번 정점, 그리고 6번 정점으로 갈 수 있으므로 각 거리를 적어준다. 그 중에서 1번 정점까지의 거리가 가장 짧으므로 1번 정점을 택한다. 이로서 1- 4의 경로가 선택됐다.

 #3 이번에는 1번 정점에서 어디로 나아갈 수 있는지를 찾아본다. 2번과 3번, 그리고 5번으로 나아갈 수 있다. 여기서 5번 정점을 주목해보자. 이미 길이가 10인 경로가 존재했지만, 1번 정점을 통하면 거리가 6으로 줄어든다. 우린 최소경로를 찾고 있는 것이기 때문에 이렇게 더 짧은 경로가 발견되면 그 정보를 갱신해준다. 

 이미 선택된 최소경로를 제외하면, 새롭게 나아갈 곳 중 가장 짧은 경로는 1 - 2 경로다. 따라서 2번 정점을 선택한다.

#4 위에서 선택한 2번을 토대로 갱신할 수 있는 경로 혹은 새롭게 나아갈 수 있는 경로가 있는지 탐색한다. 새롭게 나아갈 수 있는 경로는 없었지만, 갱신할 수 있는 정보가 있다. 2번에서 3번 경로가 기존의 10길이에서 2길이로 줄어드므로 갱신해준다. 그 후 현재까지 선택된 경로 중 가장 거리가 짧은 경로인 2 - 3 경로를 선택해준다. 이로써 3번 정점이 선택됐다.

 #5 위에서 선택한 3번 정점을 토대로 새로얻을 수 있는 정보는 3 - 6 경로의 거리 정보다. 기존의 길이인 5보다 더 짧은 4가 나오므로 정보를 갱신해준다. 그 후 지금까지 선택된 정점을 제외한 것 중 가장 짧은 경로인 3 - 6 경로를 선택한다. 즉 우리는 6번 정점을 선택한 것이다.

 #6 마지막이다. 지금까지의 경로 중 선택되지 않은 정점은 5번 정점이다. 5번 정점을 선택하고 새롭게 갱신할 수 있는 정보가 있는지 살펴본다. 없다. 5번 정점의 거리는 1번 정점을 선택할 때 나온 것이므로, 1 - 5의 경로가 선정됐다. 이로써 Prim 알고리즘의 종료다. MST에 적어둔 경로들로 종합한 것이 그래프의 최단 경로다.

#7 Prim을 직접 손으로 작성해보고, 그 결과인 간선들을 토대로 탄생한 최소 신장 그래프는 아래의 그래프다.

# Prim의 알고리즘 구현

---

 먼저 dist라는 정점의 개수 크기의 배열이 필요하다. dist는 현재까지 알려진 신장트리의 정점 집합에서 각 정점까지의 거리를 가지고 있다. 처음에는 시작 노드만 값이 0이고, 다른 노드는 전부 무한대(프로그램에서는 1000L)의 값을 갖는다. 아직까지 트리집합에는 아무것도 존재하지 않는다.

 정점들이 트리 집합에 추가되면서 dist의 값은 변경된다. 여기서 우선순위 큐를 하나 도입한다. 배열로 구현할 수도 있고 히프를 통해 구현할 수도 있다. 우선순위 큐에 모든 정점을 삽입한다. 이 때의 우선순위는 dist 배열값이 된다. 다음은 while 루프로 우선순위큐에서 가장 작은 dist값을 가지는 정점을 추출한다. (첫 실행때는 시작 정점인 0이 추출될 것이다.) 추출된 정점이 트리 집합에 추가된다. 프로그램에서 추가의 구현은 화면에 출력하는 것으로 했다.

 다음에는 트리 집합에 새로운 정점 u가 추가되었으므로 u에 인접한 정점 v들의 dist값을 변경시켜준다. 즉 기존의 dist[v] 값보다 간선 (u, v)의 가중치가 적으면 간선 (u, v)의 가중치로 dist[v]를 변경시킨다. 우선순위큐에 있는 모든 정점들이 소진될 때까지 이러한 과정을 되풀이하면 된다. 한 번 선택된 정점은 Q에서 삭제되므로 다시 선택되지는 않는다.

 그리고 트리 집합에 인접하지 않는 정점들의 dist 값은 무한대이므로 역시 선택되지 않을 것이다. 아래는 프로그램 코드다. 코드를 간단히 하기 위하여 오류 처리가 생략되었는데, 만약 알고리즘 도중에 선택된 정점의 dist 값이 무한대이면 오류처리가 된다. 왜냐하면 우린 최소 신장 트리를 구하고 있고 그 과정이 반드시 인접한 정점을 선택하는 것이 되어야 하기 때문이다.

/*************************************************
 ** Prim의 최소 비용 신장 트리 프로그램
*************************************************/

#include <stdio.h>
#define TRUE 1
#define FALSE 0

#define MAX_VERTICES 7	// 신장트리의 정점 개수
#define INF 1000L	// 경로가 없는 INFINITE를 표현하기 위해 정의된 상수 INF

int weight[MAX_VERTICES][MAX_VERTICES] = {// 신장트리의 거리와 모양을 배열로 표현, INF는 바로갈 수 있는 경로가 없음을 뜻한다.
	{0,29,INF,INF,INF,10,INF},
	{29,0,16,INF,INF,INF,15},
	{INF,16,0,12,INF,INF,INF},
	{INF,INF,12,0,22,INF,18},
	{INF,INF,INF,22,0,27,25},
	{10,INF,INF,INF,27,0,INF},
	{INF,15,INF,18,25,INF,0}
};

int selected[MAX_VERTICES]; // 선택된 정점의 정보를 담을 배열, 선택이 됐는지 안됐는지를 표시한다.
int dist[MAX_VERTICES];	// 최소의 거리 정보만을 담는 배열, 새로운 최소거리가 나올 때마다 갱신된다.

// 최소 dist[v]값을 갖는 정점을 반환
int get_min_vertex(int n)
{
	int v, i;	// 정점의 정보를 저장할 변수 v, 반복문을 위한 변수 i
	
	for (i = 0; i < n; i++)
	{
		if (selected[i] == FALSE) {
			v = i;	// 아직 선택되지 않은 정점의 번호를 v에 저장, 각 함수 실행별 0부터 n - 1까지 차례대로 저장된다.
			break;
		}
	}

	// 위에서 선택된 정점이 과연 최소거리를 지니고 있는 정점인지를 확인한다.
	for (i = 0; i < n; i++)
	{
		// 선택되지 않은 정점들을 순회하면서 최소거리를 가진 정점을 찾아낸다.
		if (selected[i] = FALSE && (dist[i] < dist[v]))
			v = i;	// 더 적은 거리가 존재한다면 해당 정점을 저장한다.
	}

	return(v);	// 최소의 거리를 갖는 정점이 선택됐으므로 정점 번호를 리턴한다.
}

// Prim, s는 시작 정점
void prim(int s, int n)
{
	int i, u, v;

	for (u = 0; u < n; u++)	// dist배열과 selected배열의 정보를 초기화
	{
		dist[u] = INF;
		selected[u] = FALSE;
	}

	dist[s] = 0;	// 시작정점과 시작정점간의 거리는 0이다. 자기자신을 순환하는 경로는 없다고 가정한다.
	
	for (i = 0; i < n; i++)
	{
		// 리턴된 정점 번호를 u에 저장한다. u는 최소거리를 가지는 정점. 손으로 썻을 때 선택하는 효과를 가져온다.
		u = get_min_vertex(n);
		selected[u] = TRUE;	// 최소거리를 갖는 정점의 정보(u)를 알아냈으니 해당 정점을 선택했다고 표시한다.

		// 만약 경로가 없다면 함수를 종료한다. 정상적인 신장트리의 정보가 들어왔다면 실행될 일은 없을 것이다.
		if (dist[u] == INF) return;
		
		printf("%d ", u);	// 방문한 정점(u)을 출력한다.

		for (v = 0; v < n; v++)	// 이 과정은 우리가 새롭게 발견한 정보를 저장하는 과정이다.
		// 직접적인 경로가 발견되어 INF 에서 상수거리로 바뀌는 과정과
		// 기존의 상수거리보다 더 짧은 거리가 발견되 그 정보를 갱신하는 과정이 포함되어 있다.
		{
			// 선택된 u 정점을 기준으로 정점(u)과 연결되어 있는 정점까지의 거리를 각각 비교한다.
			if (weight[u][v] != INF)	// 정점 u와 연결이 되어있고
			{
				// 아직 선택되지 않았으며 해당 변(weight[u][v])의 길이가 기존의 dist[v] 값보다 작다면
				if (selected[v] == FALSE && weight[u][v] < dist[v])
					dist[v] = weight[u][v];	// dist[v]의 값을 갱신해준다.

				// 새롭게 발견되는 정점들이 초반에 저장될 수 있는 건 INF를 1000으로 설정해줬기 때문이다.
				// 우리가 만든 그래프의 경로값들은 전부 100이하의 값이기 때문에 새롭게 발견되는 정점이 있다면
				// 우선 등록되고 그 후 더 짧은 거리가 등장하면 갱신되는 형태로 이 프로그램은 작동한다.
			}
		}
	}
}

void main()
{
	prim(0, MAX_VERTICES);	// 정점 개수가 7개인 그래프에서 0번 정점을 출발하여 얻을 수 있는 최소비용신장트리를 찾아라.
}

/*************************************************
 ** End Line
*************************************************/