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)를 기반으로 쓰입니다

크루스칼 알고리즘:

1. light edge에 가중치를 준다 (= 비용이 적은 edge를 우선적으로 확인)
2. edge를 하나씩 확인하며 현재의 edge가 cycle을 발생시키는지 확인한다
   • cycle 발생하지 않는 경우: MST에 포함시킨다
   • cycle 발생하는 경우: MST에 포함시키지 않는다
3. 모든 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)

크루스칼 알고리즘 시간복잡도

1. edge 정렬(light edge에 가중치)
   • 모든 node에 대해 union 연산을 수행하므로 초기화에 필요한 계산량은 $O(N)$입니다.
   • 이후 edge를 중심으로 정렬을 수행하므로 현존하는 알고리즘 가운데 가장 성능 좋은 기법을 쓸 경우 그 계산량은 $O(ElogE)$입니다.
     (Python의 경우 sort()를 뜻 합니다)
2. edges 탐색
   • Set에 속한 데이터 수가 𝑛개일 때 find_parent , union_parent 연산의 계산복잡성은 모두 𝑂(log𝑛)이고,
   • 이를 전체 edge에 대해 반복 수행하므로 반복문에서 필요한 계산량은 𝑂(𝐸log𝐸)입니다.

따라서 크루스칼 알고리즘의 전체적인 계산복잡성은 $O(ElogE)$입니다

이코테 p.290 & 링크