Union-Find (유니온 파인드)

Union Find알고리즘은 Heap과같이 기준을 바탕으로 우선순위를 두고 Tree형태로 데이터를 관리할 때 자신과 연결된 노드들의 집합에 한해서 우선순위가 가장높은 부모노드를 O(1)로 찾을 수 있게하는 알고리즘이다.

 

1. 초기화

특정한 배열에 대하여 처음 초기화를 할 때는 모든 노드가 서로 연결되어있지 않으므로 자기 자신이 루트 노드가 된다.

때문에

자신(index)의 루트 노드를 나타내는 배열 tree가 존재한다면

tree[5] = {0, 1, 2, 3, 4}

와같이 자기자신이 루트임을 나타내는 배열 형태를 볼 수 있다.

 

 

2. find

Find함수는 말그대로 특정 인덱스에 대하여 연결된 노드 중 루트 노드가 무엇인지 찾아가는 function이다.

여러 개의 노드들과 연결되어있는 경우를 커버하기 위해 재귀를 통해서 find(index)를 재귀함수로 구현한다.

재귀함수를 통해 최종적으로 해당 노드와 연결된 그룹 중 가장 상위 노드의 index값을 알 수 있다.

 

 

3. Union

union구조는 서로 연결되어있지 않은 노드들을 연결해주는 function이다.

이 떄 구현에 따라 min, max, 처음 오는 파라미터 등 parent가 되는 기준을 적용시켜 union작업을 진행한다.

 

먼저 합치고자하는 각각의 노드가 어느 그룹에 속해져있을 수 있기 때문에 각각 노드들의 최상위 index값을 찾아준다.

그리고 찾은 index값에 대하여 tree[] 배열에 업데이트를 해줌으로써 노드간의 연결은 종료된다.

 

 

4. 구현

#include <iostream> using namespace std; const int32_t MAX_SIZE = 32; int32_t tree[MAX_SIZE]; void inits(void) {     for (int32_t i=0; i<MAX_SIZE; i++) {         tree[i] = i;     } } int32_t find(int32_t i) {     if (tree[i] == i) {         return i;     }     int32_t y = find(tree[i]);     tree[i] = y;     return y; } void unions(int32_t parent, int32_t child) {     int32_t x = find(parent);     int32_t y = find(child);     tree[find(y)] = x; } int32_t main (void) {     inits();     cout<<find(5)<<endl;     unions(2,5);     cout<<find(5)<<endl;     unions(1,2);     cout<<find(5)<<endl;     return 0; }