最小生成樹（minimum spanning tree）

想像你必須用電纜連接一組城鎮，讓電力能在任兩者之間流通，而你想花的電纜總量越少越好。你不需要每一對之間都有電纜——你只需要整個網路連成一塊。最便宜的這種電纜集合就是最小生成樹：以最少的總成本連通一切，沒有浪費的多餘連結。

形式上，給定一個連通的無向圖，每條邊有一個權重，生成樹是一個邊的子集，它連接全部 V 個頂點且不含環（故恰有 V-1 條邊）。最小生成樹是總邊權盡可能最小的生成樹。為何恰好 V-1 條邊？更少會使圖不連通；更多必然造出一個環，而環上含有一條可移除的邊，移除它仍保持連通卻降低成本——所以最小解絕不含環。兩個事實驅動每個 MST 演算法：切割性質（跨越頂點任一分割的最便宜邊可安全納入）與環性質（任一環上最貴的邊可安全排除）。

MST 是網路設計的骨幹——以最小成本鋪設光纖、水管或電路走線——它也出現在分群演算法以及旅行推銷員等困難問題的近似方案中。兩個演算法能有效找到一棵：克魯斯卡（用並查集，加入不形成環的最便宜邊）與普林（往外生長一棵樹，總是加入它最便宜的出口邊）。一個值得記住的澄清：MST 為了連通一切而最小化邊權總和；它不是最短路徑樹，後者最小化從單一源點的距離——MST 中兩頂點之間的路徑常不是它們的最短路徑。此外，唯有所有邊權相異時，MST 才唯一。