[Data Structure & Algorithm] 최소 신장 트리 & 크루스칼 알고리즘 (shortest path)
Data Structure
신장 트리(Spanning Tree):
-
Tree 자료구조 중 하나입니다
-
하나의 graph가 있을때 모든 node를 포함하면서 cycle이 존재하지 않는, 부분 graph를 뜻 합니다
최소 신장 트리(Minimum Spanning Tree, MST):
- 하나의 graph에서 여러개의 신장 트리가 나올 수 있는데, 이 중 최소한의 비용의 트리를 최소 신장 트리라 합니다
Algorithm
MST 를 찾는 알고리즘으로 크루스칼 알고리즘(Kruskal Algorithm)과 프림 알고리즘(Prim’s algorithm)이 존재하는데
본 글에서는 크루스칼 알고리즘에 대해 알아 보겠습니다
크루스칼 알고리즘 특징:
- greedy algorithm 중 하나입니다
- 서로소 집합 자료구조(disjoint set data structure)를 기반으로 쓰입니다
크루스칼 알고리즘:
- light edge에 가중치를 준다 (= 비용이 적은 edge를 우선적으로 확인)
- edge를 하나씩 확인하며 현재의 edge가 cycle을 발생시키는지 확인한다
- cycle 발생하지 않는 경우: MST에 포함시킨다
- cycle 발생하는 경우: MST에 포함시키지 않는다
- 모든 edge에 대해 2 번의 과정을 반복한다
source code 예시
# 이코테 p.288 크루스칼 알고리즘
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):
a = find_parent(parent, a)
b = find_parent(parent, b)
if a < b:
parent[b] = a
else:
parent[a] = b
v, e = map(int, input().split())
parent = [0] * (v + 1)
edges = []
result = 0
for i in range(1, v + 1):
parent[i] = i
for _ in range(e):
a, b, cost = map(int, input().split())
edges.append((cost, a, b))
edges.sort()
for edge in edges:
cost, a, b = edge
if find_parent(parent, a) != find_parent(parent, b): # cycle이 발생하지 않는 경우에만 포함
union_parent(parent, a, b)
result += cost
print(result)
크루스칼 알고리즘 시간복잡도
- edge 정렬(light edge에 가중치)
- 모든 node에 대해 union 연산을 수행하므로 초기화에 필요한 계산량은 입니다.
- 이후 edge를 중심으로 정렬을 수행하므로 현존하는 알고리즘 가운데 가장 성능 좋은 기법을 쓸 경우 그 계산량은 입니다.
(Python의 경우 sort()를 뜻 합니다)
- edges 탐색
- Set에 속한 데이터 수가 𝑛개일 때 find_parent , union_parent 연산의 계산복잡성은 모두 𝑂(log𝑛)이고,
- 이를 전체 edge에 대해 반복 수행하므로 반복문에서 필요한 계산량은 𝑂(𝐸log𝐸)입니다.
따라서 크루스칼 알고리즘의 전체적인 계산복잡성은 입니다
이코테 p.290 & 링크
Author And Source
이 문제에 관하여([Data Structure & Algorithm] 최소 신장 트리 & 크루스칼 알고리즘 (shortest path)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jiggyjiggy/Data-Structure-Algorithm-신장-트리-크루스칼-알고리즘-shortest-path저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)