그래프 - Prim의 MST 알고리즘

# [C언어로 쉽게 풀어쓴 자료구조(천인국)]를 공부하고 주요 내용을 정리하고자 작성하는 글입니다.

# 해당 게시글에 대한 모든 피드백 환영합니다. 

 

Prim의 MST 알고리즘

시작 정점에서 출발하여 신장 트리 집합을 단계적으로 확장해 나가는 방법으로,
이전 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택한다.

아래의 그래프를 이용해 이해하며 위의 정의를 곱씹어 본다.

• 시작 정점을 0으로 두자.

==> 신장트리 집합: { 0 }

• 0의 인접 정점 중 최소 간선을 선택하자.

==> 신장트리 집합: { 0, 5 }

• 이 상태에서 신장트리 집합에 인접(*)한 정점을 살펴보면, 1과 4가 있다. 간선 (0,1)과 (5,4)의 가중치를 비교해보면 (5,4)가 27로서 (0,1)의 29보다 작다. 따라서 간선 (5,4)가 선택되고 정점 4가 신장트리 집합에 포함된다. 

==> 신장트리 집합: { 0, 5, 4 }

• 다음 단계에서 신장트리 집합은 { 0, 5, 4, 3 } 이 된다.
• 신장트리 집합의 정점의 개수가 (n-1)개가 될 때까지 이 과정이 되풀이된다. 

(*)인접: 간선 하나만 건너면 바로 있는 것.

 

Kruskal 알고리즘과의 차이는,

Kruskal 알고리즘은 간선을 기반으로 한다면, Prim 알고리즘은 정점을 기반으로 한다.

 

Kruskal 알고리즘은, 이전 단계에 만들어진 신장트리집합의 인접정점은 전혀 신경쓰지 않고

무조건 전체 그래프에서 최저 가중치 간선을 고른다. 

Prim 알고리즘은, 이전 단계에 만들어진 신장트리집합의 인접정점 중에서 최저 가중치 간선을 고르며

신장트리를 확장하는 방식이다.

 

즉, Kruskal 알고리즘은 항상 전체를 기준으로 최저 가중치 간선을 고르는, 전체 중에 하나씩 선택하는 느낌이라면,

Prim 알고리즘은 현재 집합을 기준으로 인접정점을 찾아 고르는, 확장되는 느낌이다.

 

Dijkstra 알고리즘과의 차이는,

신장트리 집합에 인접한 정점들 중에서 가중치를 볼 때,

 

Prim 알고리즘의 경우, 트리 내 정점과 트리 밖 정점 간의 거리(가중치)를 다시 계산하지 않는다.

반면에 Dijkstra 알고리즘의 경우, 트리 내 정점과 트리 밖 정점 간의 거리(가중치)를 다시 계산한다.

 

그렇다면 Prim 알고리즘은 어떻게 구현될까?

생각의 순서는 다음과 같다.

 

*사용할 변수

distance[] : 현재까지 알려진 신장트리 집합으로부터 각 정점까지의 가중치를 저장한 배열

weight[]: 각 정점 간의 원래 가중치를 저장한 배열; INF == 간선이 없음

1. 시작 정점을 s 라고 한다.
2. 시작정점을 제외한 모든 정점에 대한 거리를 INF(무한대)로 설정한다.
3. 시작정점의 거리는 0으로 설정한다.
4. 그래프의 모든 정점에 대해서,
   • 트리 밖의 정점 중, 최소 거리를 갖는 정점 u를 가져와 트리에 포함시킨다.
   • 정점 u에 인접한 정점 v들의 distance값을 변경한다.
     • 기존의 distance[v]값 > 간선(u,v)의 가중치 값 ==> distance[v] = weight[u][v]
     • 위의 조건이 만족하지 않는 경우, continue.

c언어로 구현

#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 50
#define INF 999

typedef struct GraphType {
	int n; // 정점의 개수
	int weight[MAX_VERTICES][MAX_VERTICES]; // 원래 거리를 저장할 배열
} GraphType;

int selected[MAX_VERTICES];	// 트리 내 정점으로 선택된 배열은 TRUE로 된다
int distance[MAX_VERTICES];	// 트리 내에서 각 정점 간의 거리

// 최소 distance[v]값을 갖는 정점을 찾는다
int get_min_vertex(int n) //정점의 개수: n
{
	int v;	// 최소 거리를 갖는 정점을 담을 변수
	for (int i = 0; i < n; i++) {
		if (!selected[i]) {		// 일단 방문 안 한 정점을 찾고,
			v = i;
			break;
		}
	}
	// 그 정점을 기준으로 그래프 내 모든 정점들과 거리를 비교해서
	// 최소 거리를 갖는 정점을 찾는다. 
	// 단, 트리 밖인 정점에 한해서.
	for (int i = 0; i < n; i++) {
		if (!selected[i] && (distance[i] < distance[v]))
			v = i;
	}
	return v;
}
// prim 함수
void prim(GraphType* g, int s)
{
	int i, u, v;

	for (u = 0; u < g->n; u++)		// distance 배열의 값을 모두 INF로 초기화한다.
	{	// 신장트리집합에는 시작정점 빼고 다른 정점까지의 거리를 하나도 모르기 때문.
		distance[u] = INF;
	}
	distance[s] = 0;				// 시작정점에 대한 distance값을 0으로 초기화한다.
	for (i = 0; i < g->n; i++)
	{
		u = get_min_vertex(g->n);	// 신장트리 집합 밖 정점 중 최소거리 정점 GET
		selected[u] = TRUE;			// 해당 정점을 신장트리집합에 포함한다.
		if (distance[u] == INF)		// ERROR 대비
			return;
		printf("정점 %d 추가\n", u);
		
		for (v = 0; v < g->n; v++) {
			if (g->weight[u][v] != INF)	// 정점 u에 인접한 정점 중에서
			{
				if (!selected[v] && g->weight[u][v] < distance[v])
				{	// 트리 밖의 정점이고, 
					// 트리 내에서 계산한 거리보다 기존 거리가 더 짧으면 변경한다.
					distance[v] = g->weight[u][v];
				}
			}
		}
	}
}
int main()
{
	GraphType g = { 7,
		{{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}}
	};
	prim(&g, 0);
	return 0;
}

결과

신장트리 포함 순서

시간복잡도

주 반복문 ==> 정점의 개수 n만큼 반복

내부 반복문 ==> n번 반복

 

==> O(n^2) 

 

따라서,

Kruskal 알고리즘의 시간복잡도는 O(eloge)이므로 희소 그래프에 적합하고,

Prim 알고리즘의 시간복잡도는 O(n^2) 이므로 밀집그래프에 적합하다.