三種最小生成樹算法的簡要比較：Kruskal算法, 破圈法(管梅谷), Prim算法

本文針對之前常常弄混Kruskal算法, 破圈法(管梅谷), Prim算法這三種算法的問題，僅僅簡單地總結Kruskal算法, 破圈法(管梅谷), Prim算法在求最小生成樹時的思路的差別。

如果目的是為了比較這三種算法的複雜度、優缺點等進階的差別，請參考其他文章。

1. Kruskal算法

克魯斯克爾(Kruskal):1928年生，一家3弟兄都是數學家，1954年 在普林斯頓大學獲博士學位，導師是著名的ErdÖs,他大部分研究工作是 數學和語言學，主要在貝爾實驗室工作。1956年發表包含克魯斯 克爾算法論文，使他名聲大振。

思路：從G中的最小邊開始，進行避圈式擴張。

2. 破圈法(管梅谷)

管梅谷（１９３４－）。我國著名數學家，曾任山東師範大學校 長。中國運籌學會第一、二屆常務理事，第六屆全國政協委員。從 事運籌學及其應用的研究，對最短投遞路線問題的研究取得成果 ， 冠名為中國郵路問題，該問題被列入經典圖論教材 和著作。

思路：從賦權圖G的任意圈開始， 去掉該圈中權值最大的一條邊，稱為破圈。不斷破圈，直到G中沒 有圈為止，最後剩下的G的子圖為G的最小生成樹。

3. Prim算法

Prim(1921---) 1949年在普林斯頓大學獲博士學位，是Sandia公司副總裁。

從G中的任意點開始，選擇關聯的權重最小且不生成圈的邊添加，直到得到最小生成樹。

總結：(下面的話是對的，但原因尚不清楚，建議參考拟陣相關知識)

這三個算法都是基于貪婪算法的思想設計的(一個從最小邊開始，一個從任意全開始，一個從任意點開始)，每一步選擇局部最優，進而期望得到全局最優的算法。

• 如果組合優化問題滿足拟陣的結構，則可以使用适當的貪婪算法得到最優解，如這三個算法。
• 不滿足拟陣結構的問題，貪婪算法可能得不到最優解，如旅行商問題(TSP).