최소 스패닝 트리 - BOJ

최소 스패닝 트리 - BOJ

크루스칼 알고리즘

def Find(x): # 부모가 같은지 비교
    if p[x] == x:
        return x
    else:
        y = Find(p[x])
        p[x] = y
        return y

def Union(x, y): #부모 병합
    x = Find(x)
    y = Find(y)
    if x != y:
        p[y] = x

V, E = map(int, input().split())
G = []
p = [i for i in range(V + 1)]
for _ in range(E):
    A, B, C = map(int, input().split())
    G.append([A, B, C])

G.sort(key=lambda x: x[2])

w, cnt = 0, 0
for i in range(E):
    s = G[i][0]
    e = G[i][1]
    d = G[i][2]
    if Find(s) != Find(e): # 사이클이 없는 경우(root 다른 경우)
        Union(s, e)
        w += d
        cnt += 1
    if cnt == V - 1:
        break
print(w)

프림 알고리즘

• 특정 노드를 선택했을 때 greedy 알고리즘에 따라서 해당 노드에 연결된 가장 가중치가 작은 간선을 선택(여기서 heapq 사용)하고 mst에 삽입
• 중간에 선택한 노드가 연결된 노드 집합에 없을 때(사이클이 생기지 않을 때)만 삽입.

import heapq
def prim(v):
    q = []
    visit = [False] * (V + 1)
    visit[v] = True
    d = 0
    cnt = 1
    for a in p[v]:
        heapq.heappush(q, a)
    while q:
        c, v = heapq.heappop(q)
        if not visit[v]:
            visit[v] = True
            cnt += 1
            d += c
            for a in p[v]:
                heapq.heappush(q, a)
        if cnt == V:
            return d
    return 0

V, E = map(int, input().split())
p = [[] for _ in range(V + 1)]

for _ in range(E):
    a, b, c = map(int, input().split())
    p[a].append((c, b))
    p[b].append((c, a))

print(prim(1))