Union-Find 알고리즘

Union-Find

 - Disjoint Set( 서로소 집합 자료구조 ) 을 표현하기 위해 사용하는 알고리즘

 - 아래 3가지 연산을 이용하여 Disjoint Set 을 표현한다.

 

Union-Find 연산

1. make-set(x)

• 초기화, 인자 x 를 원소로 가지는 새로운 집합을 만든다.

2. union(x, y)

• 합연산, x가 속한 집합과 y 가 속한 집합을 합한다.

3. find(x)

• 탐색. x가 속한 집합의 대표 값(루트 값) 을 찾는다. x가 어떤 집합에 속해있는지 확인하는 연산

Union-Find 의 기본적인 구현

/*make-set(x)*/
int parent[MAX_SIZE];

for(int i=0; i<MAX_SIZE; i++){
	parent[i] = i;
}

/* find(x) : x의 최상위 부모 노드(루트 노드) 반환 */
int find(int x){

	// 루트 노드인 경우
	if(parent[x] == x){
    	return x;
	}
    
    return find(parent[x]);
}

/* union(x,y) : y를 x 집합에 포함시킨다 */
void union(int x, int y){

	parent[find(y)] = find(x);

	return;
}

 

References

gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html