一、什麼是生成樹和最小生成樹？¶
在數據結構中，圖是由頂點（也叫節點）和邊組成的結構。生成樹是指連通無向圖的一個子圖，它包含圖中所有的頂點，並且沒有環（即樹的性質：n個頂點有n-1條邊，且任意兩個頂點之間有且僅有一條路徑）。
舉個例子：如果有4個城市（頂點）A、B、C、D，它們之間的道路（邊）連接起來，形成一個沒有重複道路和閉環的網絡，這就是一個生成樹。而最小生成樹（Minimum Spanning Tree, MST） 則是所有可能的生成樹中，邊權值之和最小的那一棵。
比如，城市間的道路有不同的長度（權值），我們希望找到連接所有城市且總長度最短的道路網絡，這就是最小生成樹的問題。
二、貪心算法：爲什麼最小生成樹適合貪心？¶
貪心算法的核心思想是“每一步都選擇當前最優解，最終得到全局最優解”。最小生成樹恰好符合貪心算法的適用場景，因爲：
- 生成樹必須包含所有頂點，且邊數爲n-1（n爲頂點數）。
- 我們只需要考慮“局部最優”的邊選擇：每次選擇連接“已選頂點集合”和“未選頂點集合”的最小權邊，就能逐步構建出總權值最小的生成樹。
三、Prim算法的基本思路¶
Prim算法是最小生成樹的經典貪心算法之一，核心步驟如下：
- 初始化：任選一個頂點作爲起點（例如頂點v₀），將其標記爲“已選頂點”。
- 重複擴展：每次從“已選頂點集合”和“未選頂點集合”之間的所有邊中，選擇權值最小的那條邊，將對應的未選頂點加入“已選頂點集合”。
- 終止條件：當所有頂點都被加入“已選頂點集合”時，生成樹構建完成。
四、算法步驟詳解（附實例）¶
爲了直觀理解，我們用一個簡單的例子演示Prim算法：
示例圖：有4個頂點A、B、C、D，邊及其權值如下：
- A-B: 2，A-C: 3，B-C: 1，B-D: 4，C-D: 5
頂點編號：A=0，B=1，C=2，D=3。
步驟1：選擇起點¶
任選一個起點，比如選A（頂點0）。此時：
- 已選頂點集合 S = {0}（僅包含A）
- 未選頂點集合 U = {1, 2, 3}（B、C、D）
步驟2：尋找最小邊並擴展¶
重複以下操作，直到所有頂點被選中：
第一次迭代：¶
S = {0}，U = {1, 2, 3}
需要找S（0）和U（1,2,3）之間的所有邊：
- A-B（0-1）: 權值2
- A-C（0-2）: 權值3
最小邊是A-B（權值2）。將B（1）加入S：
S = {0, 1}，U = {2, 3}
第二次迭代：¶
S = {0, 1}，U = {2, 3}
需要找S（0,1）和U（2,3）之間的所有邊：
- A-C（0-2）: 權值3
- B-C（1-2）: 權值1
- B-D（1-3）: 權值4
最小邊是B-C（權值1）。將C（2）加入S：
S = {0, 1, 2}，U = {3}
第三次迭代：¶
S = {0, 1, 2}，U = {3}
需要找S（0,1,2）和U（3）之間的所有邊：
- A-D（無直接邊）
- B-D（1-3）: 權值4
- C-D（2-3）: 權值5
最小邊是B-D（權值4）。將D（3）加入S：
S = {0, 1, 2, 3}，所有頂點已選入。
最終最小生成樹¶
選中的邊爲：A-B（2）、B-C（1）、B-D（4），總權值=2+1+4=7。
五、算法實現與細節¶
1. 數據結構表示¶
圖可以用鄰接矩陣或鄰接表表示。對於初學者，鄰接矩陣更直觀（二維數組），例如：
graph = [
[0, 2, 3, 0], # A的鄰接：A-B=2，A-C=3
[2, 0, 1, 4], # B的鄰接：B-A=2，B-C=1，B-D=4
[3, 1, 0, 5], # C的鄰接：C-A=3，C-B=1，C-D=5
[0, 4, 5, 0] # D的鄰接：D-B=4，D-C=5
]
其中graph[i][j]表示頂點i和j之間的邊權值（0表示無邊）。
2. 核心步驟僞代碼¶
// Prim算法僞代碼
function Prim(graph, n):
// n爲頂點數，graph爲鄰接矩陣
key = [INF] * n // key數組：記錄未選頂點到已選集合的最小邊權
parent = [-1] * n // parent數組：記錄生成樹的父節點
key[0] = 0 // 從頂點0開始（起點）
selected = [False] * n // 標記頂點是否已選入S
for i from 0 to n-1:
// 找到未選頂點中key最小的u
u = 找到key最小且selected[u]=False的頂點
selected[u] = True // 將u加入已選集合
// 更新未選頂點的key值
for v from 0 to n-1:
if graph[u][v] > 0 and not selected[v] and graph[u][v] < key[v]:
key[v] = graph[u][v]
parent[v] = u
// 計算總權值
total_weight = sum(key[1..n-1]) // 起點key爲0，其他爲加入的邊權
return total_weight, parent
3. 時間複雜度¶
- 使用鄰接矩陣時，外層循環n次，內層循環n次，總複雜度爲O(n²)（n爲頂點數），適合頂點數較少的稠密圖。
- 若用鄰接表+優先隊列優化，複雜度可降至O(m log n)（m爲邊數），適合稀疏圖。
六、Prim算法的關鍵思想¶
- 貪心選擇：每次選擇“連接已選集合和未選集合的最小邊”，確保局部最優。
- 安全邊性質：無論從哪個頂點開始，最終得到的生成樹總權值一定最小（證明需數學歸納法，初學者可理解爲貪心的合理性）。
七、應用場景¶
- 網絡佈線：城市間鋪設光纖，使總費用最低。
- 電路設計：用最少導線連接所有電子元件，成本最低。
- 交通規劃：規劃道路，使總長度最短且覆蓋所有區域。
總結¶
最小生成樹是貪心算法的經典應用，Prim算法通過“從起點逐步擴展，每次選最小邊”的策略，高效構建出總權值最小的生成樹。理解其核心思想（貪心選擇）和步驟，對解決圖論問題（如最短路徑、網絡優化）至關重要。對於初學者，關鍵是通過具體例子（如本文中的4頂點圖）熟悉算法流程，逐步掌握其實現細節。