1. 최소 신장 트리
•
Minimum Spanning Tree, MST 라고 불리움
•
가능한 Spanning Tree 중에서, 간선의 가중치 합이 최소인 Spanning Tree를 지칭함
2. 최소 신장 트리 알고리즘
•
그래프에서 최소 신장 트리를 찾을 수 있는 알고리즘이 존재함
•
대표적인 최소 신장 트리 알고리즘
◦
Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)
3. 크루스칼 알고리즘 (Kruskal's algorithm)
1.
모든 정점을 독립적인 집합으로 만든다.
2.
모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
3.
두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)
탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음)
4. Union-Find 알고리즘
•
Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘
•
간단하게, 노드들 중에 연결된 노드를 찾거나, 노드들을 서로 연결할 때 (합칠 때) 사용
•
Disjoint Set이란
◦
서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
◦
공통 원소가 없는 (서로소) 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 자료구조를 의미함
◦
Disjoint Set = 서로소 집합 자료구조
1.
초기화
•
n 개의 원소가 개별 집합으로 이뤄지도록 초기화
2.
Union
•
두 개별 집합을 하나의 집합으로 합침, 두 트리를 하나의 트리로 만듬
3.
Find
•
여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하기 위해, 각 그룹의 최상단 원소 (즉, 루트 노드)를 확인
path compression
•
Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법
•
Find를 실행한 노드는 이후부터는 루트 노드를 한번에 알 수 있음
•
union-by-rank 와 path compression 기법 사용시 시간 복잡도는 다음 계산식을 만족함이 증명되었음
◦
O(M log^N)
◦
log^N 은 다음 값을 가짐이 증명되었음
▪
N이 2^65536 값을 가지더라도, $ log^N 의 값이 5의 값을 가지므로, 거의 O(1), 즉 상수값에 가깝다고 볼 수 있음
5. 시간 복잡도
•
크루스컬 알고리즘의 시간 복잡도는 O(E log E)
◦
다음 단계에서 2번, 간선을 비용 기준으로 정렬하는 시간에 좌우됨 (즉 간선을 비용 기준으로 정렬하는 시간이 가장 큼)
1.
모든 정점을 독립적인 집합으로 만든다.
2.
모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
•
퀵소트를 사용한다면 시간 복잡도는 O(n log n) 이며, 간선이 n 이므로 O(E log E)
3.
두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)
•
union-by-rank 와 path compression 기법 사용시 시간 복잡도가 결국 상수값에 가까움, O(1)
6. 구현
parent = dict()
rank = dict()
def find(node):
# path compression 기법
if parent[node] != node:
parent[node] = find(parent[node])
return parent[node]
def union(node_v, node_u):
root1 = find(node_v)
root2 = find(node_u)
# union-by-rank 기법
if rank[root1] > rank[root2]:
parent[root2] = root1
else:
parent[root1] = root2
if rank[root1] == rank[root2]:
rank[root2] += 1
def make_set(node):
parent[node] = node
rank[node] = 0
def kruskal(graph):
mst = list()
# 1. 초기화
for node in graph['vertices']:
make_set(node)
# 2. 간선 weight 기반 sorting
edges = graph['edges']
edges.sort()
# 3. 간선 연결 (사이클 없는)
for edge in edges:
weight, node_v, node_u = edge
if find(node_v) != find(node_u):
union(node_v, node_u)
mst.append(edge)
return mst
Plain Text
복사
