Algorithm - 최소신장트리(Kruskal, Prim)

문제 참고

최소 신장 트리(MST, Minimum Spanning Tree)

• 신장 트리
• 모든 노드를 포함하면서, 사이클을 이루지 않는 트리

• 최소 신장 트리
• 신장 트리 중 그래프에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 연결한 트리

Kruskal 알고리즘

• 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택한다.

• 탐욕법을 이용하여 최소 비용을 연결한다.

• 과정
1. 그래프의 간선들을 오른차순으로 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택
→ 사이클을 형성하는 간선은 제외하며, 가장 낮은 가중치를 먼저 선택한다.
→ 사이클 판별 여부는 최적화된 union-find로 판별한다.
Union-Find

def find(parent, x):
    if parent[x] == x: return x
    else: return find(parent, parent[x])

def union(parent, x, y):
    rootX = find(parent, x)
    rootY = find(parent, y)
    if rootA > rootB: rootA,rootB=rootB,rootA
    parent[rootA]=rootB

v,e=list(map(int, input().split()))
parent=[i for i in range(v+1)] 
edges=[]; answer=0
for _ in range(e):
    a, b, cost = map(int, input().split())
    edges.append((cost, a, b))
edges.sort()
for cost,a,b in edges:
    if find(parent, a) != find(parent, b):
      union(parent, a, b)
      answer+=cost
print(answer)

• 시간 복잡도는 O(ElogE) (E: 간선의 개수)
• 간선을 정렬하는 작업(퀵소트, O(NlogN))이 대부분임

Prim 알고리즘

• 시작 정점에서 출발하여 신장 트리 집합을 단계적으로 확장해나가는 방법

• 이전 단계에서 만들어진 신장 트리를 확장하는 기법

• 과정
• 정점부터 출발하여, 각 정점들 중에 최소 간선으로 연결된 정점을 선택하여 트리를 확장함
• 최소 간선 연결 선택을 위해 우선순위 큐 가 사용됨
• 노드에 연결되어 있는 방문하지 않은 모든 노드들을 heapq에 넣는다.
• 이미 그래프에 속한 노드인지 판별을 위해 visited 배열 필요
• 이를 (N-1)개의 간선을 가질 때까지 반복하며 cost를 더한다.

# 프림
import heapq
import sys
from collections import defaultdict
input = sys.stdin.readline
v,e=list(map(int, input().split()))
edges=defaultdict(list)
for _ in range(e):
    a,b,cost=list(map(int, input().split()))
    edges[a].append((cost,b))
    edges[b].append((cost,a))

h=[]; cnt=1
heapq.heappush(h, (0, 1))
visited=[False for _ in range(v+1)]
answer=0
while(h):
    cost,here= heapq.heappop(h)
    if visited[here]: continue # heapq의 노드가 방문한 곳이면 continue
    visited[here]=True 
    answer += cost # 선택된 간선 cost 증가
    for next_cost,_next in edges[here]: # 노드의 간선들에 대해 방문하지 않았으면 
        if not visited[_next]: # heapq에 삽입
            heapq.heappush(h, (next_cost, _next)) # cost + next_cost 아님
print(answer)

• 시간 복잡도는 O(ElogV) (E:간선의 개수, V:노드의 개수)