[Algorithm] Union-Find

 

최소 신장 트리를 표현하기 위해 사용되는 알고리즘은 크루스칼 알고리즘, 프림 알고리즘이 존재합니다.

 이 알고리즘을 구현하는 과정에서 Union-Find 자료구조가 사용됩니다. 특히, 사이클을 판별하는 과정에서 서로소 집합을 활용하여 사이클을 판별할 수있습니다.

---

• 서로소 집합을 표현하기 위해 Union-Find 자료구조를 사용합니다.  
  • 서로소 집합 : 공통 원소가 없는 두 집합입니다. {1}와 {2,3,4}는 서로 공통 원소가 없으므로 서로소 집합이라고 할 수 있습니다.
• Union Find의 연산의 종류
  • makeSet(x) : 자기 자신의 원소 번호 자신이 속해있는 집합으로 초기화하며, 크기가 1인 서로소 집합 생성하게 됩니다.
  • find(x) : x가 속한 집합의 부모(대표가 되는 값)을 반환합니다. 
  • union(x,y) : x집합과 y집합의 루트 노드(부모)가 다른지 판단하고, 다르다면 Union 연산으로 합친다.

 

• 그림을 통해 Union Find 연산에 대해  한번 더 설명드리겠습니다.

 

1. makeset 연산 수행 시 다음과 같이 구성됩니다. 0은 0 자신을 루트노드로 가리킵니다.

makeSet(x) 을 수행 시 다음 그림과 같이 됩니다.

  

2. Union(0,1) : 0번의 루트노드는 1번이 됩니다.

 

---

1. makeSet(x) 구현 : 아래 코드와 같이 parents[i]=i를 통해 자기 자신을 가르키게 합니다. 즉, 루트노드가 자기 자신이 됩니다.

 

private static void make_set(int n) {
	parents = new int[n+1];
		
	for (int i = 1; i <= n; i++) {
		parents[i] = i;
	}
}

 

 

2. find(x) 구현 : 나의 루트노드를 찾을때까지 재귀를 통해 반복하게 됩니다. 

private static int find(int a) {//a의 대표자 찾기
	if(parents[a] == a) {//나의 부모가 곧 나인 경우(내가 대표자)
		return a;
	}
		
	//우리의 대표자를 나의 부모로 바꾼다. : path compression
	return parents[a] = find(parents[a]);
}

 

 

3. union(x,y) 구현 : 사이클을 형성하게 되면 false를 리턴하며, union이 성공하게 되면 true를 리턴합니다.

private static boolean union(int a, int b) {//리턴값 : true=>union 성공
	int aRoot = find(a);
	int bRoot = find(b);
		 
	if(aRoot == bRoot) return false;
		 
	parents[bRoot] = aRoot;
	return true;
}