話說最小生成樹的prim演算法和kursual演算法的區別?

01-03

prim用二叉堆優化是 $O((E +V)logV)$ 複雜度，Kruskal是 $O(ElogE + E*A(V) + V)$ 的複雜度。A是阿克曼函數的反函數，再加V因為並查集要初始化...

要是prim用fib堆的話，應該是 $O(E + VlogV)$ ，因為fib堆update一次是 $O(1)$ 的。。。

好久不搞這個了，不知道是不是說錯了。。。

當然prim改一改還可以 $V^2$ 求次小生成樹。。。

作者：許鐵-巡洋艦科技

鏈接：從最小生成樹演算法談起 - 混沌巡洋艦 - 知乎專欄

來源：知乎

著作權歸作者所有。商業轉載請聯繫作者獲得授權，非商業轉載請註明出處。

給你一個有向帶權圖，需要你刪除一些邊，使這個圖變成一個權值最小的樹，這就是圖論入門時最經典的最小生成樹問題了，很多人都學過該演算法。那我們要談什麼了。

首先說的是該演算法在實際中是很有用的，不止是將高速公路問題中的城市看做圖中的頂點，城市之間修建的道路看做圖中頂點之間的邊，城市之間所修修建的公路的長度看做是圖中個邊上的權值。這樣我們就把高速公路問題轉換成了求一個有向連通網的最小生成樹問題。

我們甚至可以將大腦中的神經元看成是一個圖，而學習的過程就是去除無用的神經元連接，從而生成一顆最小生成樹的過程，這其中也會有用到相應的，當然人腦內發生的事情可沒有那麼簡單，不過實驗已證明，人腦中的神經元連接，是童年時最為豐富，成年後連接減少，但這些連接穩固而快捷，學習的過程，就是去除那些不常在一起的連接。將思維的背景放寬，古代的帝王之術，也要求其統治下的官僚體系維持為一顆最小生成樹，不能要官員自己有相互的勾結（形成環），官官相護。這就是為什麼帝王要要打擊腐敗的原因，雖然他們做的都不夠成功，這與其方法固然有關，這之後還要說起。

再說解決該問題的倆種經典方法之前，我先說說我拿到該問題時想到的方法，「破圈法」即見圈就破，破圈時去除圈裡權值最大的邊，具體來看，就是先將所有的邊按權值進行降序排列.之後對於取出的每一個邊來說,判斷其連接的兩個結點是否具有圈.(即先刪除次邊,然後判斷這兩個結點是否連接,之後對刪除的邊進行恢復)對於有圈的,將這條邊刪除,否則,往下查找.演算法結束:當剩下的邊=結點數-1的時候。學過演算法的可以分析下該方法的複雜度，肯定比Prim和kruskal都差不止一個數量級，我認為該方法是O（n^3)級的，n為圖中點的個數）。

回想起來，我在初學演算法時為什麼會想到這樣的方法，多半是因為這種方法夠直接，目的是要圖中沒有圈，那就破圈好了。但是在圖上的信息不明時，破圈實際是一種好策略，如果你面對的一張圖，但你只能看到圖的一部分，而每一次觀察都要消耗能量，記憶住圖上點自己的信息也需要消耗能量，那麼當你看到一個圈時，將圈中權值較大的邊破除，確實是一個好辦法，這也就是中國古代帝王們做的，他們對龐大官僚系統，尤其當官僚系統成熟後，所能掌握的信息甚少，只能頭痛醫頭，腳痛醫腳。該問題也可以成為啟發式演算法研究的一個開放問題，對於一個agent，給點其信息存儲空間，限定其觀察信息的方式，使該agent無法在一開始就擁有全局信息，看該agent如何行動，以求得相對較小的生成樹。

接下來說該問題的倆種標準方法，Kruskal演算法：所有的頂點放那，每次從所有的邊中找一條代價最小的，同時保證加入的邊不產生圈。Prime普利姆演算法求最小生成樹時候，和邊數無關，只和定點的數量相關，所以適合求稀疏圖的最小生成樹，時間複雜度為O（n*n）。Prim:演算法：在U，（V – U）之間的邊，每次找一條代價最小的，具體的說，1.將一個圖的頂點分為兩部分，一部分是最小生成樹中的結點（A集合），另一部分是未處理的結點（B集合）。2.首先選擇一個結點，將這個結點加入A中，然後，對集合A中的頂點遍歷，找出A中頂點關聯的邊權值最小的那個（設為v），將此頂點從B中刪除，加入集合A中。3.遞歸重複步驟2，直到B集合中的結點為空，結束此過程。4.A集合中的結點就是由Prime演算法得到的最小生成樹的結點，依照步驟2的結點連接這些頂點，得到的就是這個圖的最小生成樹。Prim適合稠密圖，因此通常使用鄰接矩陣儲存，而Kruskal多用鄰接表。

