Minimum Spanning Tree

Chiahui Chen

3 min read

·

Jun 19, 2026

--

Share

解決無向圖的問題。有兩種常見解法。

1. Kruskal’s Algorithm

以邊界來看。

從最小的邊開始加，只要不構成 cycle 即可加入，加到 n-1 就中止。

class DSU:

    def __init__(self, n):
        self.roots = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.roots[x] == x:
            return x
        self.roots[x] = self.find(self.roots[x])
        return self.roots[x]

    def union(self, x, y):
        rootX, rootY = self.find(x), self.find(y)
        if rootX == rootY:
            return False
        if self.rank[rootX] > self.rank[rootY]:
            self.roots[rootY] = rootX
        elif self.rank[rootY] > self.rank[rootX]:
            self.roots[rootX] = rootY
        else:
            self.roots[rootY] = rootX
            self.rank[rootX] += 1
        
        return True


dsu = DSU(n)
edges = []
mst_w, mst_edges = 0, []
for _ in range(m):
    u, v, w = map(int, input().split())
    edges.append((w, u, v))

for w, u, v in sorted(edges):
    if dsu.union(u, v):
        mst_edges.append((u, v, w))
        mst_w += w
        if len(mst_edges) == n - 1:
            break

2. Prim’s Algorithm

以點來看。

任意點開始，push 邊進 min_heap, pop 最小的邊。

st = 0
mst_weights, mst_edges = 0, [st]
visited = set()
min_heap = [(0, st)] # weight, cur

while min_heap:
    w, u = heappop(min_heap)
    
    if u in visited:
        continue
    
    visited.add(u)
    mst_weights += w

    if u != st:
        mst_edges.append(u)
    for v, w in graph.get(u, []):
        heappush(min_heap, (w, v))