MST: 프림 알고리즘

‘부분 트리에 속한 정점’과 ‘인접한 정점’ 사이의 에지 중 가중치가 최소인 에지를 선택한다. n-1개의 에지가 선택될 때까지 진행한다. prim으로 인해 만들어진 부분트리를 S, 나머지 정점들을 T라고 놓고 문제를 접근한다.

프림 알고리즘 구현

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

#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100
#define INF 1000L

typedef struct GraphType {
	int n;
	int weight[MAX_VERTICES][MAX_VERTICES];
}GraphType;

int selected[MAX_VERTICES]; // <테이블의 s/t열> , 선택되면 s집합에 속함 
int w[MAX_VERTICES]; // <테이블의 w열> , 원소: s집합에서 해당 정점까지의 거리 

// 현재 테이블(s/t,w) 상태 출력 
void print_status(GraphType* g) {
	printf("\nS/T: ");
	for (int i = 0; i < g->n; i++)
		printf("%2d ", selected[i]);
	printf("\n");
	printf("W:   ");
	for (int i = 0; i < g->n; i++) {
		if (w[i] == INF)
			printf("INF ");
		else
			printf("%2d ", w[i]);
	}
	printf("\n");
}

// s집합에 속하지 않으면서 최소 w[v] 값을 갖는 정점을 반환
int get_min_vertex(int n) {
	int v, i;
	// 선택되지 않은 정점을 선택 (v정점 지정) 
	for (i = 0; i < n; i++) {
		if (!selected[i]) {
			v = i;
			break;
		}
	}
	// v정점의 w값과 나머지 정점들의 w값을 비교하면서 최소 w값을 갖는 정점 구하기 (선택된 것은 제외) 
	for (i = 0; i < n; i++) {
		if (!selected[i] && (w[i] < w[v]))
			v = i;
	}
	return v;
}

void prim(GraphType* g, int s) {
	int i, u, v;

	// s집합에 원소가 없으면 a(0)만 인접하다고 가정하고 문제를 풀음 
	for (u = 0; u < g->n; u++)
		w[u] = INF;
	w[s] = 0;

	// s집합에 원소가 한 개 이상 있을 때 반복문으로 문제 풀기 (정점을 n개 선택할 때까지)
	for (i = 0; i < g->n; i++) {
		print_status(g);
		// w배열에서 가중치가 가장 작은 정점 선택 (s에 속하지 않은 정점들로 한정) 
		u = get_min_vertex(g->n);
		selected[u] = TRUE;
		if (w[u] == INF) {
			printf("-> 선택할 정점이 없음\n");
			return;
		}
		else
			printf("-> 정점 %c 선택\n", u+97);

		// s집합과 인접한 정점들로 w배열 업데이트
		for (v = 0; v < g->n; v++) {
			// u정점을 기준으로 인접한 것을 찾음 <u정점 말고 다른 정점도 s집합에 속하지만 같은 배열을 업데이트하는 개념이므로, 이미 처리가 된 상태임>
			if (g->weight[u][v] != INF) {
				if (!selected[v] && g->weight[u][v] < w[v]) // v정점이 s집합에 속하면 처리 x, u-v의 가중치가 기존의 w배열 원소보다 작으면 업데이트 
					w[v] = g->weight[u][v];
			}
		}
	}
}

int main(void) {

	// a(0)부터 g(7)까지를 정점으로 가지는 그래프 
	GraphType g = { 8,{
		{0,2,INF,3,INF,INF,INF,INF},
		{2,0,5,4,INF,INF,INF,INF},
		{INF,5,0,4,INF,INF,INF,6},
		{3,4,4,0,1,2,INF,7},
		{INF,INF,INF,1,0,5,7,INF},
		{INF,INF,INF,5,5,0,8,INF},
		{INF,INF,INF,INF,7,8,0,INF},
		{INF,INF,6,7,INF,INF,INF,0}
		}
	};
	prim(&g, 0);
	return 0;
}