Union-Find 알고리즘, KRUSKAL 알고리즘

Union-Find 란?

Disjoint Set을 표현할 때 사용하는 알고리즘 

• 그렇다면 Disjoint Set(서로소 집합, 상호 배타 집합) 이란 ?
  • 서로 공통된 원소를 가지고 있지 않은 두 개 이상의 집합을 말한다.
  • 집합에 속한 하나의 특정 멤버(root node)를 통해 각 집합들을 구분한다. 이를 대표자(representative)라 한다. 

 

• 상호 배타 집합을 표현하는 방법 
  1. 트리
     • 하나의 집합을 하나의 트리로 표현
     • 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다. 
     • 연결 리스트보다 효율적이다.
  1. 연결 리스트
     • 같은 집합의 원소들은 하나의 연결 리스트로 관리
     • 연결 리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.
     • 각 원소는 집합의 대표 원소를 가리키는 링크를 갖는다.

 

상호 배타 집합 연산

make-set(x)

• x를 유일한 원소로 하는 새로운 집합을 만든다. (초기화)

parent = list(range(N + 1))

 

find-set(x)

• x가 속한 집합의 대표(root node)를 알아낸다.

def find(x):
    if parent[x] == x:
        return x
    else:
        return find(parent[x])
        
# 시간 복잡도 더 줄이기 
def find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]

 

union(x, y)

• x가 속한 집합과 y가 속한 집합을 합친다. 

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

 

 

Union-Find 연산 효율 높이기

Union by Rank

• 각 노드는 자신을 루트로 하는 subtree의 높이를 rank라는 이름으로 저장한다.
• 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다.

make-set(x)

parent = list(range(N + 1))
# union by rank에서의 깊이 저장하는 리스트
rank = [0 for i in range(N + 1)]

 

find-set(x)

def find(x):
    if parent[x] == x:
        return x
    else:
        return find(parent[x])
        
# 시간 복잡도 더 줄이기 
def find(x):
    if parent[x] == x:
        return x
    parent[x] = find(parent[x])
    return parent[x]

 

union(x, y)

# 시간 복잡도를 좀 더 줄이는 union by rank
def union_by_rank(x, y):
    x = find(x)
    y = find(y)
	
    # 깊이가 더 깊은 곳에 붙인다. 
    # 깊이가 깊지 않아야 find 함수의 시간 복잡도가 줄기 때문
    if rank[x] > rank[y]:
        parent[y] = x
    elif rank[x] < rank[y]:
        parent[x] = y
    else:
        parent[y] = x	# 깊이가 같은건 어디에 붙여도 상관없음
        rank[x] += 1	# 근데 루트가 된 곳의 깊이는 +1이 된다.

 

---

 

KRUSKAL 알고리즘

• 간선을 하나씩 선택해서 MST를 찾는 알고리즘
  1. 처음에 모든 간선을 가중치에 따라 오름차순으로 정렬한다. ★
  2. 가중치가 가장 낮은 간선부터 선택하면서 이동한다.
     • 주의 ⚠︎ 사이클이 존재하면 다음으로 가중치가 낮은 간선을 선택한다.
  3. n-1개의 간선이 선택될 때까지 ②를 반복한다.

 

예시 문제

SWEA - 5249. 최소신장트리