在前幾天，我們學習了最短路徑問題 (Shortest Path)，例如 Dijkstra、Bellman-Ford、Floyd-Warshall、A*，今天要介紹的則是圖論中的另一個核心問題 —— 最小生成樹 (Minimum Spanning Tree, MST)

什麼是最小生成樹?

對於一個 連通、加權、無向圖:

• 生成樹 (Spanning Tree): 包含所有頂點，邊數為 $V-1$ 的子圖，且保證連通、無環。
• 最小生成樹 (MST): 在所有生成樹中，邊權重和最小的一棵。

應用場景:

• 網路佈線 (最省成本連接所有電腦/伺服器)
• 電力網建設 (最少電纜成本連接所有城市)
• 道路/光纖規劃 (確保覆蓋所有節點，且成本最小)

演算法分類

兩個經典演算法:

• Kruskal’s Algorithm (邊為導向)
  • 思路
    • 將所有邊依照權重排序
    • 從最小邊開始，若不會形成環，則加入生成樹
    • 重複直到選出 $V-1$ 條邊
  • 工具: 並查集 (Union-Find)
• Prim’s Algorithm (點為導向)
  • 思路
    • 從任意一個節點開始
    • 每次選取連接「已在樹內」與「樹外」節點的最小邊
    • 重複直到所有節點加入生成樹
  • 工具: 優先佇列 (Min-Heap)

Python 實作

Kruskal 演算法

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

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路徑壓縮
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        return True


def kruskal(V, edges):
    uf = UnionFind(V)
    mst = []
    edges.sort(key=lambda x: x[2])  # 按照權重排序
    
    for u, v, w in edges:
        if uf.union(u, v):
            mst.append((u, v, w))
    return mst


# 測試
V = 4
edges = [
    (0, 1, 10),
    (0, 2, 6),
    (0, 3, 5),
    (1, 3, 15),
    (2, 3, 4)
]

mst = kruskal(V, edges)
print("Kruskal MST:", mst)
# 輸出: [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

Prim 演算法

import heapq

def prim(graph, start=0):
    V = len(graph)
    visited = [False] * V
    mst = []
    pq = [(0, start, -1)]  # (權重, 當前節點, 來源節點)

    while pq:
        w, u, parent = heapq.heappop(pq)
        if visited[u]:
            continue
        visited[u] = True
        if parent != -1:
            mst.append((parent, u, w))

        for v, weight in graph[u]:
            if not visited[v]:
                heapq.heappush(pq, (weight, v, u))
    return mst


# 測試
graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}

mst = prim(graph, 0)
print("Prim MST:", mst)
# 輸出: [(0, 3, 5), (2, 3, 4), (0, 1, 10)]

Kruskal vs Prim 比較

應用場景

• 網路佈線: 找出最小成本連接所有電腦的電纜佈線方式
• 電力網建設: 最少電纜長度連接所有城市
• 聚類分析 (Clustering): MST 可用於分群，透過刪除權重最大的邊，將圖劃分為多個子群

結語

最小生成樹 (MST) 問題與最短路徑不同，它關心的是 整體的最小成本連接，而不是單點之間的最短距離。Kruskal 與 Prim 是兩種經典解法，分別適用於稀疏圖與稠密圖

在 Day 27 與 Day 28，我們會分別深入 Kruskal 與 Prim，帶大家更細緻地掌握這兩個演算法的細節與應用