크루스칼 알고리즘

가중치가 작은 순서대로, 에지를 하나씩 추가하며 MST를 만든다. Cycle이 만들어지면 해당 에지는 버린다. 이를 n-1개의 에지가 만들어질 때까지 진행한다.

MST: 최소 신장 트리, 에지 가중치 합이 최소가 되는 신장 트리

구현 방법
1) 가중치가 작은 에지부터 차례대로 고려하기 위해 최소 힙을 사용한다. 최소 힙을 만든 뒤 루트부터 삭제해서 정렬한다.
2) 에지를 추가하였을 때 cycle이 생기는지 알려면 Union-Find를 이용한다. Find를 해서 같은 root가 나오면 같은 집합이다. (cycle 조건) Union은 최대 n-1회, Find는 최대 2m회가 수행된다.

시간복잡도
(1) O(mlogm) + (2) O(m) = O(mlogm)

추가 설명
그래프의 정점을 연결하는 것이나 유니온파인드에서 합집합을 만드는 것이나 형태는 비슷하다.
다만 차이점이 있다.
유니온파인드는 집합에 이미 있는 원소를 또 집어 넣으면 집합의 형태는 변하지 않는다.
그러나 그래프는 선(에지)이 이어져서 사이클을 만드는 형태로 바뀐다.
즉 이 차이점을 사이클의 구분점으로 사용하면 알고리즘을 구상할 수 있다.
-> 두 노드가 같은 루트를 가지면(같은 트리(집합)에 속하면) 사이클이 발생한다고 생각 가능
이는 아래 이미지에서 [5] 과정을 보고 이해할 수 있다.

유니온 파인드 비 최적화 결과

유니온 파인드 최적화 결과 (경로압축 및 가중법칙 적용)

Kruskal을 이용해서 MST의 가중치 합 구하기 (최적화 적용)

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

#define MAX 1000002

// 에지 구조체 
typedef struct {
	int v, w, x; // v,w는 정점, x는 가중치 
}Edge;
int n, m; // 그래프의 정점과 에지 수 

typedef struct {
	Edge heap[MAX];
	int heap_size; // 힙 사이즈가 n이면 heap배열의 원소들이 (idx 1 ~ idx n) 까지 존재 
}HeapType;
typedef HeapType* HeapType_ptr;


// 힙 생성 및 초기화 함수
HeapType_ptr heap_init(Edge* e) {
	HeapType_ptr h = (HeapType_ptr)malloc(sizeof(HeapType));
	// 배열 e를 '완전 이진 트리 배열'로 생각한 뒤 h에 일단 저장 
	h->heap_size = m;
	int i;
	for (i = 1; i <= h->heap_size; i++)
		h->heap[i] = e[i - 1];
	h->heap[i].v = h->heap[i].w = h->heap[i].x = -34529; // 힙의 m+1번째 노드는 쓰레기값 처리 (for. Dev-C++)  
	// -> 힙 성질을 만족하지 않는 h가 생성됨 
	return h;
}

// 에지 m개를 원소로 가진 힙을 O(m) 시간에 구현 
void MyHeapify(HeapType_ptr h) {
	// 힙 성질을 만족하게 할 첫 번째 서브트리 지정 
	int parent, child, parent_save, child_save;
	child = child_save = h->heap_size; // 말단 노드부터 비교 시작 
	parent = parent_save = h->heap_size / 2;

	// 모든 서브트리에 대해 힙 성질 만족 시키기 
	Edge temp;
	while (parent > 0) {
		// 현재 부모 노드의 값을 temp에 저장 
		temp = h->heap[parent];
		// 자식이 힙을 벗어나지 않았으면 반복문 진행 
		while (child <= h->heap_size) {
			// 두 자식노드가 있으면 더 작은 자식노드를 찾는다.
			if ((h->heap[parent * 2].x >= 0) && (h->heap[(parent * 2) + 1].x >= 0)) {
				if ((h->heap[parent * 2].x) < (h->heap[(parent * 2) + 1].x))
					child = parent * 2;
				else
					child = (parent * 2) + 1;
			}
			// temp 노드를 현재 자식의 부모 노드의 위치에 있다고 생각했을 때, 값이 작거나 같으면 힙 조정할 필요가 X
			if (temp.x <= h->heap[child].x)
				break;
			// 부모 노드 자리에 자식 노드의 값들을 저장 
			h->heap[parent] = h->heap[child];
			// 한 단계 아래로 이동
			parent = child;
			child *= 2;
		}
		// child > h->heap_size로, 위치해야 될 노드에 저장 
		h->heap[parent] = temp;
		// 서브트리 재지정 
		parent = parent_save = parent_save - 1;
		child = child_save = parent * 2; // p가 1이고 c가2면 전체 노드를 다 보게 됨 
	}
}

