Kruskal 알고리즘 구현 과제

프로그램 개요

 

욕심쟁이 방법은 최적화 문제를 해결하기 위한 방법이다. 가능한 모든 대안 중에서 가장 좋은 해답을 고르는 문제에 대표적인 최소 비용 신장 트리 구하기를 보다 구체적으로 이해하기 위해, 최소 비용 신장 트리의 구현 방법 중 Kruskal의 알고리즘을 선택. 알고리즘의 필요한 init_set(), find_set(), union_set() 함수를 구현.

 

프로그램 구조

 

아래 조건을 만족하는 최소 비용 신장 트리를 만들어 최소 비용을 구한다.

간선의 가중치의 합이 최소.

반드시 (n-1)개의 간선만을 사용.

사이클이 포함되어서는 안 된다.

 

오름차순(퀵 정렬을 이용)으로 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택하여 현재의 최소 비용 신장 트리의 집합에 추가한다.

 

집합을 구현하는 데에는 가장 효율적인 방법인 트리 형태를 사용한다.

 

프로그램설계

 

사이클을 생성하는지 체크하기 위해 지금 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사하는 find_set() 함수를 구현하고, 같은 집합에 속하지 않는다면 사이클을 형성하지 않는다고 판단하여, 두 정점을 집합으로 입력받아 2개의 집합의 합집합을 만드는 union_set() 함수를 구현.

 

집합을 트리 형태로 구현하기 위해 parent 배열을 init_set() 함수에서 만든다. 각 인덱스에는 음수와 양수가 들어갈 수 있다.

- 루트 노드가 아닌 노드는 parent[node] = node의 부모 노드 인덱스로 표현.

루트 노드는 parent[rooot] - (root 집합의 원소개수)로 표현.

 

parent 배열을 이용하여 각 상황에 맞는 합집합을 만드는 연산들을 구현.

 

소스코드

#include <stdio.h>
#include <stdlib.h> // qsrot 함수가 선언된 헤더 파일 (퀵정렬)
#define MAX_VERTICES 9 // 정점의 수
#define INF 1000 // 무한대

typedef struct { // 간선의 집합을 만들기 위한 구조체
	int key; // 간선의 가중치
	int u; // 정점 1
	int v; // 정점 2
}element;
int compare(const void *a, const void *b) { // 오름차순 비교 함수 구현
	element *m = (element *)a; // void 포인터를 element 포인터로 변환한 뒤 역참조하여 값을 가져옴
	element *n = (element *)b; // void 포인터를 element 포인터로 변환한 뒤 역참조하여 값을 가져옴
	if (m->key < n->key) return -1; // a가 b보다 작을 때는 -1 반환
	if (m->key > n->key) return 1; // a가 b보다 클 때는 1 반환
	return 0; // a와 b가 같을 때는 0 반환 
}

int parent[MAX_VERTICES]; // 부모 노드
int edge_num = 0; // 간선의 개수

