Algorithm - Union-Find

Union-find

• Union-find는, 여러 개의 노드가 존재할 때 두 개의 노드를 선택하여 현재 이 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.

• 서로소 집합(Disjoint-Set)
• 서로 중복되지 않는 부분 집합들로 나누어진 원소들에 대한 정보를 저장하고 조작하는 자료구조
• 공통 원소가 없어야 한다.

• 과정
1. 초기화
• 각 노드들을 하나의 집합으로 초기화한다.
• 0~5까지의 노드가 있을 때 {0}, {1}, {2}, {3}, {4}, {5}와 같이 각각의 집합으로 초기화
2. 합치기(union)
• 두 집합을 합친다.
• union(a,b)를 하면 a와 b의 집합을 합침
3. 찾기(find)
• 주어진 노드가 속한 대표 노드를 반환한다.
 

• 예시



• 이 상태에서, union(1,4), union(2,3), union(2,4), union(5,6) 을 진행한 경우
 



• 다음과 같은 결과가 나온다. 1과 5가 각 집합의 대표 노드이다.
• 재귀함수를 통해 각 노드들의 parent를 판별, 같은 집합인지 확인한다.
 

• 단순한 구현

parent=[i for i in range(NODE_LEN)]
def find(parent, x):
    if parent[x] == x: return x
    else: return find(parent, parent[x])

def union(parent, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    parent[rootY] = rootX

• 다음과 같은
• 트리 구조가 비대칭적임
• 연결 리스트임
• 이런 경우 시간 복잡도가 O(n)이 됨, Recursion Error가 발생할 수 있다.

• 더 순위가 노드를 부모 노드로 만들어 최적화를 진행한다.

parent=[i for i in range(NODE_LEN)]

def find(parent, x):
    if parent[x] == x: return x
    else: return find(parent, parent[x])

def union(parent, x, y, rank):
    rootX = find(parent, x)
    rootY = find(parent, y)
    # 더 작은 루트 노드를 기준으로 합친다.
    if rootA>rootB: rootA,rootB=rootB,rootA
    parent[rootA]=rootB