Union Find

Union Find 란?

: Data structure that keeps track of elements which are split into one or more disjoint sets

위키백과의 설명을 빌리자면, Union Find는 상호 배타적으로 이루어진 집합을 효율적으로 표현하기 위해 만들어진

자료 구조를 의미합니다. 

 

주요 기능 : Find , Union

Find Operation (어떤 set에 속해있는지 판별)

: To find which component a particular element belongs to find the root of that component by following the parent nodes until a slef loop is reached(a node who's parent is itself)

 

Union Operation (서로 다른 set를 병합)

: To unify two elements find which are the root nodes of each component and if the root nodes are different make one of the root nodes be the parent of the other

 

아래 코드를 보면 각 기능이 어떤 역할을 하는지 더 잘 이해할 수 있습니다

ArrayList list = []

    Function additem():
        list.append([list.length, 0])

    Function find(index):
        if list[index][0] == index:
            return index     #최상위 노드 값 반환
        else:
            return find(list[index][0])

    Function union(a, b):
        roota = self.find(a)
        rootb = self.find(b)
        list[roota][0] = list[rootb][0]
        
        # 2개의 집합을 하나의 root로 결합 (합집합 개념)

(Code source: https://namu.wiki/w/Union%20Find)

 

Union Find의 활용처

• Kruskal's minimum spanning tree algorithm
• Grid percolation
• Network connectivity
• Least common ancestor in trees
• Image Processing

 

Complexity

Construction	O(n)
Union	a(n)
Find	a(n)
Get component size	a(n)
Check if connected	a(n)
Count components	O(1)

*a(n)은 Amortized constant time을 의미합니다

 

 

▷ Kruskal's minimum spanning tree algorithm

1. Sort edges by ascending edge weight

2. Walk through the sorted edges and look at the two nodes the edge belongs to, if the nodes are already unified we don't include this edge, otherwise include it and unify the nodes

3. The algorithm terminates when every edge has been processed or all the vertices has been unified

 

 

Union Find Path Compression

 

 

일반적으로 E 노드의 ROOT를 찾기 위해서는 D-C-B-A-F 이렇게 가야하고, L 도 마찬가지 이지만

Path compression 은 오히려 각 노드가 ROOT노드를 가리키도록 해서 비효율성을 줄입니다

 

 

 

Union Find 관련 코딩 문제는 아래를 참고해주세요

↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

https://psygo22.tistory.com/65?category=1023721 

Leetcode 200. Number of Islands (Union Find)

 

 

 

** 본 글은 공부를 위해 아래 YouTube 내용을 바탕으로 작성된 글입니다

https://www.youtube.com/watch?v=RBSGKlAvoiM&t=8916s