void init_set(int n) { // 초기화
	parent[n] = -1;
}
int find_set(int v) { // v가 속하는 집합을 반환
	while (parent[v] >= 0) {
		v = parent[v]; // 루트 노드까지 반복
	}
	return v; // 집합의 대표 원소를 반환
}
void union_set(int n1,int n2) { // 두 개의 원소가 속한 집합을 합친다.
	int tem; // parent 배열의 원소를 루트 노드로 바꾸게 되면 그 정점의 개수가 사라지기 때문에 정점의 개수를 저장해둘 변수
	int i;
	// 따로 원소의 개수가 있는 배열을 만들지 않고
	// parent 배열에서 양수인 인덱스는 루트노드를 나타내고,
	// 음수는 루트노드로써 인덱스의 절대값은 원소의 개수를 나타내므로 음수와 양수일 때를 구분한다.
	if (parent[n1] < 0 && parent[n2] < 0) { // 두 정점이 전부 루트 노드일 때
		if (parent[n1] <= parent[n2]) { // n1의 원소의 개수가 n2보다 작거나 같다면
			tem = parent[n2]; // n2의 개수를 저장
			parent[n2] = n1; // n2의 루트를 n1으로 저장
			parent[n1] += tem; // n1에 n2의 개수를 더함
		}
		else { // n1의 원소의 개수가 n2보다 크다면
			tem = parent[n1]; // n1의 개수를 저장
			parent[n1] = n2; // n1의 루트를 n2으로 저장
			parent[n2] += tem; // n2에 n1의 개수를 더함
		}
	}
	else if (parent[n1] < 0 && parent[n2] >= 0) { // 한 정점만 루트 노드일 때(n1이 루트 노드)
		tem = parent[n1]; // n1의 개수를 저장
		parent[n1] = parent[n2]; // n1의 루트를 n2의 루트로 설정
		parent[parent[n2]] += tem; // n2의 루트에 n1의 개수를 저장
	}
	else if (parent[n1] >= 0 && parent[n2] < 0) { // 한 정점만 루트 노드일 때(n2가 루트 노드)
		tem = parent[n2]; // n2의 개수를 저장
		parent[n2] = parent[n1]; // n2의 루트를 n1의 루트로 설정
		parent[parent[n1]] += tem; // n1의 루트에 n2의 개수를 저장
	}
	else { // 두 정점 모두 루트 노드가 아닐 때
		tem = parent[n1]; // n1의 루트가 어디인지 저장
		parent[n1] = parent[n2]; // n1의 루트를 n2의 루트로 설정
		parent[tem] = parent[n2]; // n1의 루트의 루트를 n2의 루트로 설정
	}
	printf("정점 %d 과(와) %d 를(을) 유니온! 배열 parent --> ",n1,n2);
	for (i = 0; i < MAX_VERTICES; ++i)
		printf("%3d", parent[i]); // parent 의 변화를 출력
	printf("\n");
}
int krustkal(element e[],int n) { // 간선 배열, 정점의 개수
	int i, u, v;
	int mst_e = 0; // 최소 비용
	int mst_e_n = 0; // 최소 비용을 구하는데 선택된 간선의 수
	qsort(e, edge_num, sizeof(element), compare); // 간선 가중치 정렬
	for (i = 0; i < n; ++i) // 정점의 개수만큼 parent 배열을 초기화
		init_set(i);
	for (i = 0; mst_e_n<n-1; ++i) { // 간선의 개수가 n-1이 될 때까지
		u = e[i].u;
		v = e[i].v;
		if (find_set(u) != find_set(v)) { // 각 정점 u와 v가 같은 집합에 없다면 사이클이 발생하지 않으므로
			mst_e += e[i].key; // 정점 u와 v가 가지는 간선을 채택하여 비용에 추가
			mst_e_n++; // 선택된 간선의 개수를 증가
			union_set(u, v); // 정점 u와 v를 유니온
		}
		else {
			printf("정점 %d 과(와) %d 는(은) 사이클 발생!!\n", u, v);
		}
	}
	return mst_e; // 최소 비용을 반환
}
int main() {
	int mst;  
	int graph[MAX_VERTICES][MAX_VERTICES] = { // input_graph
		{ 0,4,INF,INF,INF,INF, INF, 8, INF },
		{ 4,0,8,INF,INF,INF, INF, 11, INF },
		{ INF,8,0,7,INF,4, INF, INF,2 },
		{ INF,INF,7,0,9,14, INF, INF, INF },
		{ INF,INF,INF,9,0,10, INF, INF, INF },
		{ INF,INF,4,14,10,0, 2, INF,INF },
		{ INF,INF,INF,INF,INF,2, 0, 1, 6 },
		{ 8,11,INF,INF,INF,INF, 1, 0, 7 },
		{ INF,INF,2,INF,INF,INF, 6, 7, 0 } };
	element edge_set[INF]; // 간선 집합
	int i,j;
	for (i = 0; i < MAX_VERTICES; ++i) {
		for (j = i; j < MAX_VERTICES; ++j) {
			if (graph[i][j] != INF && graph[i][j] != 0) { // 그래프를 읽어서 간선들의 집합을 만듬
				edge_set[edge_num].key = graph[i][j];
				edge_set[edge_num].u = i;
				edge_set[edge_num].v = j;
				++edge_num; // 간선의 개수 증가
			}
		}
	}
	mst=krustkal(edge_set, MAX_VERTICES); // 크러스컬 알고리즘 호출
	printf("최소 비용은 %d 입니다.\n", mst);
}

 

 

 

 

 

프로그램실행결과

위 그래프의 최소 비용 신장 트리 생성 과정을 포함하여 최소 비용을 구한 결과

 

결과분석

 

복잡도를 구해보면,

- 퀵 정렬에서는 O(nlogn)가 걸린다.

krustkal함수에서 최대 2e번의 find 연산과 최대 e번의 union 연산을 실행한다. 또한, inits_set 연산은 n번 실행하므로, 정렬이 전체 알고리즘의 복잡도를 좌우하고 이 알고리즘의 시간 복잡도는 O(e loge)이다.