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; }