Union-find 알고리즘

 Union-find란?

 서로소 집합 (Disjoint-set : 서로소 또는 상호배타 집합, 서로 중복 포함된 원소가 없는 집합) 을 표현할 때 사용하는 알고리즘

 

 서로소 집합 연산

•  Make-Set(x) : x를 유일한 원소로 하는 집합 만드는 연산
• Find-Set(x) : x의 대표자 (집합에 속한 하나의 특정 멤버) 값을 반환하는 연산
• Union(x, y) : x집합을 y집합에 합치는 연산

 트리 표현

  - 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자 

Union-Find 기본 연산

static void makeSet() { // 크기가 1인 단위집합을 만든다.
	for (int i=1;i<=N;i++) {
		roots[i] = i;
	}
}
	
static int findSet(int x) {
	if (roots[x]==x) return x; // 내 자신이 대표자라면 return x
		
	return findSet(roots[a]); 
}
	
static void union(int x, int y) {
	int xRoot = findSet(x);
	int yRoot = findSet(y);
	if (xRoot==yRoot) return; // 같은 집합
		
	roots[yRoot] = xRoot;
}

 

 연산 효율 높이기

최악의 경우

최악의 경우는 트리 구조가 완전한 비대칭인 경우로 원소의 개수가 N일 때 시간 복잡도가 O(N)이 되므로 배열 구현보다 비효율적

 

연산 효율 높이는 방법

• Rank
• Path Competition

 Rank

 - 트리 높이를 저장한 다음 연산 시 트리 높이가 낮은 트리를 높은 트리 밑에 넣음으로써 트리의 높이가 커지는 상황 방지

static void makeSet() { // 크기가 1인 단위집합을 만든다.
	for (int i=1;i<=N;i++) {
		roots[i] = i;
        rank[i] = 0;
	}
}
	
static int findSet(int x) {
	if (roots[x]==x) return x; // 내 자신이 대표자라면 return x
		
	return findSet(roots[a]); 
}
	
static void union(int x, int y) {
	int xRoot = findSet(x);
	int yRoot = findSet(y);
	if (xRoot==yRoot) return; // 같은 집합
	
    if (rank[xRoot]<rank[yRoot]) rank[xRoot] = yRoot;
    else rank[yRoot] = rank[xRoot];
    
    if (rank[xRoot]==rank[yRoot]) rank[xRoot]++;
}

 

 Path Competition

 - findSet을 행하는 과정에서 만나는 모든 노드들이 루트를 가리키도록 변경 ( 경로 압축 )

static void makeSet() { // 크기가 1인 단위집합을 만든다.
	for (int i=1;i<=N;i++) {
		roots[i] = i;
	}
}
	
static int findSet(int x) {
	if (roots[x]==x) return x; // 내 자신이 대표자라면 return x
		
	return roots[a] = findSet(roots[a]); // 루트 = 내 부모
}
	
static void union(int x, int y) {
	int xRoot = findSet(x);
	int yRoot = findSet(y);
	if (xRoot==yRoot) return; // 같은 집합
		
	roots[yRoot] = xRoot;
}