普林演算法（Prim's algorithm）

克魯斯卡演算法在整張地圖上四處撒下便宜的電纜並合併孤島，普林演算法則從一個起始城鎮往外生長出單一個連通團塊，像潑出的水擴散。它每一刻都持有一棵連通的樹，並問：在所有從我目前的樹通向尚未納入之城鎮的電纜中，哪一條最便宜？它加入那一條，吞下新城鎮，並重複直到每個城鎮都被吸收。

具體上：挑任一起始頂點；它的樹起初只含那個頂點。為每個樹外的頂點維護一條把它連到樹最便宜的單邊（用以該成本為鍵的優先佇列）。重複 V-1 次：取出連接成本最小的樹外頂點，把它與那條邊加入樹，再更新它鄰居的最佳連接成本。正確性是切割性質的反覆套用：目前建好的樹是切割的一側，而普林總是加入跨越那個切割最小權重的邊，這正是切割性質保證的安全邊。用二元堆積成本為 O(E log V)；用費氏堆積為 O(E + V log V)，在稠密圖上漸進更佳。

普林傾向在稠密圖（邊多）上勝出，那裡克魯斯卡預先把所有邊排序的代價昂貴，而克魯斯卡在稀疏圖或邊已排序時最自然。兩者都產生最小生成樹；只是生長方式不同——普林是一棵擴張的樹，克魯斯卡是多片合併的森林。一個常見的混淆要釐清：普林看起來幾乎與戴克斯特拉演算法一模一樣，甚至用相同的優先佇列機制，但它最小化的鍵不同。普林依「把頂點接到樹最便宜那條單邊」的權重把頂點排入佇列；戴克斯特拉依「從源點起的總距離」排入佇列。骨架相同、量不同——而它們解決不同的問題。