최소 신장 트리 ( Minimum Spanning Tree )
Spanning Tree
그래프내 모든 정점을 포함하는 트리
그래프의 최소 연결 부분 그래프
- 최소 연결 = 간선의 수가 적다.
- n개의 노드의 최소 간선 개수는 N - 1개이고, N - 1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고, 이를 Spannig Tree라고 한다.
특징
- DFS, BFS와 같은 트리 탐색 방법으로 신장 트리를 찾을 수 있다.
- 여러 개의 신장트리가 존재할 수 있다.
- 모든 노드가 연결되어 있어야하며 사이클이 포함되어서는 안된다.
최소 신장 트리
Spanning Tree를 이루는 간선들의 가중치 합이 최소인 트리
가중치의 합이 동일하지 않을 때 적은 수의 간선을 사용한다고 최소 비용이 적어지는 것은 아니다. 가중치를 고려한 Spanning Tree를 고르는 방식.
Kruscal Algorithm
그리디(Greedy)한 방법으로 모든 노드를 최소비용으로 연결하는 방법을 찾는 알고리즘.
💡 **Greedy?**- 그 순간 가장 좋은 선택지를 고르는 과정을 반복해서 해답을 찾는 과정
- 그 순간 최적을 골라나가는 것이 전체적으로 최적이라는 보장이 없기 때문에 검증 과정이 꼭 필요하다. (but. Kruscal은 최적의 값을 알려줌)
동작 과정
- 간선들의 가중치를 오름차순으로 정렬한다.
- 리스트에서 순서대로 사이클을 형성하지 않는 낮은 가중치의 간선을 선택한다.
- Spanning Tree가 완성될 때까지 과정을 반복한다.
주의할 점
최소 비용의 간선을 선택할 때마다 사이클이 만들어지는지 확인하는 과정이 필요하다. 추가할 간선의 양 끝 노드가 현재 만들고 있는 Spanning Tree에 포함되어 있는지 확인하는 방식을 통해서 체크가 가능하다.
이때 union-find 알고리즘을 활용하여 두 노드가 같은 집합에 속하는지 확인할 수 있다.
시간 복잡도
앞서 union-find 알고리즘을 이용하면 Kruscal 알고리즘의 시간 복잡도는 가중치가 있는 간선을 정리하는 시간에 영향을 많이 받는다. 퀵정렬을 통해 간선 정렬을 하는 Kruscal알고리즘인 경우 시간 복잡도는 O(e * loge) 로 정의할 수 있다.
백준 1197번 - 최소 스패닝 트리 (with. Kruscal)
import sys
import heapq
input = sys.stdin.readline
V, E = map(int, input().split())
edges = [ list(map(int, input().split())) for _ in range(E) ]
parent = [ x for x in range( V + 1 ) ]
flag = [ False for _ in range( V + 1 ) ]
wtf = []
# adjedctive list
adj_list = [ [] for _ in range( V + 1 )]
for e in edges:
a, b, c = e
adj_list[a].append([b, c])
adj_list[b].append([a, c])
# Kruscal Algorithm
sorted_edges = sorted(edges, key = lambda x : x[-1])
cost = 0
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
return parent[x]
for e in sorted_edges:
A, B, C = e
p_a = find_parent(parent, A)
p_b = find_parent(parent, B)
if p_a == p_b:
continue
else:
if p_a < p_b:
parent[p_a] = p_b
else:
parent[p_b] = p_a
cost += C
print(cost)
참고: https://techblog-history-younghunjo1.tistory.com/262#google_vignette
Prim Algorithm
시작 정점에서 출발해서 Spanning Tree의 집합을 확장해나가는 방법
동작 과정
- 시작 정점을 Spanning Tree의 집합에 넣고 시작한다.
- Spanning Tree 집합과 연결된 간선 중 가장 낮은 가중치의 간선을 선택하고 연결된 노드를 Spanning Tree 집합에 포함시킨다.
- 위 과정을 Spanning Tree의 간선이 N - 1개가 될 때까지 반복한다.
시간 복잡도
정점의 수 만큼 반복하고, 정점마다 간선에 대해서 반복하기 때문에 시간 복잡도는 O(n^2) 라고 볼 수 있다.
백준 1197번 - 최소 스패닝 트리 (with. Prim)
import sys
import heapq
input = sys.stdin.readline
V, E = map(int, input().split())
edges = [ list(map(int, input().split())) for _ in range(E) ]
parent = [ x for x in range( 1, V + 1 ) ]
flag = [ False for _ in range( V + 1 ) ]
wtf = []
# adjedctive list
adj_list = [ [] for _ in range( V + 1 )]
for e in edges:
a, b, c = e
adj_list[a].append([b, c])
adj_list[b].append([a, c])
# prim algorithm
q = [(0, 1, 1)]
total_cost = 0
while q:
cost, node, prev = heapq.heappop(q)
if flag[node] is True:
continue
wtf.append([cost, node, prev])
flag[node] = True
total_cost += cost
for dst, weight in adj_list[node]:
if flag[dst] is False:
heapq.heappush(q, (weight, dst, node))
print(total_cost)참고: https://gmlwjd9405.github.io/2018/08/30/algorithm-prim-mst.html
서로소 집합 자료구조
서로소 집합이란 교집합이 없는 다른 집합을 의미한다. 따라서 서로소 집합 자료구조는 서로소 부분 집합으로 나누어진 원소들의 데이터를 처리하기 위한 자료구조이다. 서로소 집합 자료구조는 합집합 연산인 union 과 찾기 연산인 find 연산을 사용할 수 있다.
동작과정
- Union 연산에서 연결된 두 노드 A, B를 확인한다.
- 두 노드의 root node(A’, B’)를 탐색한다. (Find 연산)
- 두 root node 중 작은 값을 부모 노드로 가정하고 두 부모노드를 연결한다. ( A’ < ‘B 인 경우, B’ → A’ )
- 남은 연산에 대해서 위 과정을 반복한다.
def init_parent(array = [], v):
parent = [ 0 ] * (v + 1)
for i in array:
parent[i] = i
def find_parent(parent, x):
if parent[x] != x:
parent[x] = find_parent(parent, parent[x])
# 부모 노드가 재귀에 의해서 업데이트 된다.
return parent[x]
def union_parent(parent, a, b):
p1 = union_parent(parent, a)
p2 = union_parent(parent, b)
if p1 > p2:
parent[p1] = p2
else:
parent[p2] = p1이 서로소 집합 알고리즘을 통해서 크루스칼 알고리즘의 조건 중 하나인 ‘Spanning Tree’ 내부에 Cycle이 없어야한다는 점을 검증할 수 있다.
cycle = False
for _ range(e):
a, b = map(int, input().split()) # 간선 정보를 받는다.
if find_parent(parent, a) == find_parent(parent,b): # 두 노드의 부모노드를 비교
cycle = True # 같을 경우 순환하는 상태이다.
break
else:
union_parent(parent, a, b)참고: https://gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html
