[C++] Union Find & MST & 크루스칼 (Kruskal) 알고리즘 정리

Union Find

Union-Find란 ? Data들끼리 그룹을 짓고 관리할 수 있다. 각 Data들이 같은 그룹에 속해있는지, 다른 그룹인지 확인할 수 있다. 

왜 Union-Find를 쓰는가 ? 각 Data들이 어떤 조직에 속하는지 배열로 관리하기 쉽다. 빠른 속도로 그룹을 통합처리 가능하다.

 

<코드>

#include <iostream>
using namespace std;

char parent[200];

char getParent(char c) {

	if (parent[c] == 0)return c;
	int ret = getParent(parent[c]);
	parent[c] = ret; //더 빠른 성능을 위해서 추가 : getParent함수에서 return 될때, 탐색되는 노드의 부모를 root로 바꿔준다.
	return ret;

}

void insert(char c1, char c2) {

	int a = getParent(c1);
	int b = getParent(c2);

	if (a != b)parent[b] = a;
	// root가 같다면 아무것도 하지 않는다.
	// root가 다르다면 c2그룹이 c1그룹안에 속하게 도와준다.
	// 그룹하는 방법은 c2의 root 부모를 c1의 root로 설정한다.
}

int main() {
	
	insert('A', 'G');
	insert('H', 'C');
	insert('A', 'H');
	insert('F', 'D');
	insert('A', 'F');
	
	return 0;
}

 

맵으로 보면 이런식으로 보여진다.

 

MST (Minimum Spanning Tree)

MST란 ? 그래프에서 최소 비용으로 모든 구간을 연결한 Tree이다.

MST는 Tree이기 때문에 Cycle이 존재하지 않는다. 답이 여러개 될 수 있다.

MST를 구하는데 대표적인 알고리즘 : 크루스칼 (Kruskal)이다.

 

크루스칼 (Kruskal)

크루스칼의 시간복잡도는 O(n log n)

크루스칼 알고리즘 과정 

1. 가중치 값을 기준으로 정렬을 한다
2. Union Find 자료구조를 사용해 간선을 선택한다.

크루스칼 알고리즘 과정 상세설명

1. 그래프가 주어지면 정렬시킨다.

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
	char v1, v2;
	int val;
};

node n[8] = {
		{'A','B',6},
		{'A','C',4},
		{'A','D',5},
		{'C','B',1},
		{'C','D',3},
		{'C','E',7},
		{'E','B',3},
		{'E','D',1},
};

void sort(int len) {
	for (int i = 0; i < len; i++) {
		for (int j = i + 1; j < len; j++) {
			if (n[i].val > n[j].val) {
				swap(n[i], n[j]);
			}
		}
	}
}

int main() {
	
	int len = 8;
	sort(len);
	
	return 0;
}

2. Union-Find를 이용해서 그룹핑한다. 만약 같은 그룹인 노드를 연결해 Cycle이 발생하면 MST로 채택하지 않고 넘어간다.

int parent[200];

int getParent(int now) {

	if (parent[now] == 0)return now;
	int ret = getParent(parent[now]);
	parent[now] = ret; 
	return ret;

}

int insert(int v1, int v2) {

	int a = getParent(v1);
	int b = getParent(v2);

	if (a == b)return 0;
	parent[b] = a;
	return 1;
}

 

3. 그룹을 다 연결하면 정렬되었기 때문에 Cycle이 발생하지 않는 최소인 것들끼리 연결이 된다.

정점은 총 5개로 간선이 4(5-1)개가 되면 완성이 되는 것이다.

 

<코드 완성>

#include <iostream>
#include <algorithm>
using namespace std;

struct node {
	char v1, v2;
	int val;
};

node n[8] = {
		{'A','B',6},
		{'A','C',4},
		{'A','D',5},
		{'C','B',1},
		{'C','D',3},
		{'C','E',7},
		{'E','B',3},
		{'E','D',1},
};

int parent[200];

int getParent(int now) {

	if (parent[now] == 0)return now;
	int ret = getParent(parent[now]);
	parent[now] = ret; 
	return ret;

}

int insert(int v1, int v2) {

	int a = getParent(v1);
	int b = getParent(v2);

	if (a == b)return 0;
	parent[b] = a;
	return 1;
}


void sort(int len) {
	for (int i = 0; i < len; i++) {
		for (int j = i + 1; j < len; j++) {
			if (n[i].val > n[j].val) {
				swap(n[i], n[j]);
			}
		}
	}
}

int main() {
	
	int len = 8;
	int sum = 0;
	int cnt = 0;
	sort(len);
	for (int i = 0; i < len; i++) {
		if (insert(n[i].v1, n[i].v2) == 1) {
			sum = sum + n[i].val;
			cnt++;
		}
	}
	if (cnt == 4)cout << sum;

	return 0;
}