圖： Prime 演算法示意

為什麼要說這倆種演算法了，其實我想對比的是這倆種方法背後的世界觀。簡而言之，Prime演算法背後是日拱一卒的保守主義的世界觀，在演算法開始時不假設已知全部信息，而將圖分為一個已知的A集合，（包含最小生成樹）以及一個B集合（將要加入最小生成樹）的集合。而Kruskal演算法則要求對所有邊按照權值進行排序，然後再重頭開始貪心的構建生成樹，背後是建構主義的世界觀。這也就對於了現實社會，當面對的情況越發複雜，我們需要改變打倒重來的策略，切換到保守主義的世界觀上，不可一日不拱卒。

而破圈法則是直線思維的產物，其背後的價值觀是屬於前現代化時代的。這也就解釋了為什麼當官僚機構發展到了晚期，例如嘉慶年間，儘管嘉慶是個道德很完善，也很勤政的皇帝，但當他面對盤根錯節的官僚網路時，如救火隊員般顧此失彼。嘉慶還在用著「破圈法」去在官僚集團這張網上去一個個的纏鬥。這也可以解釋為什麼計劃經濟無法應對日益複雜的環境，即使在靜態的環境，當你做好了排序，你需要的存儲空間，時間成本，都遠高於將世界分為已知與未知，並不斷擴展已知世界的動態開放的經濟系統。

接下來想說說Prime 和Kruskal 演算法並行化的問題，應該是Prime 的並行化更加有效率，Prime演算法可以自然的套用Map -Reduce的框架，基於MapReduce的圖聚類演算法的研究與實現，這裡就有一篇實現分散式環境下的MST（最小生成樹）的論文。而Kruskal在並行化時需要先進行排序，生成樹的時候其各個節點間的通信量也會很大，因為各個節點間的關係是相互影響的。這並不令人意外，這倆種演算法底層的世界觀就決定了這個。

最後我想說的是，Kruskal演算法本質是貪心演算法，而Prime演算法是動態規劃。所謂動態規劃，你可以給7歲的小孩說清，你問孩子1+1等於幾，她告訴你2，那麼你問她2+1了？她回答說3，然後你問她那你算2+1時還用不用再算1+1=2，她肯定會說不用了，你已經知道1+1=2了。其實動態規劃就是記住自己已知的未知的，不要混淆已知與未知的界限，同時不斷利用已知的知識以及自己對當前情況的判斷去擴展已知的花式技法。重要的是你要有一個起點，一個能夠不斷等新已知與未知邊界的迭代函數。這既是動態規劃演算法的精要，也是保守主義的核心價值觀。

「真誠讚賞，手留余

複雜度，演算法步驟上面已經說的很清除了

我來說說演算法思想：其實兩者都是貪心的思想，只不過考慮的角度不同：

Prim演算法從頂點的角度出發，每次選擇距離當前節點最近的節點加入，直到所有節點都加入。

Kruskal演算法從邊的角度出發，每次總是選擇權重最小的邊加入，直到加入n-1條邊為止。（如果加入一條邊後出現迴路，skip這條邊）。

從代碼實現的角度：

Prim演算法需要維持一個堆數據結構（實際實現中用priority_queue比較多）

Kruskal演算法需要union-find的數據結構

對於最小生成樹，有兩種演算法可以解決。一種是Prim演算法，該演算法的時間複雜度為O(n2)，與圖中邊數無關，該演算法適合於稠密圖，而另外一種是Kruskal，該演算法的時間主要取決於邊數，它較適合於稀疏圖。

Prim演算法：設圖G =（V，E），其生成樹的頂點集合為U。 ①、把v0放入U。 ②、在所有u∈U，v∈V-U的邊(u，v)∈E中找一條最小權值的邊，加入生成樹。 ③、把②找到的邊的v加入U集合。如果U集合已有n個元素，則結束，否則繼續執行②。

Kruskal演算法與Prim演算法的不同之處在於，Kruskal在找最小生成樹結點之前，需要對所有權重邊做從小到大排序。將排序好的權重邊依次加入到最小生成樹中，如果加入時產生迴路就跳過這條邊，加入下一條邊。當所有結點都加入到最小生成樹中之後，就找出了最小生成樹。

參見最小生成樹—Prim、Kruskal、Sollin(Boruvka)