Union-Find 알고리즘

Union-Find 알고리즘

Kruskal MST에서 사용되는 알고리즘 중 "Union-Find 알고리즘"이 존재한다.

이를 먼저 알아야 Kruskal MST를 구현할 수 있으므로 이 알고리즘부터 알아보자.

 

◎ Union-Find 알고리즘이란?

Union-Find는 Disjoint Set을 만들 때 사용하는 알고리즘이다.

 

Disjoint는 "분리된, 별개의"라는 뜻을 가지고 있다.

Disjoint Set이란 "분리된 집합"이라는 의미로 교집합이 존재하지 않는 부분집합들을 조작 및 저장하는 자료구조이다.

모든 부분 집합 사이에 교집합이 없는 상호 배타적인 부분 집합들로 이뤄진 자료구조라 할 수 있다.

 

◎ Union-Find 연산

• make-set(x)
  • Set을 초기화하는 함수
  • x 자체가 하나의 부분 집합이 되도록 자료구조를 초기화 함
• union(x,y)
  • x가 속한 부분집합과 y가 속한 부분집합을 통합시키는 함수
  • x가 속한 부분 집합의 Root 값과 y가 속한 부분 집합의 Root 값을 비교함으로써 결합 이전 두 개 집합이 같은 집합에 속해 있는지를 확인한다.
• find(x)
  • x가 속한 집합의 Root 값 찾기

---

기본적인 Union-Find 구현 방법

class Union_Find{
	int[] parent;

	public Union_Find(int nodeSize){
		parent = new int[nodeSize];
		for(int i =0;i<nodeSize;i++) parent[i] = i; // make-Set 함수
	}

	int find(int x){
		if(parent[x] == x) return x; // 현재 노드와 Parent Node가 같다면 자기 자신이 Root Node

		return find(parent[x]); // 현재 노드의 부모 Node의 Root Node를 찾음
	}

	void union(int x, int y){
		// 1개 부분 집합의 Root를 다른 부분 집합 Root의 자식 Node로 만듦
		x = find(x);
		y = find(y);

		parent[y] = x;
	}
}

---

최적화된 Union-Find 알고리즘

◎ 기본적인 Union-Find 알고리즘의 문제점

출처 : https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html

위에서 구현한 기본적인 Union-Find 알고리즘의 경우 트리 구조가 완전 비대칭, 즉 위 사진 처럼 일렬로 구성될 경우 최악의 상황으로 간주할 수 있다.

 

이 경우 트리의 높이가 최대가 되므로 Union과 Find 함수 모두 O(N)의 시간 복잡도를 가진다.

이는 배열로 구현하는 것보다 비효율적인 시간 복잡도이고, 이런 문제를 해결하기 위해 몇 가지 방법을 사용하여 Union-Find 알고리즘을 최적화한다.

 

◎ 효율을 위한 추가 알고리즘

• 경로 압축(Path Cmopression) : find(x) 과정에서 거치는 모든 Node의 부모 Node를 Tree의 Root Node로 재지정해줌
• Union-By-Rank : Root Node에 Tree의 높이를 저장하여 항상 높이가 더 낮은 트리의 Root Node를 높이가 더 높은 트리의 자식으로 넣음

 

◎ 최적화된 Union-Find 알고리즘

class Union_Find{

	int[] parent;
	int[] rank; // 트리의 높이를 저장할 배열

	public Union_Find(int nodeSize){
		parent = new int[nodeSize];
		rank = new int[nodeSize];
		for(int i =0;i<nodeSize;i++) {
			parent[i] = i;
			rank[i] = 0; // 트리 높이 초기화
		}
	}

	int find(int x){ // Path Compression
		if(parent[x] == x) return x; // 현재 노드와 Parent Node가 같다면 자기 자신이 Root Node

		parent[x] = find(parent[x]); // find하면서 만난 모든 값의 부모 노드를 Root로 만듦.
		return parent[x];
	}

	void union(int x, int y){
		// 1개 부분 집합의 Root를 다른 부분 집합의 Root의 자식 Node로 만듦
		x = find(x);
		y = find(y);

		if(x==y) return; // Root가 같으므로 동일한 Tree임. 합치지 X

		// Union-By-Rank
		if(rank[x] < rank[y]){
			parent[x] = y; // x의 Rank가 낮으므로 y의 아래로 들어감
		}
		else{
			parent[y] = x; // y의 Rank가 낮으므로 x의 아래로 들어감
			
			if(rank[x]==rank[y]) rank[x]++; // 높이가 같을 경우 1층이 증가되어야 함
		}
	}
}