最小生成樹（MST, Minimum Spanning Tree）

 最小生成樹（MST, Minimum Spanning Tree） 問題

---

問題描述

給定一個 無向加權連通圖，圖中有 (n) 個頂點和 (m) 條邊，每條邊有一個權重。請找出該圖的 最小生成樹，即：

1. 包含所有頂點。
2. 邊的總權重最小。
3. 不包含環。

---

解法

最常用的兩種演算法來求最小生成樹：

1. Kruskal 演算法：基於邊排序，使用並查集來檢查環。
2. Prim 演算法：基於頂點，每次選擇權重最小且未加入樹的邊。

以下用 Kruskal 演算法實現。

---

Kruskal 演算法

1. 將所有邊按權重從小到大排序。
2. 從小到大依次選擇邊，並檢查是否形成環：
   • 如果不形成環，將邊加入最小生成樹。
   • 如果形成環，跳過這條邊。
3. 當樹中包含 (n-1) 條邊時，最小生成樹構建完成。

---

Python 程式碼

class UnionFind:
    """並查集實現"""
    def __init__(self, n):
        self.parent = list(range(n))  # 每個節點的父節點
        self.rank = [0] * n           # 每個集合的秩（樹的高度）

    def find(self, x):
        """查詢 x 的根節點"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路徑壓縮
        return self.parent[x]

    def union(self, x, y):
        """合併 x 和 y 所屬的集合"""
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            elif self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1


def kruskal(n, edges):
    """
    Kruskal 演算法求最小生成樹權重總和
    :param n: 節點數
    :param edges: 邊列表，每條邊為 (u, v, w)
    :return: 最小生成樹的權重總和
    """
    uf = UnionFind(n)
    mst_weight = 0
    mst_edges = 0

    # 按邊的權重排序
    edges.sort(key=lambda x: x[2])

    for u, v, w in edges:
        if uf.find(u) != uf.find(v):  # 如果不形成環
            uf.union(u, v)
            mst_weight += w
            mst_edges += 1
            if mst_edges == n - 1:  # 當 MST 包含 n-1 條邊時停止
                break

    return mst_weight


# 測試資料
n = 4  # 節點數
edges = [
    (0, 1, 1),
    (1, 2, 2),
    (0, 2, 2),
    (1, 3, 3),
    (2, 3, 4)
]

# 計算最小生成樹的權重
print("最小生成樹的權重總和:", kruskal(n, edges))

---

測試範例

測試資料 1

輸入：

n = 4
edges = [
    (0, 1, 1),
    (1, 2, 2),
    (0, 2, 2),
    (1, 3, 3),
    (2, 3, 4)
]

輸出：

最小生成樹的權重總和: 6

---

程式說明

1. 初始化並查集：
   每個節點最開始是自己的一組。
2. 排序邊：
   按權重從小到大排序。
3. 選擇邊：
   每次選擇權重最小且不形成環的邊，加入最小生成樹。
4. 停止條件：
   當選擇的邊數達到 (n-1) 時，最小生成樹構建完成。
   –

優化與適用場景

1. 優化：
   • 若圖的頂點數較少且邊數多，可考慮使用 Prim 演算法。
2. 適用場景：
   • 解決網絡連通性問題（如電纜鋪設成本最小化）。
   • 圖的最小生成樹應用（如最短管道建造問題）。