최소 비용 신장 트리(MST): Kruskal, Prim 알고리즘

 

신장 트리(Spanning Tree)

 

• 그래프 내의 모든 정점을 포함하는 트리
• 모든 정점들이 연결되어 있고 사이클을 포함하면 안된다.
• 그래프의 최소(간선의 수가 가장 작은) 연결 부분 그래프
  • n개의 가지는 그래프는 최소한 (n-1)개의 간선을 가진다.
• 간선에 비용을 붙여 링크의 구축 비용까지를 고려해 최소 비용의 신장 트리를 선택해야함
• 통신 네트워크 구축에 많이 사용

 

최소 비용 신장 트리(MST)

 

• 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결
• 신장 트리 중에서 사용된 간선들이 가중치 합이 최소인 신장 트리
• Kruskal, Prim 알고리즘이 대표적
• 반드시 n-1 개의 간선만 사용하고, 사이클이 포함되어서는 안된다.

 

 

Kruskal 의 MST 알고리즘

 

• 탐욕적인 방법(greedy method)을 이용
• MST가 최소 비용의 간선으로 구성, 사이클을 포함하지 않는다는 조건에 근거하여 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택

 

과정

1. 그래프의 간선들을 가중치의 오름차순으로 정렬한다.
2. 정렬된 간선들의 리스트에서 사이클을 형성하지 않는 간선을 찾는다.
   • 가장 낮은 가중치를 먼저 선택한다.
   • 사이클을 형성하면 그 간선은 제외된다.
3. 해당 간선을 현재의 최소 비용 신장 트리의 집합에 추가한다.

 

 

시간복잡도

간선들을 정렬하는 시간에 좌우된다. 효율적인 정렬 알고리즘을 사용한다면 시간복잡도는 O(eloge) 이다. 

 

 

구현

#include <stdio.h>
#include <stdlib.h>
#define INF 1000L
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 100

int parent[MAX_VERTICES]; // 부모 노드

void set_init(int n) { // 초기화 
	for (int i = 0; i < n; i++) parent[i] = -1;
}

// curr의 루트 노드를 반환(curr가 속하는 집합 찾기)
int set_find(int curr) {
	if (parent[curr] == -1) // 자기 자신이 루트 노드
		return curr;

	while (parent[curr] != -1) curr = parent[curr]; // 가장 상위인 루트 노드 찾기
	return curr;
}

// 두개의 원소가 속한 집합을 합침
void set_union(int a, int b) {
	int root1 = set_find(a); // 노드 a의 루트 찾기
	int root2 = set_find(b);  // 노드 b의 루트 찾기
	if (root1 != root2) // 두 노드의 집합이 다르다면
		parent[root1] = root2; // 합한다.
}

//간선의 정보
struct Edge {
	int start, end, weight;
};

//그래프의 정보
typedef struct GraphType {
	int n;	// 간선의 개수
	struct Edge edges[2 * MAX_VERTICES];
} GraphType;

// 그래프 초기화 
void graph_init(GraphType* g) {
	g->n = 0;
	for (int i = 0; i < 2 * MAX_VERTICES; i++) {
		g->edges[i].start = 0;
		g->edges[i].end = 0;
		g->edges[i].weight = INF;
	}
}

// 간선 정보 삽입 연산
void insert_edge(GraphType* g, int start, int end, int w) {
	g->edges[g->n].start = start;
	g->edges[g->n].end = end;
	g->edges[g->n].weight = w;
	g->n++;
}

// qsort 함수의 정렬방식을 결정하는 함수. 1, 0, -1 값중 하나 리턴
// 리턴값이 1이면 오름차순, -1이면 내림차순
int compare(const void* a, const void* b) {
	struct Edge* x = (struct Edge*)a;
	struct Edge* y = (struct Edge*)b;

	return (x->weight - y->weight); // 오름차순 
}

