Union-Find

Union-Find는 대표적인 그래프 알고리즘이다. 

각 노드들이 서로 같은 그래프에 속해있는지 확인하는 알고리즘으로 서로소 집합(Disjoint-set)이라고도 부른다.

 

 

위와 같이 노드가 존재한다고 하자.

초기에 각 노드는 본인의 값을 부모로 가진다.

노드	1	2	3	4	5	6	7	8	9	10
부모	1	2	3	4	5	6	7	8	9	10

 

Union-Find에서는 보통 부모가 작은 것으로 통일 시켜준다. 만약 위와 같이 1번 2번 노드가 연결되고, 5번과 8번 노드가 연결되면

 

노드	1	2	3	4	5	6	7	8	9	10
부모	1	1	3	4	5	6	7	5	9	10

 

위와 같이 테이블이 변경된다!

 

#include <iostream>

using namespace std;

int parent[11];

// 부모를 찾는 함수 (재귀 사용)
int get_parent(int parent[], int n) { 
	int result = 0;
	if (parent[n] == n) return n;
	return result = get_parent(parent, parent[n]);
}

// 두 노드의 부모를 합치는 함수
void union_parent(int parent[], int a, int b) {
	int p_a = get_parent(parent, a);
	int p_b = get_parent(parent, b);
	if (p_a < p_b) {
		parent[b] = a;
	}
	else {
		parent[a] = b;
	}
}

// 두 노드의 부모가 같은지 확인하는 함수
int is_Union(int parent[], int a, int b) {
	int p_a = get_parent(parent, a);
	int p_b = get_parent(parent, b);
	if (p_a == p_b) {
		return 1;
	}
	else return 0;
}

int main() {
	for (int i = 1; i <= 10; i++) {
		parent[i] = i;
	}

	union_parent(parent, 1, 2);
	union_parent(parent, 2, 3);
	union_parent(parent, 3, 4);

	union_parent(parent, 5, 6);
	union_parent(parent, 6, 7);
	union_parent(parent, 7, 8);
	union_parent(parent, 8, 9);
	union_parent(parent, 9, 10);

	//union_parent(parent, 1, 6);
	
	printf("%d", is_Union(parent, 1, 6));
}

Union-Find 알고리즘은 다른 고급 그래프 알고리즘의 베이스가 되는 중요한 알고리즘이며, 크루스칼 알고리즘에서도 Union-Find 알고리즘을 사용한다.