[자료구조] 프림(Prim)의 MST 알고리즘

프림(Prim)의 MST 알고리즘

Prim 알고리즘은 특정 정점에서 시작해 신장 트리 집합을 단계적으로 확장해 나가는 방법입니다.

 

인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택해 트리를 간선이 $n-1$개가 될 때까지 확장합니다.

 

최소 신장 트리 구하는 과정

예시로 한 그래프에서 Prim 알고리즘을 이용해 MST를 구해보도록 하겠습니다. 시작 정점은 0이라고 가정하겠습니다.

결론적으로 이 그래프의 최소 신장 트리는 마지막 사진에 색칠한 것과 같이 이루어짐을 알 수 있습니다.

 

코드로 구현하면 아래와 같습니다.

typedef struct Graph {
	int n; // 정점의 개수
	int weight[MAX_VERTICES][MAX_VERTICES];
} Graph;

int selected[MAX_VERTICES];
int distance[MAX_VERTICES];

// 최소 dist[v]값을 갖는 정점을 반환
int get_min_vertex(int 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;
}

void prim(Graph *g, int s) {
	for(int u = 0; u < g->n; u++) {
		distance[u] = INF;
	}
	distance[s] = 0;
	for(int i = 0; i < g->n; i++) {
		u = get_min_vertex(g->n);
		selected[u] = TRUE;
		if(distance[u] == INF) return;
		printf("정점 %d 추가\n", u);
		for(int v = 0; v < g->n; v++) {
			if(g->weight[u][v] != INF) {
				if(!selected[v] && g->weight[u][v] < distance[v]) {
					distance[v] = g->weight[u][v];
				}
			}
		}
	}
}