정의

• 노드를 합치고, 부모 노드를 찾아 서로소 집합을 찾아내는 알고리즘
• 트리 구조를 활용

특징

• Union-find 알고리즘은 두 가지의 함수로 이루어진다
• Find : 두 노드의 부모 노드를 확인하여 같은 집합에 속하는 지를 확인
• Union : 두 부분집합이 같은 집합에 속하는 경우, 하나의 부분집합으로 합침. 일반적으로 값이 더 작은 족을 부모노드로 하여 합침 두 원소의 부모 노드를 찾고, 번호가 큰 노드가 번호가 작은 노드의 부모를 가리키도록 함
• 특히 무방향 그래프 내에 사이클이 존재하는 지 확인할 때 유용하게 쓰임(유향 그래프의 경우 dfs 이용)
• Find 함수 부분을 경로 압축(Path Compression)을 통해 리팩토링 시 시간 복잡도가 감소

원리

https://www.geeksforgeeks.org

그래프의 간선정보를 순회하면서,

• 만약 a와 b 두 노드가 연결되어 있고, 같은 부모 노드를 가리킨 경우, 사이클이 존재한다고 판단
• 그렇지 않은 경우, 두 부분집합을 합치기 위한 union 함수를 실행.

간선 0-1:

⇒ 0과 1을 정점으로 하는 부분집합을 찾는다

⇒ 0과 1은 각각 0과 1 부분집합에 속한다.

⇒ 두 부분집합은 다른 부분집합이므로, union을 수행하여 부분집합을 합친다.

⇒ 1번 노드를 0번 노드의 부모로 만든다. (0 ⊂ 1) (union을 수행하기 위해서는, 노드 0을 노드 1의 부모노드로 만들거나 그 반대로 만들어야 한다.)

간선 1-2:

⇒ 1과 2는 각각 1과 2 부분집합에 속한다.

⇒ 두 부분집합은 서로 다르므로, union을 실행한다.

⇒ 2번 노드를 1번 노드의 부모 노드로 만든다. (0⊂1, 1⊂2)

간선 0-2:

⇒ 0과 2는 각각 0과 2 부분집합에 속한다.

⇒ 1은 0번 노드의 부모이고, 2는 1의 부모이므로, 0 또한 부분집합 2에 속한다.

⇒ 이렇게, 사이클이 형성된다.