Union-Find $O(N)$,$O(logN)$

Union-Find 알고리즘은 서로소 집합(Disjoint-Set) 알고리즘 이라고도 한다. 어떤 노드들이 서로 같은 그래프에 속해 있는지(두 노드까지의 경로가 존재하는지) 판별하기 위해서 사용되며 그래프를 다룰 때 중요한 알고리즘 중 하나이다.

 

 Union-Find 알고리즘은 자신의 부모 노드를 불러오는 알고리즘, 두 노드를 이어주는 알고리즘(Union), 두 노드가 같은 그래프에 있는지 확인하는 알고리즘(Find)으로 구성된다. 이 알고리즘들은 각 노드의 부모 노드를 기준으로 구현하고 보통 parent라는 일차원 배열에 부모 노드들을 저장한다.

 

예시)

간선이 없는 초기의 그래프

노드	1	2	3	4	5
부모 노드	1	2	3	4	5

 

 먼저 초기에 아무 간선도 없을 때에는 각 노드의 부모 노드를 자기 자신으로 지정해둔다.

 

$O(N)$ 알고리즘

1. Union

간선을 추가한 그래프

예시로 1번 노드와 5번 노드, 2번 노드와 5번 노드를 차례대로 이었다고 생각해보자. 

 

1) 1번 노드와 5번 노드

1번 노드와 5번 노드가 연결되었으므로 부모 노드를 같게 만들어줘야한다. 이때 부모 노드는 두 노드 중 부모 노드의 번호가 더 작은 쪽으로 통일시킨다. 여기서는 5번 노드의 부모 노드를 1번 노드의 부모 노드인 1번 노드로 바꿔준다.

노드	1	2	3	4	5
부모 노드	1	2	3	4	1

 

2) 2번 노드와 5번 노드

이제 2번 노드와 5번 노드의 부모 노드도 하나로 통일해야한다. 이때 5번 노드의 부모 노드는 1이고, 2번 노드는 2이므로 더 작은 1로 통일시킨다.

노드	1	2	3	4	5
부모 노드	1	1	3	4	1

 

2. Find

 

1) 1번 노드와 2번 노드

 두 노드가 같은 그래프 상에 있는 지 판단하려면 부모 노드가 같은 지 확인하면 된다. 이때 두 노드의 부모 노드는 모두 1번 노드로 같으므로 두 노드는 같은 그래프 상에 있다.

 

2) 3번 노드와 5번 노드

 3번 노드의 부모 노드는 3이고, 5번 노드의 부모 노드는 1이므로 서로 다른 그래프 상에 있다.

 

 

구현

1. 어떤 노드의 부모 노드 불러오기

int getParent(int parent[],int x)
{
    if(parent[x] == x) return x;
    return parent[x] = getParent(parent,parent[x]);
}

  x번 노드의 부모 노드를 불러오고 싶으면 재귀함수를 이용해주면 된다. 이 재귀함수의 결과로 x번 노드와 연결되어있는 가장 번호가 작은 노드가 반환되고 이 노드가 부모 노드이다. 이때 최대 $N$번 시행하므로 시간복잡도는 $O(N)$이 된다.

 

2. 두 노드를 이어주기(Union)

void unionParent(int parent[], int x, int y)
{
    x = getParent(parent, x);
    y = getParent(parent, y);
    if(x>y) parent[x] = y;
    else parent[y] = x;
}

 x와 y를 연결해주는 것은 두 노드의 부모 노드의 번호 중 더 작은 것으로 부모 노드를 통일시키는 과정이다. 이를 그대로 구현하면 된다. getparent를 사용하므로 마찬가지로 $O(N)$이다.

 

3. 두 노드가 같은 그래프 상에 있는지 확인하기(Find)

int findParent(int parent[], int x, int y)
{
    x = getParent(parent, x);
    y = getParent(parent, y);
    if(x==y)return true;
    return false;
}

 두 부모 노드가 같다면 true, 아니라면 false를 반환해주면 된다. 이 경우도 $O(N)$이다.

 

 

$O(logN)$알고리즘

  $O(N)$알고리즘은 어떤 문제에선 매우 느릴 수 있기 때문에 개선할 필요가 있다. Union by rank와 Path Compression(경로 압축)을 통해  $O(logN)$까지 개선할 수 있다.

 

1) Union by rank

 먼저 union by rank는 rank(트리의 높이, 크기 등..)를 기준으로 Union을 수행하는 방법이다. 항상 rank가 높은 노드를 parent 노드로 지정한다.

 이렇게 하면 서로 다른 트리를 합칠 때 합쳐진 트리의 높이가 이전 트리의 높이중 최대이거나 최대 높이에서 + 1까지밖에 되지 않으므로 기존에 비해 훨씬 효율적이다.

 

구현

const int nMAX = 1000000;
int n,m,parent[nMAX+1],rank[nMAX+1];

void init(){ //초기화
    for(int i=0;i<=n;i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}
void unionparent(int a, int b){
    a = getparent(a);
    b = getparent(b);
    if(a==b) return;
    if(rank[a] < rank[b]){
        parent[a] = b;
    }
    else{
        parent[b] = a;
        if(rank[a] == rank[b]) rank[a] ++;
    }
}

 

2) Path Compression

getparent연산을 할 때마다 parent를 업데이트 해주며 그래프를 평평하게 만드는 방법이다. 따라서 다음번에 getparent를 수행할 때 부모노드가 parent 배열에 바로 저장되어있으므로 $O(1)$이 걸린다.

 

구현

int getparent(int a){
    if(parent[a] == a) return a;
    return parent[a] = getparent(parent[a]);
}