上一節我們學習了最短路徑算法, 這一節來學習最小生成樹.

最小生成樹(Minimum Spanning Tree, MST)算法是圖論中的一種重要算法, 主要用于在加權無向圖中找到一棵生成樹, 使得這棵樹包含圖中的所有頂點, 并且所有邊的權重之和最小. 這樣的樹被稱為最小生成樹. 最小生成樹廣泛應用于網絡設計, 電路布線等領域. 主要有兩種算法 Prim 算法和 Kruskal 算法.

---

環境要求

本文所用樣例在Windows 11以及Ubuntu 24.04上面編譯通過.

1. Windows: 使用[Visual Studio],
2. Ubuntu: 使用 Clang 18.1.3. (Ubuntu 24.04 系統安裝版本)
3. GCC 無法編譯直接本項目代碼, 因為本文代碼使用了 C++20 Module, 而 GCC 對此支持不完整.

關于 Module 的更多信息, 請參考我之前的博客: CMake 構建 C++20 Module 實例(使用 MSVC)

本項目工程目錄: 圖論代碼

---

Prim 算法

Prim 算法是一種用于尋找加權無向圖的最小生成樹(Minimum Spanning Tree, MST)的經典貪心算法. 它由捷克數學家 Vojtěch Jarník 在 1930 年提出, 后來又被計算機科學家 Robert C. Prim 獨立發現, 并因此得名. Prim 算法特別適用于稠密圖, 即邊的數量接近頂點數平方的情況.

算法步驟

Prim 算法的基本思想是從一個任意選擇的起始頂點開始構建最小生成樹, 逐步將距離當前生成樹最近的頂點加入到生成樹中, 直到所有頂點都被包含為止. 具體步驟如下:

1. 初始化:

   • 選擇任意一個頂點作為起始點, 將其標記為已訪問.
   • 初始化一個優先隊列(或最小堆), 用來存儲尚未訪問的頂點及其與當前生成樹的最短距離. 初始時, 除了起始頂點外, 其他所有頂點的距離設為無窮大(表示還未連接).

2. 迭代過程:

   • 從優先隊列中取出距離當前生成樹最近的頂點 $u$, 并將其標記為已訪問.
   • 對于頂點 $u$ 的所有鄰接頂點 $v$, 如果 $v$ 尚未被訪問, 并且通過 $u$ 到達 $v$ 的距離比之前記錄的距離更短, 則更新 $v$ 的距離值, 并將($v$, 距離)對插入或更新到優先隊列中.

3. 終止條件:

   • 當優先隊列為空, 或者所有頂點都已被訪問時, 算法結束. 此時, 已經找到了最小生成樹.

偽代碼

// 輸入: 一個加權無向圖G = (V, E), 其中V是頂點集合, E是邊集合
// 輸出: 最小生成樹MST的邊集Prim(G, start_vertex):// 初始化MST = []  // 存儲最小生成樹的邊priority_queue = new MinHeap()  // 優先隊列(最小堆), 存儲(權重, 頂點)對visited = new Set()  // 已訪問頂點集合add start_vertex to visited// 將起始頂點的所有鄰接邊加入優先隊列for each neighbor in G.adjacent(start_vertex):if neighbor not in visited:priority_queue.insert((neighbor, weight(start_vertex, neighbor), start_vertex))// 主循環while not priority_queue.isEmpty():// 取出優先隊列中權重最小的邊(u, v)(u, weight_uv, previous_u) = priority_queue.extractMin()if u in visited:continue  // 如果頂點u已經被訪問過, 則跳過// 將頂點u標記為已訪問, 并將邊(previous_u, u)加入MSTadd u to visitedadd (previous_u, u, weight_uv) to MST// 對于頂點u的所有鄰接頂點vfor each (v, weight_u_v) in G.adjacent(u):if v not in visited:// 將(v, 權重)對插入或更新到優先隊列中priority_queue.insertOrDecreaseKey((v, weight_u_v, u))return MST

樣例

考慮下面這個圖, 求它的最小生成樹.

1. 初始化: 假設我們從G開始訪問, 此時標記G為已訪問, 并將與G相鄰的點加入到優先隊列中. 設置其他點的距離為無窮大.
   

2. 迭代過程:

• 從優先隊列中取出(G, C), 將C標記為已訪問, 將G-C這條邊加入到結果集中. 訪問C的鄰接點[A, B, D], 更新他們的距離, 由于新的距離更小, 所以將[A, B, D]加入優先隊列中.
  

• 從優先隊列中取出(C, A). 將A標記為已訪問, 將C-A這條邊加入到結果集中. 訪問A的鄰接點[B, C, D, H], 其中C已經訪問過, 跳過. 將其他的邊加入優先隊列中.

  

• 從優先隊列中取出(A, B). 將B標記為已訪問, 將A-B這條邊加入到結果集中. 訪問B的鄰接點[A, C, D, E], A, C均已訪問, 跳過; 將其他的邊加入優先隊列中.
  

• 從優先隊列中取出(B, E). 將E標記為已訪問, 將B-E這條邊加入到結果集中. 訪問E的鄰接點[B, D, F, H], B以訪問,跳過. 將其他的邊加入優先隊列中.
  

• 從優先隊列中取出(B, D). 將D標記為已訪問, 將B-D這條邊加入到結果集中. 訪問D的鄰接點[A, B, C, E, F], 其中[A, B, C, E]已訪問, 跳過. 將D,F加入優先隊列.
  

• 跳過(C, B), (A,D) , (C,D)

• 從優先隊列中取出(D, F). 將F標記為已訪問, 將D-F這條邊加入到結果集中. 訪問F的鄰接點[D, E], 均已訪問過, 跳過.
  

• 從優先隊列中取出(G, H). 將H標記為已訪問, 將G-H這條邊加入到結果集中. 訪問H的鄰接點[A, E, G], 均已訪問, 跳過.

  

• 其他邊的頂點都已經訪問過, 均被跳過, 算法結束. 得到的最小生成樹如下:

實現細節

typedef std::pair<unsigned, int> EdgeWithWeight;
class Prim {public: