[Algorithm] Union-Find Algorithm

Union-Find Algorithm

- Disjoint Set을 표현할 때 사용하는 알고리즘

 

Disjoint Set

- 각 집합들에 대해 서로 공통 원소가 없는 집합 :: 서로소 집합 자료구조

• 트리 구조를 사용하면 가장 효율적으로 구현할 수 있다
• 최소 힙과 비슷하게 root를 가장 작은 값으로 설정해주면 편리하다

 

Union-Find 연산

(1) init-set(x)

- 각 node들을 본인의 번호로 초기화 

번호	1	2	3	4	5	6
root	1	2	3	4	5	6

 

(2) union(x, y)

- x가 속한 집합과 y가 속한 집합을 합친다

 

ex) (1, 3) (2, 4, 5, 6) 합치기

- 합치고, 각자 번호를 해당 tree의 root번호로 변경해준다

• 바로 위의 부모 node로 변경하는게 아니라 최종적인 부모 node로 변경해야 한다

번호	1	2	3	4	5	6
root	1	2	1	2	2	2

 

(3) find(x)

- x의 최종부모 node번호를 return해준다

번호	1	2	3	4	5	6
root	1	2	1	2	2	2

---

static int [] parent;

static void init_set(int x){
    // 1 ~ x까지의 번호를 본인의 번호로 초기화
    // (x+1)크기 만큼의 배열 parent에 초기화

    parent = new int[x+1];

    for(int i=1; i<=x; i++)
        parent[i] = i;
}

static void union(int x, int y){
    x = find(x);
    y = find(y);
    // 각각 본인의 부모 노드로 갱신

    if(x == y)
        return;
    // x, y 각각의 부모 노드가 동일하다면 굳이 union 할 필요가 없다
    else{
        if(x < y)
            parent[y] = x;
        else
            parent[x] = y;
    }
    // Tree 구조를 최소힙 구조로 구현함으로써 무조건 부모 노드를 작게 구현해준다
}

static int find(int x){
    if(parent[x] == x)
        return x;
    // x가 최종 부모 node 그 자체면 그냥 해당 x값을 return

    return parent[x] = find(parent[x]);
    // 최종 부모 node를 찾는 과정에서 경로 최적화
}

• Kruskal Algorithm에서 Cycle을 판별할 경우 사용하는 유용한 알고리즘이다