Union Find

 

Disjoint Set

서로 중복되지 않는 부분집합만으로 이뤄진 자료구조 = 서로소 집합 자료구조

 

Union-Find

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

2가지 자료구조로 구현할 수 있다. (Array, Tree)

 

When to use?

(1) Detect cycle in a undirected graph
(2) Check relationship between sets
(3) Kruskal Algrotihm

* condition : The graph doesn't contain any self-loops

 

Key

For each edge, make subsets using both the vertices of the edge

If both the vertices are in the same subset ==> Cycle exists

 

Graph 예시

 

총 10개의 노드가 있고 위 그림과같이 edge로 연결되어있다고 가정하면

[원칙]

• 각 노드는 모두 부모 노드를 갖는다. (초기값 자기 자신)
• edge로 연결해서 부분 집합을 형성 시 해당 집합의 가장 작은 노드 번호가 root 노드가 된다.

 

따라서 1과 3이 각각의 부분집합의 Root 노드가 되고

각각의 부모가 같은 노드끼리는 같은 집합에 속해있다고 해석할 수 있다.

 

 

구현측면에서는 총 3가지 기능이 필요한데.

Union-Find 알고리즘의 핵심은 두 노드의 부모를 비교하여 두 부분집합의 관계를 파악하는데에 있다.

ex) Krukcal 알고리즘에서 새 노드를 연결하려 할 때 이미 자신이 연결된 노드인지 확인 하려는 경우

 

Union Find 알고리즘의 Module

1. 부모 노드 초기화 (자기 자신값)
2. 부모 노드 탐색
3. 자신이 속한 Group 확인
4. 부모 노드 결합(Union)

 

 

배열을 통한 Union-Find Algorithm 구현

① 설계 & 분석

모듈별 함수 정의

    #include <stdio.h>
    
    // 초기화 함수
    void initParent(int nodeNum, int parent[]) {   
        for(int i = 1 ; i <= nodeNum; i++) {
            parent[i] = i;
        }
    } 
    // 부모 노드 찾는 함수
    int getParent(int i, int parent[]) {
        if (i == parent[i]) return parent[i];
        else return parent[i] = getParent(parent[i], parent);
     } 
     
    // 노드간 서로 같은 집합인지 체크하는 함수
    int unionCheck(int a, int b, int parent[])
    {
        a = getParent(a, parent);
       b = getParent(b, parent);
        
        if (a == b) return 1;
        else return 0;
     } 
    
    // 노드를 서로 결합하는 함수
    void unionConnect(int a, int b, int parent[]) 
    {
        a = getParent(a, parent);
        b = getParent(b, parent);
        if (a < b) parent[b] = parent[a];
        else parent[a] = parent[b];
   }

Main.c

 
#include <stdio.h>
#include "union-Find.c"
 
int main(void)
{
    int nodeNum = 0;
    int i = 1;
    int parent[100];
    
    printf("노드의 개수를 입력하세요 : "); // 처리 1 
    scanf("%d", &nodeNum);
    printf("\n");
    
    initParent(nodeNum, parent); //처리2    
    /*처리3*/ 
    unionConnect(1, 2, parent);  
    unionConnect(2, 5, parent);
    unionConnect(3, 7, parent);
    unionConnect(7, 9, parent);
    
    /*처리4 */ 
    printf("1과 5의 연결여부? %d\n", unionCheck(1, 5, parent));
    printf("1과 3의 연결여부? %d\n", unionCheck(1, 3, parent));
    
    
    /*처리 5*/ 
    printf("\n\n");
    printf("======현재 각 노드의 parent확인======\n");
    for(i = 1; i <= nodeNum; i++)
    {
        printf("%d의 부모노드 : %d\n", i, parent[i]);
    }
    
    return 0;
}

연결 상태를 배열로 표현하면

i: node Number, parent[i]: 부모노드

i	1	2	3	4	5	6	7	8	9	10
P[i]	1	1	3	4	1	6	3	8	3	10

 

실행결과

윗 노드-부모노드별 테이블 정보와 같은 결과를 얻는다.

 

 

만약 5번노드와 7번 노드를 연결한다면?

 

 

5번 노드와 7을 연결하면

테이블 정보는 어떻게 될까?

 

unionConnect(5, 7, parent);  코드를 추가하여 확인해보겠다.

 

앞에 원칙상 노드 7, 3, 9도 모두 부모노드 1을 가져서 다음과 같은 테이블 정보로 update되야한다.

i	1	2	3	4	5	6	7	8	9	10
P[i]	1	1	1	4	1	6	1	8	1	10

하지만 막상 실행해본다면?

1과 3번이 한 그래프 (부분집합)을 형성했찌만 7과 9의 부모노드가 1이 아닌 3이다.

오로지 3번의 부모노드만 1로 갱신되고 나머지는 그대로 3이다!

이는 서로 노드가 Disjoint Set인지 아닌지를 검사하는데는 무관하지만 의문을 가질 수도 있는 결과다.

[실행 결과]

i	1	2	3	4	5	6	7	8	9	10
P[i]	1	1	1	4	1	6	3	8	3	10

 

Q. 왜 3만 1로 갱신되는지??

 

A. 이는 결합함수'unionConnect'를 살펴보면 된다.

내부적으로 getParent를 수행하는데

unionConnect(5,7) 수행시

i	1	2	3	4	5	6	7	8	9	10
P[i]	1	1	1	4	1	6	3	8	3	10

5와 7의 부모 getParent가 재귀함수로 정의되어 있으므로

5의 부모 -> 1

7의 부모 -> 3 -> 3의 부모 ->3

부모 값 1 vs 3 => 1의 승리

👉 '3' 노드에만(Representative node == Root node) 1이라는 부모노드의 값이 Update된다.

---

트리를 통한 Union-Find 알고리즘 구현

배열로 구현할 경우 최악의 경우 union - find의 시간복잡도가 O(N)이 된다.

이를 O(Log n)으로 줄일 수 있는 해법이 바로 Union by rank 이다.

rank는 원래 높이(hegiht)로 표현되었으나 수 있지만 Path Compression과 같이 사용할 경우 실제 트리 높이와 달라지기 때문에 선호되는 이름이다.

 

Union by rank

rank가 높은 집합에 낮은 집합을 합친다(Union). (높이의 증가를 최소화하는 방식)
rank가 같은 집합끼리 union시 일단 대치하고 대치한 쪽의 rank를 +1한다. 

※ rank에 변화가 있는 구간은 rank가 같은 집합끼리 합칠 때 밖에 없다.

 

Union 시 rank는 모든 노드에 대해 업데이트 할 필요 없고 오로지 'root'만 업데이트 해주면 된다.

union-find 에서 모든 기준은 root (representative nodoe)이다. 따라서 root만 업데이트하면 rank는 알아서 업데이트된다. => 해당 root의 rank 업데이트시 속한 모든 노드의 rank가 업데이트된다.

 

 

Union By Rank + Path Compression (Optimized Version)

---

Reference

Union-Find Algorithm | Set 2 (Union By Rank and Path Compression) - GeeksforGeeks