[그래프] 백준 1197 최소 스패닝 트리(kruskal/prim)

최소 스패닝 트리란?

모든 정점을 포함하며/ 사이클이 만들어지지 않고/ 최소한의 가중치 값의 합

을 만족하는 트리이다.

 

1. kruskal 알고리즘

- 그리디

- 가중치가 가장 작은 값부터 선택하면서

- 사이클이 만들어진다면 버리고

- 반복

import sys
V, E = map(int, sys.stdin.readline().split())
root = [i for i in range(V+1)] # root[i]는 i의 루트 정점을 의미

edges=[]
for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    edges.append([w, u, v])
edges.sort() # 오름차순

def find_root(x):
    if x!=root[x]:
        root[x]=find_root(root[x])
    return root[x]

result = 0
for i in range(E):
    w, u, v = edges[i]
    u_root = find_root(u)
    v_root = find_root(v)
    # 둘의 root가 같을때 연결하면 cycle이 된다.
    if u_root != v_root:
        if u_root>v_root:
            root[u_root]=v_root
        else:
            root[v_root]=u_root
        result += w
print(result)

 

2. prim 알고리즘

- 한 정점을 임의의 시작점으로 잡고

- visited에 포함된 정점들 / 그 외의 정점들 집합으로 나눠서

- 두 집합 사이 최저 가중치를 갖는 (아직 방문하지 않은)정점을 연결

- https://www.weeklyps.com/entry/%ED%94%84%EB%A6%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Prims-algorithm

프림 알고리즘 ( Prim's algorithm )

import sys
import heapq

V, E = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(V+1)]
for _ in range(E):
    u, v, w = map(int, sys.stdin.readline().split())
    graph[u].append([w, v])
    graph[v].append([w, u])
visited = [0]*(V+1)
heap = [[0,1]]

result = 0
cnt = 0
while heap:
    if cnt==V:
        break
    w, s = heapq.heappop(heap)
    if visited[s]==0:
        visited[s]=1
        result += w
        cnt += 1
        for i in graph[s]:
            heapq.heappush(heap, i)
print(result)