// kruskal의 최소 비용 신장 트리 프로그램
void kruskal(GraphType* g) {
	int edge_accepted = 0; // 현재까지 선택된 간선의 수 
	int uset, vset; // 정점 u와 정점 v의 집합 번호
	struct Edge e; // 간선

	qsort(g->edges, g->n, sizeof(struct Edge), compare); // 간선들의 가중치 오름차순 정렬
	set_init(g->n); // 부모 노드 배열 초기화 

	int i = 0;
   
	while (edge_accepted < (g->n - 1)) { // 간선의 수 < (n-1) 일 때 가중치 낮은 간선들부터 탐색
		e = g->edges[i];
		uset = set_find(e.start);  // 정점 u의 집합 번호
		vset = set_find(e.end); // 정점 v의 집합 번호

		if (uset != vset) { // 같으면 사이클이 될 수 있음
			printf("간선 : (%d, %d): %d 선택\n", e.start, e.end, e.weight);
			edge_accepted++; // 선택된 간선 수 1증가
			set_union(uset, vset); // 두개의 집합을 합친다.
		}
		i++;
	}
}

int main(void) {
	GraphType* g;
	g = (GraphType*)malloc(sizeof(GraphType));
	graph_init(g);
	insert_edge(g, 0, 1, 29);
	insert_edge(g, 1, 2, 16);
	insert_edge(g, 2, 3, 12);
	insert_edge(g, 3, 4, 22);
	insert_edge(g, 4, 5, 27);
	insert_edge(g, 5, 0, 10);
	insert_edge(g, 6, 1, 15);
	insert_edge(g, 6, 3, 18);
	insert_edge(g, 6, 4, 25);

	kruskal(g);
	free(g);
	return 0;
}

간선 : (5, 0): 10 선택
간선 : (2, 3): 12 선택
간선 : (6, 1): 15 선택
간선 : (1, 2): 16 선택
간선 : (3, 4): 22 선택
간선 : (4, 5): 27 선택

 

 

Prime의 MST 알고리즘

 

• 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법
• 정점을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장 트리를 확장

 

과정

1. 시작 정점만이 MST 집합에 포함
2. 앞 단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리를 확장
   • 인접한 정점들 중 가장 낮은 가중치를 먼저 선택
3. 위의 과정을 신장 트리 집합에 정점의 개수가 n-1개가 될 때까지 반복

 

 

시간복잡도

 

주 반복문이 정점의 수 n만큼 반복하고, 내부 반복문이 n번 반복하므로 O(n^2)의 복잡도를 가진다.

 

 

구현

#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]; // 방문 체크 
int distance[MAX_VERTICES];

int get_min_vertex(int n) { // distance 배열의 가장 작은 값을 갖는 정점 찾기  
	int v, i;
	for (i = 0; i < n; i++) {
		if (!selected[i]) {
			v = i; // 방문하지 않은 정점 찾기 
			break;
		}
	}
	for (i = 0; i < n; i++) // v정점에 대해 최솟값을 갖는 i찾기 
		if (!selected[i] && (distance[i] < distance[v])) v = i; // v보다 i의 distance값이 작다면 v를 i값으로 갱신

	return(v); 
}

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

	for (u = 0; u < g->n; u++) 
		distance[u] = INF; // 거리 무한대로 초기화
	distance[s] = 0; // 0번 정점 0으로 설정

	for (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 (v = 0; v < g->n; v++)
			if (g->weight[u][v] != INF) // u의 인접 정점중 가중치가 무한대가 아니면
				if (!selected[v] && g->weight[u][v] < distance[v]) // 기존의 distance[v] 값보다 간선(u,v)의 가중치 값이 적으면
					distance[v] = g->weight[u][v]; // 간선(u,v)의 가중치 값으로 distance[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;
}

정점 0 추가
정점 5 추가
정점 4 추가
정점 3 추가
정점 2 추가
정점 1 추가
정점 6 추가