1. 首頁 > 生活 > >

最小生成樹prim算法圖解 prim算法求最大生成樹

小知識



文章插圖
最小生成樹prim算法圖解 prim算法求最大生成樹

文章插圖
最小生成樹
假設你是電信的實施工程師，需要為一個鎮的九個村莊架設通信網絡做設計，村莊位置大致如圖，其中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我們已經走過，走過的路標記為紅色 。
第二步但是接下來我們該如何走呢？其實我也很迷茫，既然不知道，那就選當前能走的路的最近的一條吧 ?，F在我們有兩種選擇，第一種從V0出發，第二種從V1出發，分別產生的可能性如下（綠色）：
選一條最短的
接下來看V5和V1能到達哪里？然后繼續尋找…直到最后一個頂點被連通（從0-n的循環）其實這就是普里姆算法的核心思路，既然思路知道了，我們對比算法來講解吧 。
普里姆（Prim）算法
【最小生成樹prim算法圖解 prim算法求最大生成樹】在講之前我們先選一種圖的存儲結構吧，這里我們用圖的鄰接矩陣存儲結構來講解 。
39-47行就是上面講述的尋找我們當前頂點鄰接的最小權值邊，(用之前的例子講：第一次循環是頂點V0所有的邊，第二次循環除去邊(V0,V1)以后頂點V0和V1所有的邊，以此類推）而51-58行則是更新當前所有可能的邊的最小權值 。算法比較晦澀的是adjvex[MAXVEX]和lowcost[MAXVEX]的理解，一旦理解這兩個數組的含義，這個算法也就沒難點了 。
由代碼中的循環嵌套可得知此算法的時間復雜度為O(N^2) 。