[고급 자료구조] Tree: Union-Find

1. Union-Find

• 서로소 부분 집합들로 나눠진 원소들을 관리하는 자료구조 입니다.

 

서로소 집합 (disjoint)

상호 배타 집합

• 공통 원소가 없는 두 집합입니다. 
• 두 집합 A와 B가 있을 때 교집합이 공집합이라면, A와 B는 서로소 관계에 있습니다.

 

2. 연산

Make-Set

• 하나의 원소만을 가지는 집합을 만듭니다.

 

Union

• 두 대표 원소의 집합들을 하나로 합칩니다.
• 두 대표 원소를 입력 인자로 사용합니다.

 

Find

• 주어진 원소의 대표원소를 반환합니다.

 

3. 구현

Circularly Doubly Linked List

Head

• 대표 원소

 

연산

• find: head 반환
• union: 두 링크드리스트 병합

 

시간복잡도

•  O(N)

 

연산 속도가 느려 tree 방식이 고안되었습니다.

 

Tree

노드

• root: 대표 원소
• link: 자신의 부모

 

연산

• find(x)
  
  • x부터 link를 끝까지 타고가서, 루트노드 방문 및 반환합니다.
  • Path Compression: 특정 노드에서 루트까지 방문하면서 재귀적으로 방문한 노드들의 루트 노드를 갱신합니다.
• union(x, y)
  • 주어진 대표원소의 두 tree들을 합칩니다.
  • Union By Rank: 작은 높이 tree를 큰 높이 tree의 자식으로 추가합니다. (최종 트리의 깊이 최소화)

 

시간복잡도

• $O(h)$
  • $O(a(V))$ : 애커만 함수의 역함수. (거의 상수시간)

 

코드

public class UnionFind {
    private int[] root;
    private int[] rank;

    public UnionFind(int size) {
        root = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            root[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (x == root[x]) return x;

        return root[x] = find(root[x]);
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX == rootY) return;

        if (rank[rootX] > rank[rootY]) root[rootY] = rootX;
        else root[rootX] = rootY;

        if (rank[rootX] == rank[rootY]) rank[rootY]++;
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

 

 

4. 응용

연결 요소 추적 (무향 그래프)

연결 요소

• 그래프 내에서 서로 연결되어 있는 꼭짓점들의 집합

 

추적

• 연결 요소를 추적하여 전체 원소에 접근할 수 있습니다.

 

사이클 감지 (무향 그래프)

사이클

HDGH

• 마지막 꼭짓점이 다시 시작점으로 돌아오는 경로를 뜻합니다.
• 최소 3개 이상의 유일한 꼭짓점들로 연결되어 있습니다.

 

사이클 존재 여부

• 두 꼭짓점을 연결할 때, 이미 존재하는 경로를 통해 도달할 수 있는지 여부

 

Kruskal Algorithm

• 최소 신장 트리를 찾는데 활용됩니다.

 

출처

• Wiki - 서로소 집합 자료 구조
• Wiki - 순환 (그래프 이론)