[Algorithm] Union-Find의 개념과 구현

Union-Find의 개념

• 서로 중복되지 않는 부분 집합 (Disjoint Set)을 표현할 때 사용하는 자료구조
• 초기화 / 합치기 (Union) / 찾기 (Find) 세 가지 연산을 사용한다
• 최소 스패닝 트리를 구현하는 크루스칼 알고리즘에 사용되며, 사이클을 만들지 않고 모든 노드를 방문할 수 있다

Union-Find의 구현

• 초기화 : N 개의 원소가 각각의 집합에 포함되어 있도록 초기화한다 -> 각각을 유일한 원소로 가지는 집합 생성
• Union (합치기) : 두 원소 a, b 가 각각 속한 두 집합을 하나로 합친다 -> 두 개의 집합을 하나로 연결하는 역할
• Find (찾기) : 원소 a 가 주어질 때, 이 원소가 속한 집합을 루트노드를 반환한다 -> a가 어느 집합에 속해있는지 찾는 역할 

//초기화
for(int i=1; i<=V; i++) 
	parent[i] = i;
     
// Find 연산 : a가 속한 트리의 루트 노드를 반환한다.
int find(int a) {
	// 루트 노드는 부모 노드 번호로 자기 자신을 가진다.
	if(a==parent[a]) return a;
	// 각 노드의 부모를 찾아 올라간다.
   	else parent[a] = find(parent[a]);
	return parent[a];
}

// Union 연산 : a와 b가 속한 트리를 하나로 합친다.
void union(int a, int b) {
	// 각 원소가 속한 트리의 루트노드를 찾는다.
	int rootA = find(a);
	int rootB = find(b);

	// 루트가 동일하지 않다면 서로 다른 두개의 트리를 합친다.
	if(rootA!=rootB) parent[rootA] = b;
	// 같은 트리에 속할 경우 함수를 종료한다.
	else return;
}

 

 

 

🕊참고자료

[알고리즘] Union-Find 알고리즘 - Heee's Development Blog

 

[자료구조]Union-Find: Disjoint Set의 표현