1. 貪心算法的基本思想

貪心算法在每一步都選擇局部最優的邊，希望最終得到整體最優的生成樹。常見的兩種 MST 算法為 Kruskal 算法 和 Prim 算法。這兩者均滿足貪心選擇性質和最優子結構性質，即：

• 貪心選擇性質：局部最優選擇（比如選擇當前權值最小的邊）可以構成全局最優解。

• 最優子結構：一個最優解包含其子問題的最優解。

---

2. 正確性證明

2.1 交換論證法

以 Kruskal 算法為例，正確性證明常使用“交換論證法”：

• 假設在某一步選取了當前權值最小的邊 e，若該邊不在某最優解中，則存在一個邊 f（在最優解中）可以與 e 交換，并且不會增加生成樹的總權值。

• 通過不斷的“交換”，最終可構造出與 Kruskal 算法選取的邊集合相同的生成樹，從而證明其最優性。

2.2 剪枝證明（Cut Property）

• 割定理（Cut Property）：對于圖中的任一割，跨割的最小邊必定屬于某個 MST。

• Kruskal 算法每次選擇全圖中最小且不會形成環的邊，正好滿足割定理，從而確保了所選邊集一定可以擴展為 MST。

類似地，Prim 算法從任意一個點開始，每次添加連接已構造生成樹和其他頂點之間最小的邊，這也遵循割定理，從而保證了正確性。

---

3. 算法步驟

3.1 Kruskal 算法步驟

1. 排序：將所有邊按權值從小到大排序。

2. 初始化：每個頂點為一個獨立的集合（并查集數據結構）。

3. 遍歷邊集：依次取出最小邊，判斷其兩個頂點是否在同一集合：

   • 如果不在同一集合，則將該邊加入生成樹，并合并兩個集合；

   • 否則，跳過該邊（避免環的產生）。

4. 終止條件：當生成樹邊數達到 n?1（n 為頂點數）時結束。

3.2 Prim 算法步驟

1. 初始化：任選一個頂點，將其加入 MST 集合。

2. 維護優先隊列：將所有與當前生成樹相連的邊加入優先隊列。

3. 選擇邊：從隊列中取出最小邊，若其另一端未被訪問，則加入生成樹，并將該頂點所有相連邊更新到隊列。

4. 重復：直到所有頂點均已加入 MST。

---

4. 時間復雜度分析

4.1 Kruskal 算法

• 排序：對所有 E 條邊進行排序，時間復雜度為 O(Elog?E) 。

• 合并查找：利用路徑壓縮和按秩合并，合并與查詢的時間復雜度近似為 O(α(n))（α 為阿克曼函數的反函數，幾乎看作常數）。

• 總體：總體時間復雜度為 O(Elog?E)，當圖稀疏時可近似看作 O(Elog?V)。

4.2 Prim 算法

• 利用最小堆：每次從堆中取出最小邊和更新堆的操作總體復雜度為 O((E+V)log?V)。

• 總體：因此總體時間復雜度為 O(Elog?V)。

---

5. 實例分析

考慮下列圖：

• 頂點集合：{A, B, C, D, E}

• 邊集合及權值：

  • A-B: 1

  • A-C: 3

  • B-C: 3

  • B-D: 6

  • C-D: 4

  • C-E: 2

  • D-E: 5

利用 Kruskal 算法構造 MST：

1. 排序邊：A-B(1), C-E(2), A-C(3), B-C(3), C-D(4), D-E(5), B-D(6)。

2. 選邊：

   • A-B (1)：加入，集合合并 {A, B}。

   • C-E (2)：加入，集合合并 {C, E}。

   • A-C (3)：A 屬于 {A, B}，C 屬于 {C, E}，加入，集合合并 {A, B, C, E}。

   • B-C (3)：跳過（形成環）。

   • C-D (4)：D 未加入集合，加入后合并為 {A, B, C, D, E}。

3. 完成：共選 4 條邊，即生成 MST，總權值 1+2+3+4=10。

---

6. Python代碼舉例

以下代碼使用 Kruskal 算法實現 MST 求解，并展示了如何使用并查集數據結構：

class UnionFind:def __init__(self, n):self.parent = list(range(n))self.rank = [0] * ndef find(self, u):if self.parent[u] != u:self.parent[u] = self.find(self.parent[u])return self.parent[u]def union(self, u, v):root_u = self.find(u)root_v = self.find(v)if root_u == root_v:return False  # u 和 v 已經在同一集合# 按秩合并if self.rank[root_u] < self.rank[root_v]:self.parent[root_u] = root_velif self.rank[root_u] > self.rank[root_v]:self.parent[root_v] = root_uelse:self.parent[root_v] = root_uself.rank[root_u] += 1return Truedef kruskal(n, edges):"""n: 頂點數，頂點編號為 0 到 n-1edges: 邊列表，每個元素 (u, v, weight)返回最小生成樹的邊列表及總權值"""# 按權值排序邊edges.sort(key=lambda x: x[2])uf = UnionFind(n)mst = []total_weight = 0for u, v, weight in edges:if uf.union(u, v):mst.append((u, v, weight))total_weight += weightif len(mst) == n - 1:breakreturn mst, total_weight# 示例數據
# 對應上面的實例，頂點 A,B,C,D,E 分別用 0,1,2,3,4 表示
edges = [(0, 1, 1),  # A-B(0, 2, 3),  # A-C(1, 2, 3),  # B-C(1, 3, 6),  # B-D(2, 3, 4),  # C-D(2, 4, 2),  # C-E(3, 4, 5)   # D-E
]
n = 5mst, total_weight = kruskal(n, edges)
print("最小生成樹邊集:", mst)
print("總權值:", total_weight)

運行結果將輸出 MST 邊集及其總權值。例如，上述代碼可能輸出：

最小生成樹邊集: [(0, 1, 1), (2, 4, 2), (0, 2, 3), (2, 3, 4)]
總權值: 10

最小生成樹邊集: [(0, 1, 1), (2, 4, 2), (0, 2, 3), (2, 3, 4)] 總權值: 10

---

總結

• 邏輯推理與正確性證明：貪心算法基于割定理及交換論證法保證了局部最優選擇可推導出全局最優解。

• 算法步驟：Kruskal 和 Prim 分別通過排序邊或維護最小堆實現貪心選擇。

• 時間復雜度：Kruskal 算法主要為 O(Elog?E) ；Prim 算法為 O(Elog?V) 。

• 實例與代碼：通過一個實例和 Python 代碼演示了 MST 的求解過程。