普林與克魯斯卡的貪婪觀點（Prim and Kruskal as greedy）

假設你必須用道路連接一組城鎮使人人可達，按你修築的道路總長付費，而你想要最便宜的這種網路。沒有浪費迴路、最便宜的連接網路就是最小生成樹。兩個著名演算法——克魯斯卡與普林——都能找到一棵，且兩者都是純貪婪：它們一次又一次加入能安全加入的最便宜的邊，從不反悔。

克魯斯卡：把所有邊由便宜到昂貴排序；依序掃過；加入每條邊，「除非」它會與已選的邊形成環；當樹生成全部頂點時停止。普林：從一個起點頂點長出單一棵樹，每步加入連接樹與樹外新頂點且最便宜的邊。兩者都是貪婪，因為每步都取局部最便宜的合法邊。為何「局部最便宜」能抵達「全域最便宜」的樹？切割性質：對任何把頂點分成兩側的方式，跨越該切割最便宜的邊可安全納入某個最小生成樹。其背後的交換論證：若某個最小生成樹省略了那條最便宜的跨越邊，它必以一條較貴的邊跨越該切割；把貴的跨越邊換出、便宜的換入——仍是生成樹、且不更貴——故某個最小生成樹含有那條便宜邊。克魯斯卡與普林只是以特定順序套用這條「安全邊」規則，故兩者皆正確。

最小生成樹是完美貪婪問題的更深層原因是：它的獨立集——無環邊集（森林）——構成一個擬陣（圖擬陣），而擬陣貪婪定理保證在那裡貪婪最佳。這正是為何貪婪對最小生成樹可行，卻對例如旅行推銷員巡迴不可行。注意本領域的邊界：切割性質、環性質，以及讓克魯斯卡高效的並查集資料結構，屬於專門的最小生成樹領域；這裡專注於為何這些演算法是正確的貪婪方法。