1. 基本定義
-
生成樹：在一個連通無向圖中，一個生成樹是包含所有頂點且邊數為 n?1（n為頂點數）的無環連通子圖。
-
最小生成樹：在所有生成樹中，邊權和最小的那一棵樹。也就是說，若每條邊有一個非負權值，最小生成樹就是使得所有選中邊的權值之和最小的生成樹。
2. 基本性質
-
連通性：MST必須覆蓋圖中的所有頂點，保證圖中任意兩個頂點之間都有路徑連接。
-
無環性：由于MST是一棵樹，所以它沒有回路。
-
邊數：對于一個有 n 個頂點的圖，生成樹總是包含 n?1 條邊。
-
唯一性：如果圖中所有邊的權值都不同，則最小生成樹是唯一的；當存在相同權值的邊時，可能會有多個不同的最小生成樹。
3. 關鍵性質與定理
-
割定理（Cut Property）：對于圖中的任意割（將頂點分成兩部分的劃分），跨越這個割的權值最小的邊必定出現在某個最小生成樹中。這一定理是貪心算法（如 Kruskal 和 Prim 算法）正確性的理論基礎。
-
環定理（Cycle Property）：在圖中的任意一個環中，若存在一條邊的權值最大，則這條邊不可能出現在最小生成樹中。這個性質用于排除在構造 MST 時會引入環路的邊。
4. 貪心策略與算法
最小生成樹的求解常采用貪心策略，即在每一步都選擇局部最優的邊，從而希望構造出全局最優的生成樹。常見的算法包括：
-
Kruskal 算法：
-
思路：先將所有邊按照權值從小到大排序，然后依次選擇每條邊（前提是不與已選邊形成環），直到選出 n?1 條邊。
-
理論依據：利用割定理保證每次選擇的最小邊是安全的。
-
-
Prim 算法：
-
思路：從任一頂點開始，逐步將與當前生成樹相連的權值最小的邊加入生成樹，直到所有頂點都被包含在內。
-
理論依據：同樣基于割定理，確保每次擴展都不會違背最優性。
-
5. 正確性證明
-
交換論證法：證明如果某個最小生成樹解中沒有使用當前選定的最小邊，則可以用該邊替換某條邊而不增加總權值，從而證明貪心策略得到的解與最優解一致。
-
割定理證明：利用任意割的特性說明，在每個步驟選擇跨割的最小邊是安全的，且不會破壞后續構造最小生成樹的可能性。
6. 算法時間復雜度
-
Kruskal 算法：
-
邊排序：O(Elog?E)
-
并查集操作：每次查找和合并的時間復雜度近似為 O(α(n))（α(n)) 是極其緩慢增長的阿克曼函數的反函數）
-
總體復雜度通常認為是 O(Elog?E)。
-
-
Prim 算法：
-
利用優先隊列（最小堆）：總體時間復雜度為 O((E+V)log?V)
-
對于稠密圖來說，使用鄰接矩陣和簡單數組實現時的復雜度可達到
。
-
7. 應用與擴展
最小生成樹理論不僅在理論計算機科學中占有重要地位，而且在實際問題中也有廣泛應用，如：
-
網絡設計：構造最經濟的通信網絡、交通網絡和電網等。
-
聚類分析：在數據挖掘中用于發現數據中的結構。
-
近似算法：例如解決 NP-hard 問題時，通過構造 MST 提供近似解。