// 힙에서 최소 가중 에지를 삭제하여 되돌려 줌 
Edge myDeleteMin(HeapType_ptr h) {
	int parent, child;
	Edge item, temp;

	item = h->heap[1]; // 루트 노드 값을 반환하기 위해 item변수로 옮긴다.
	temp = h->heap[(h->heap_size)--]; // 말단 노드 값을 temp변수로 옮기고 힙 사이즈를 1 줄인다. (temp값이 처음에는 루트에 위치해있다고 생각) 
	parent = 1;
	child = 2; // 루트의 왼쪽 자식부터 비교한다. 

	while (child <= h->heap_size) {
		if ((h->heap[parent * 2].x >= 0) && (h->heap[(parent * 2) + 1].x >= 0)) {
			if ((h->heap[parent * 2].x) < (h->heap[(parent * 2) + 1].x))
				child = parent * 2;
			else
				child = (parent * 2) + 1;
		}
		// 말단 노드를 현재 자식의 부모 노드의 위치에 있다고 생각했을 때, 값이 작거나 같으면 힙 조정할 필요가 X
		if (temp.x <= h->heap[child].x)
			break;
		h->heap[parent] = h->heap[child];
		parent = child;
		child *= 2;
	}
	h->heap[parent] = temp;
	return item;
}

// 유니온파인드 구조체 
typedef struct {
	int parent;
	int count;
}uf;
typedef uf* ufp;

// 유니온 파인드 생성 및 초기화 함수 
ufp uf_init(int n) {
	ufp u = (ufp)malloc(sizeof(uf) * n);

	int i;
	for (i = 0; i < n; i++) {
		u[i].parent = -1;
		u[i].count = 1;
	}
	return u;
}

// 경로압축을 하고 집합의 루트를 반환한다. 
int myFind(ufp u, int curr) {
	if (u[curr].parent == -1)
		return curr;

	// 루트 노드 찾기 
	int tmp = myFind(u, u[curr].parent);
	// 경로 압축 (리턴해서 받은 루트 노드의 값을 부모 노드의 값으로 사용)
	// 다음에 comp_Find가 호출되면 순환 횟수가 줄어든다. 
	u[curr].parent = tmp;
	return tmp;
}

// 가중법칙을 적용하여 합집합을 만든다. 
void myUnion(ufp u, int a, int b) {
	int root1 = myFind(u, a);
	int root2 = myFind(u, b);
	int temp = u[root1].count + u[root2].count;

	if (u[root1].count < u[root2].count) {
		u[root1].parent = root2;
		u[root2].count = temp;
	}
	else {
		u[root2].parent = root1;
		u[root1].count = temp;
	}
}

// 입력으로 주어진 그래프를 읽는다. 
Edge* readGraph() {
	int i; // iteration 변수 

	// 정점의 수, 에지의 수 입력 
	scanf_s("%d %d", &n, &m);

	Edge* e = (Edge*)malloc(sizeof(Edge) * m); // 에지 배열 생성 
	for (i = 0; i < m; i++)
		scanf_s("%d %d %d", &e[i].v, &e[i].w, &e[i].x);

	return e;
}

int main() {
	Edge* e = readGraph(); // 그래프의 모든 에지를 e배열에 저장  
	HeapType_ptr h = heap_init(e); // 힙 자료구조에 에지 배열 원소를 순차 대입
	MyHeapify(h); // 힙 성질 맞추기 

	// 힙에서 삭제하면서 정렬 
	int i; 
	for (i = 0; i < m; i++)
		e[i] = myDeleteMin(h);
	
	ufp u = uf_init(n); // 유니온 파인드 집합 생성 
	int vroot, wroot, sum, selected_edge; // 각 집합의 루트, 가중치 합계, 연결한 에지의 수 
	selected_edge = sum = 0;

	// 연결한 에지의 수가 n-1이 되면 스패닝 트리 완성 -> 반복문 빠져 나옴 
	for (i = 0; selected_edge < (n - 1); i++) {
		vroot = myFind(u, e[i].v);
		wroot = myFind(u, e[i].w);

		// find를 해서 같은 root가 나오면 이미 같은 집합 -> 연결하면 사이클이 생성됨 
		if (vroot != wroot) {
			myUnion(u, vroot, wroot);
			selected_edge++;
			sum += e[i].x;
		}
	}
	printf("%d", sum);
	
	free(h);
	free(e);
	return 0; 
}