Union Find (합집합, 탐색) 소개

유니온 파인드란?

서로소 집합으로 나뉘어진 원소의 집합을 추적하기 위한 자료 구조이다.
여러 노드 중 두개의 노드를 선택할 때, 두 노드가 같은 그래프에 있는지 판별하는 알고리즘.
Disjoint Set라고도 불리기도 한다.
Disjoint-set is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets.

e1, e2 are in Set1 and e3, e4, and e5 are in Set2 .

병합 찾기 집합(Merge Find Set)이라고도 불린다.
하나 이상의 disjoint sets으로 쪼개진 elements를 찾아다니는것.

union(e1, e2) => link 'e1' and 'e2' to the same subset
find(e) => return the subset's root for 'e'

위의 그림에서 e2와 e3를 union 한다면? ( union(e2,e3) )

Union Find 예

노드 1과 2가 같은 트리에 있는지 확인하고싶다.

가장 빠른 방법은 lowest common ancestor인 5를 찾는 것이다.

노드 1과 4가 같은 트리에 있는지 알고싶다면?

lowest common ancestor를 찾아려고 하지만 찾지못한다. => 다른 트리임을 의미한다.

find(e1)가 find(e2)와 같으면, e1과 e2가 같은 집합에 있음을 의미한다.
이것은 특히 그래프 알고리즘의 경우, 두 노드가 서로 연결되는지 여부를 테스트해야 하는 디조인 의 유용한 특성이다.

언제 Union Find는 사용되는가?

Kruskal's minimum spanning tree 알고리즘
Grid percolation
네트워크 connectivity
Least common ancestor in trees
Image processing

복잡성

Construction O(n)
Union ∝(n) (amortized complexity)
Find ∝(n)
Get component size ∝(n)
Check if connected ∝(n)
Count components O(n)

유니온 만들기

먼저 bijection(a mapping)을 만들어야 함.

    def find_parent(parent,i): 
        if parent[i] == -1: 
            return i 
        if parent[i]!= -1: 
             return find_parent(parent,parent[i]) 
  
    def union(self,parent,x,y): 
        x_set = find_parent(parent, x) 
        y_set = find_parent(parent, y) 
        parent[x_set] = y_set 
  
    def isCyclic(self): 
          
        parent = [-1]*(V) 
        for i in graph: 
            for j in graph[i]: 
                x = find_parent(parent, i)  
                y = find_parent(parent, j) 
                if x == y: 
                    return True
                union(parent,x,y)

카쿤 개발자