最小生成樹演算法【圖解】--一文帶你理解什麼是Prim演算法和 ...

Kruskal是另一個計算最小生成樹的演算法，其演算法原理如下。

首先，將每個頂點放入其自身的資料集合中。

然後，按照權值的升序來選擇邊。

MdEditor 最小生成樹演算法【圖解】--一文帶你理解什麼是Prim演算法和Kruskal演算法 語言:CN/TW/HK 時間 2020-04-1416:40:00 部落格園精華區 主題: 最小生成樹 演算法 假設以下情景，有一塊木板，板上釘上了一些釘子，這些釘子可以由一些細繩連線起來。

假設每個釘子可以通過一根或者多根細繩連線起來，那麼一定存在這樣的情況，即用最少的細繩把所有釘子連線起來。

更為實際的情景是這樣的情況，在某地分佈著N個村莊，現在需要在N個村莊之間修路，每個村莊之前的距離不同，問怎麼修最短的路，將各個村莊連線起來。

以上這些問題都可以歸納為最小生成樹問題，用正式的表述方法描述為：給定一個無方向的帶權圖G=(V,E)，最小生成樹為集合T,T是以最小代價連線V中所有頂點所用邊E的最小集合。

集合T中的邊能夠形成一顆樹，這是因為每個節點（除了根節點）都能向上找到它的一個父節點。

解決最小生成樹問題已經有前人開道，Prime演算法和Kruskal演算法，分別從點和邊下手解決了該問題。

Prim演算法 Prim演算法是一種產生最小生成樹的演算法。

該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼克（英語：VojtěchJarník）發現；並在1957年由美國電腦科學家羅伯特·普里姆（英語：RobertC.Prim）獨立發現；1959年，艾茲格·迪科斯徹再次發現了該演算法。

Prim演算法從任意一個頂點開始，每次選擇一個與當前頂點集最近的一個頂點，並將兩頂點之間的邊加入到樹中。

Prim演算法在找當前最近頂點時使用到了貪婪演算法。

演算法描述： 在一個加權連通圖中，頂點集合V，邊集合為E 任意選出一個點作為初始頂點,標記為book,計算所有與之相連線的點的距離，選擇距離最短的，標記book. 重複以下操作，直到所有點都被標記為book：在剩下的點鐘，計算與已標記book點距離最小的點，標記book,證明加入了最小生成樹。

下面我們來看一個最小生成樹生成的過程： 1起初，從頂點a開始生成最小生成樹 2選擇頂點a後，頂點a置成book（塗黑）,計算周圍與它連線的點的距離： 3與之相連的點距離分別為7,4，選擇C點距離最短，塗黑C，同時將這條邊高亮加入最小生成樹： 4計算與a,c相連的點的距離（已經塗黑的點不計算），因為與a相連的已經計算過了，只需要計算與c相連的點，如果一個點與a,c都相連，那麼它與a的距離之前已經計算過了，如果它與c的距離更近，則更新距離值，這裡計算的是未塗黑的點距離塗黑的點的最近距離，很明顯，b和a為7，b和c的距離為6，更新b和已訪問的點集距離為6，而f,e和c的距離分別是8,9，所以還是塗黑b,高亮邊bc： 5接下來很明顯，d距離b最短，將d塗黑，bd高亮： 6f距離d為7，距離b為4，更新它的最短距離值是4，所以塗黑f，高亮bf： 7最後只有e了： 針對如上的圖,程式碼例項如下(配合註釋理解)： #include #defineINF10000 usingnamespacestd; constintN=6; boolbook[N]; intdist[N]={0}; intgraph[N][N]={{INF,7,4,INF,INF,INF},//INF代表兩點之間不可達 {7,INF,6,2,INF,4}, {4,6,INF,INF,9,8}, {INF,2,INF,INF,INF,7}, {INF,INF,9,INF,INF,1}, {INF,4,8,7,1,INF} }; intPrim(intcur){//選擇起始點 intindex=cur; intsum=0; inti=0; intj=0; cout<graph[index][j]) dist[j]=graph[index][j]; } } cout< #defineN7 usingnamespacestd; structNode{ intval;//長度 intstart;//邊的起點 intend;//邊的終點 }; NodeV[N]; intcmp(constvoid*a,constvoid*b){ return(*(Node*)a).val-(*(Node*)b).val; } //edge儲存結點屬性 intedge[N][3]={{0,1,3}, {0,4,1}, {1,2,5}, {1,4,4}, {2,3,2}, {2,4,6}, {3,4,7} }; intfather[N]={0}; intcap[N]={0}; //初始化集合，讓所有的點都各成一個集合，每個集合都只包含自己 //並查集初始化，先令每個結點的父節點為自己 voidmake_set(){ for(inti=0;i