最小生成樹 Prim 算法 C++ 實現與圖解

Prim 算法原理

貪心策略：維護已選頂點集 S，每步選擇連接 S 與 V-S 的最小權邊加入。用 `lowcost[v]` 記錄 v 到 S 的最小邊權，`closest[v]` 記錄對應 S 中頂點。

代碼流程

1. 讀入鄰接矩陣（文件 `prim.txt`）。
2. 初始化：S={1}，`lowcost[i]=c[1][i]`，`closest[i]=1`。
3. 重複 n-1 次：在 V-S 中找 `lowcost` 最小的頂點 k，輸出邊 (k, closest[k])，加入 S，更新其餘頂點的 `lowcost`/`closest`。

關鍵數據結構

int lowcost[N+1], closest[N+1];
bool inMST[N+1];

複雜度

鄰接矩陣版 O(n²)，適合稠密圖（n≤6 示例）。稀疏圖可用優先隊列優化至 O(m log n)。

測試輸出示例

圖的矩陣是：
0   6   1   5   INF INF
6   0   5   INF 3   INF
1   5   0   5   6   4
5   INF 5   0   INF 2
INF 3   6   INF 0   6
INF INF 4   2   6   0

生成最小生成樹尋找次序：
把 3 連接上 1
把 6 連接上 3
把 4 連接上 3
把 2 連接上 6
把 5 連接上 2

總結

代碼結構清晰，變量命名直觀，適合初學者理解 Prim 核心邏輯。實戰中需注意圖不連通、邊權重複、0 基/1 基索引等細節。