[그래프]Union-Find

Union-Find

Disjoint-set(서로소 집합) 자료구조를 만들기 위한 알고리즘

Disjoint-set은 교집합이 존재하지 않는 상호 배타적인 부분집합들로 나누어진 원소들에 대한 정보를 가질 수 있도록 하는 자료구조라고 정의한다.

Find : 어떤 원소가 어느 집합에 속해 있는지를 알려주는 연산
Union : 두 개의 부분 집합을 하나의 집합으로 합치는 연산. 즉, 두 개의 원소를 입력으로 주면 두 원소가 서로 다른 집합에 속할 경우 하나로 합치는 연산

예시 코드

여러 방식으로 구현할 수 있지만 널리 사용되고 있는 경로 압축(Path Compression)을 이용한 구현법으로 작성한다.

#define MAX_SIZE 100000

//index 0 is not used
int parent[MAX_SIZE + 1]; //소속한 집합의 루트값
int member[MAX_SIZE + 1]; //소속한 집합의 원소 수

int find(int n){
    if(parent[n] = n)   return n;
    return parent[n] = find(parent[n]);   //path compression
}

void union(int a, int b){
    int A(find(a));
    int b(find(b));
    if(A != B){
        parent[A] = B;
        member[B] += member[A];  //A가 B에 붙어 A에 속한 원소의 수를 더해준다.
        member[A] = 1;    //A 집합 초기화
    }
}

void init(){
    for(int i = 1; i <= MAX_SIZE; i++){
        parent[i] = i;
        member[i] = 1;
    }
}

경로 압축을 활용한 최적화

heejeong Kwon님의 블로그에 아주 친절하게 설명이 되어있다. 핵심 내용만 인용해보겠다.

최악의 상황

• 트리 구조가 완전 비대칭인 경우
• 연결 리스트 형태
• 원소의 개수가 N일 때, 트리의 높이가 N-1이므로 union과 find(x)의 시간 복잡도가 모두 O(N)이 된다.
• 배열로 구현하는 것보다 비효율적

기존의 find 연산

int find(int n){
    if(parent[n] = n)   return n;
    return    find(parent[n]);
}

최적화된 find 연산

경로 압축(Path Compression)
시간 복잡도: O(logN)

int find(int n){
    if(parent[n] = n)   return n;
    return parent[n] = find(parent[n]);   //path compression
}