最小生成樹
假設你是電信的實施工程師，需要為一個鎮的九個村莊架設通信網絡做設計，村莊位置大致如圖，其中V0~V8是村莊，之間連線代表可達距離，數字代表里程數。領導要求你用最小成本完成這次任務，如何做？
顯然這是一個帶權值的圖，即是網結構。所謂最小成本，就是n個頂點，用n-1條邊把一個連通圖連接起來，並使得權值和最小。
定義
一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只有足以構成一個樹的n-1條邊——我們把構造連通網的最小代價生成樹稱為最小生成樹（Minimum Cost Spanning Tree）
我想在講算法之前我們先做一下思考，我們如何找到該條路徑？
- 我們是否可以從某一點開始尋找呢？
- 我們從哪一個地點作為起始點呢？
- 我們找到第一個點以後如何找最小權值的邊呢？
第一步
我想先從概念下手：
首先，因為一個連通圖含有圖中全部頂點，所以我們可以從任意頂點出發（開始尋找），最終結果應該是一致的。但是為了方便講述我還是想從V0開始出發（此時我們站在V0）。
起始點找到了，那麼如何找起始點到第一個頂點的邊呢？
逆着想一下，與V0鄰接有且僅有兩條邊（V0,V1）,（V0,V5），我們必須要選一條（因為我們必須要到達V0），所以我們乾脆在V0的兩條邊上選一條到達V0。
我們站在V0巡視了一下兩條邊，然後選擇了（V0,V1）（此處有判斷）。
然後我們記錄一下V0我們已經走過，走過的路標記為紅色。
第二步
但是接下來我們該如何走呢？
其實我也很迷茫，既然不知道，那就選當前能走的路的最近的一條吧。
現在我們有兩種選擇，第一種從V0出發，第二種從V1出發，分別產生的可能性如下（綠色）：
選一條最短的
接下來看V5和V1能到達哪裡？然後繼續尋找…直到最後一個頂點被連通（從0-n的循環）
其實這就是普里姆算法的核心思路，既然思路知道了，我們對比算法來講解吧。
普里姆（Prim）算法
在講之前我們先選一種圖的存儲結構吧，這裡我們用圖的鄰接矩陣存儲結構來講解。
- 39-47行就是上面講述的尋找我們當前頂點鄰接的最小權值邊，(用之前的例子講：第一次循環是頂點V0所有的邊，第二次循環除去邊(V0,V1)以後頂點V0和V1所有的邊，以此類推）
- 而51-58行則是更新當前所有可能的邊的最小權值。
- 算法比較晦澀的是adjvex[MAXVEX]和lowcost[MAXVEX]的理解，一旦理解這兩個數組的含義，這個算法也就沒難點了。
由代碼中的循環嵌套可得知此算法的時間複雜度為O(N^2)。
原創文章，作者：投稿專員，如若轉載，請註明出處：https://www.506064.com/zh-hant/n/222818.html
微信掃一掃 
支付寶掃一掃 