最小生成樹演算法——Kruskal演算法、Prim演算法

需要排序的次數不同：Kruskal演算法是在演算法開始前對所有邊的權值進行排序，但就這一次排序。

Prim演算法是每次挑選節點時，都需要進行排序，但每次排序 ... 最小生成樹演算法——Kruskal演算法、Prim演算法、堆優化的Prim演算法 首頁 最新 HTML CSS JavaScript jQuery Python3 Python2 Java C C++ Go SQL 首頁 最新 Search 最小生成樹演算法——Kruskal演算法、Prim演算法、堆優化的Prim演算法 2019-02-11254 什麼叫最小生成樹？ 已知一個無向連通圖，那麼這個圖的最小生成樹是該圖的一個子圖，且這個子圖是一棵樹且把圖中所有節點連線到一起了。

一個圖可能擁有多個生成樹。

一個帶權重的無向連通圖的最小生成樹（minimumspanningtree），它的權重和是小於等於其他所有生成樹的權重和的。

生成樹的權重和，是把生成樹的每條邊上的權重加起來的和。

一顆最小生成樹有多少條邊？ 已知帶權重無向連通圖有V個節點，那麼圖的最小生成樹的邊則有V-1條邊。

Kruskal演算法 思路 步驟如下： 1.以每條邊的權重排序，排非降序。

2.每次挑選一個權重最小的邊，檢查將其加入到最小生成樹時，是否會形成環（一顆樹是沒有環的啊） 3.重複步驟2直到最小生成樹中有V-1條邊。

在步驟2中，我們使用Union-Findalgorithm來檢測加入邊是否會形成環。

顯而易見，Kruskal演算法是一種貪心演算法，以下面例子開始實際講解。

此圖包含9個節點和14條邊，所以該圖的最小生成樹會有（9-1）=8條邊。

該示例的處理步驟如下： 1.挑選邊7-6，此時沒有環形成，則加入這條邊。

2.挑選邊8-2，此時沒有環形成，則加入這條邊。

3.挑選邊6-5，此時沒有環形成，則加入這條邊。

4.挑選邊0-1，此時沒有環形成，則加入這條邊。

5.挑選邊2-5，此時沒有環形成，則加入這條邊。

6.挑選邊8-6，此時有環形成，則不加入這條邊。

7.挑選邊2-3，此時沒有環形成，則加入這條邊。

8.挑選邊7-8，此時有環形成，則不加入這條邊。

9.挑選邊0-7，此時沒有環形成，則加入這條邊。

10.挑選邊1-2，此時有環形成，則不加入這條邊。

11.挑選邊3-4，此時沒有環形成，則加入這條邊。

執行到這裡，已經包含了8條邊，所以演算法終止。

程式碼 fromcollectionsimportdefaultdict classGraph: def__init__(self,vertices): self.V=vertices#頂點的數量 self.graph=[]#二維list用來存邊的起點、終點、權重 #新增每條邊 defaddEdge(self,u,v,w): self.graph.append([u,v,w]) #遞迴找到每個節點所在子樹的根節點 deffind(self,parent,i): ifparent[i]==i: returni returnself.find(parent,parent[i]) #聯合兩顆子樹為一顆子樹，誰附在誰身上的依據是rank defunion(self,parent,rank,x,y): xroot=self.find(parent,x) yroot=self.find(parent,y) #進行路徑壓縮 if(xroot!=parent[x]): parent[x]=xroot if(yroot!=parent[y]): parent[y]=yroot #將較小rank的子樹附在較大rank的子樹上去 ifrank[xroot]rank[yroot]: parent[yroot]=xroot #若rank一樣，程式這裡寫死即可 else: parent[yroot]=xroot rank[xroot]+=1 #主函式用來構造最小生成樹 defKruskalMST(self): result=[]#存MST的每條邊 i=0#用來遍歷原圖中的每條邊，但一般情況都遍歷不完 e=0#用來判斷當前最小生成樹的邊數是否已經等於V-1 #按照權重對每條邊進行排序，如果不能改變給的圖，那麼就建立一個副本，內建函式sorted返回的是一個副本 self.graph=sorted(self.graph,key=lambdaitem:item[2]) parent=[];rank=[] #建立V個子樹，都只包含一個節點 fornodeinrange(self.V): parent.append(node) rank.append(0) #MST的最終邊數將為V-1 whileerank[yroot]: parent[yroot]=xroot #Ifranksaresame,thenmakeoneasrootandincrementitsrankbyone else: parent[yroot]=xroot rank[xroot]+=1 Prim演算法 思路 prim演算法也是一種貪心演算法。

開始時，最小生成樹（MST）為空（不包含任何節點），然後維持兩個集合，一個集合是包含已經進入MST中的節點，另一個集合時包含未被加入到MST中的節點。

在演算法的每個步驟中，從連線這兩個集合的所有邊中，挑選一個最小權值的邊。

在挑選之後，要把這條邊上不在MST中的另一個節點加入到MST中去。

注意，連線這兩個集合的所有邊，肯定是一個節點在MST集合中，另一個節點在非MST集合中。

Prim演算法的思想：首先要考慮連通性，最小生成樹中的每條邊，在原圖中肯定也是已存在的邊。

然後通過連線MST集合和非MST集合中的節點來生成最小生成樹。

在連線的過程中，必須挑選最小權值的邊來連線。

Prim演算法的步驟：（節點個數為V） 1.建立一個集合mstSet用來判斷是否所有節點都已經被包括到MST中，當集合大小為V時，則MST包括了所有節點。

2.根據原圖邊的權重為每個節點分配一個key值，初始時每個節點的key值都是無窮大，當0節點作為第一個被挑選的節點時，將0節點的key值賦值為0。

3.只要當mstSet還沒有包含所有節點時，就重複以下步驟： …(i)選擇一個節點u，u是非MST集合中key值最小的那個節點。

…(ii)把u加入到mstSet。

…(iii)更新u節點的鄰接點v的key值。

遍歷u的鄰接點v，每當邊u-v的權值小於v的key值時，就更新v的key值為邊u-v的權值，同時記錄下v的父節點為u。

實際例子處理步驟： 已知帶權值的無向連通圖如下： 初始時，mstSet為空，每個節點的key值為{0,INF,INF,INF,INF,INF,INF,INF}，INF代表無窮大。

現在挑選具有最小key值的節點，所以0節點被挑選，將其加入到mstSet中。

所以mstSet現在為{0}。

在加入節點到mstSet中後，更新鄰接點的key值，0的鄰接點為1和7，然後1和7的key值分別被更新為4和8。

圖中只顯示出key值為有限值的節點。

綠色節點代表在mstSet集合中的節點。

挑選不在mstSet集合中的key值最小的那個節點。

1被挑選且加入到mstSet中去，mstSet變成{0,1}。

更新1的鄰接點的key值，所以2的key值變成8. 挑選不在mstSet集合中的key值最小的那個節點。

看上圖發現，我們既可以挑選2節點，也可以挑選7節點，此時挑選7節點。

mstSet變成{0,1,7}。

更新7的鄰接點的key值，所以6和8的key值分別變成7和1。

挑選不在mstSet集合中的key值最小的那個節點。

6被挑選且加入到mstSet中去，mstSet變成{0,1,7,6}。

更新6的鄰接點的key值，所以5和8的key值分別變成2和6。

重複以上步驟，直到mstSet包含了所有的節點。

程式碼 classGraph(): def__init__(self,vertices): self.V=vertices self.graph=[[0forcolumninrange(vertices)] forrowinrange(vertices)] #使用parent[]來列印MST defprintMST(self,parent): print("Edge\tWeight") #列印每個點與父節點的邊就可以了，注意根節點不用列印 foriinrange(1,self.V): print(parent[i],"-",i,"\t",self.graph[i][parent[i]]) #在非MST集合中選擇具有最小key值的節點 defminKey(self,key,mstSet): min=float("inf") forvinrange(self.V): ifkey[v]0代表v是u的鄰接點 #mstSet[v]==False代表當前節點還沒有加入到MST中 #key[v]>self.graph[u][v]只有新距離比當前記錄距離要小時更新 #兩種情況，一是key[v]為無窮，肯定更新；二是key[v]為常數，但新距離更小 if(self.graph[u][v]>0)and(mstSet[v]==False)and(key[v]>self.graph[u][v]): key[v]=self.graph[u][v]#更新距離 parent[v]=u#更新父節點 self.printMST(parent) g=Graph(5) g.graph=[[0,2,0,6,0], [2,0,3,8,5], [0,3,0,0,7], [6,8,0,0,9], [0,5,7,9,0], ] #圖的表示用鄰接矩陣，根據矩陣元素的索引判斷是哪條邊 #根據矩陣元素判斷該邊是否有邊，不為0代表有邊 g.primMST(); 注意，對節點u的鄰接點v進行key值的減小，這裡一般稱為對v進行鬆弛操作，鬆弛操作類似最短路徑演算法的鬆弛操作。

思考與總結 Kruskal演算法因為是從所有邊中挑選權值最小的邊，所以在每次加入邊的時候，需要判斷是否形成環。

Prim演算法相比Kruskal演算法的優勢在於，Prim演算法考慮邊的連通性（Kruskal從所有邊中挑選，而Prim從連通的邊中挑選）。

而且Prim演算法不用考慮在加入節點的過程中，是否會形成環。

形成環的條件是圖中有回邊（backedge），但每次挑選節點加入mstSet中時，都是從非MST集合中挑選，所以不可能讓更新後的最小生成樹形成回邊。

需要排序的次數不同：Kruskal演算法是在演算法開始前對所有邊的權值進行排序，但就這一次排序。

Prim演算法是每次挑選節點時，都需要進行排序，但每次排序都是一部分邊就行。

明顯可見，Prim演算法排序的總次數，肯定比Kruskal演算法排序的總次數要多。

Kruskal演算法時間複雜度：為O(ElogE)或者O(ElogV)。

排序所有邊需要O(ELogE)的時間，排序後，還需要對所有邊應用Union-find演算法，Union-find操作最多需要O(LogV)時間，再乘以邊數E，所以就是O(ElogV)。

所以總共需要O(ELogE+ELogV)時間。

由於一般圖中，邊數E是大約為O(V2V2):，所以O(LogV)和O(LogE)是大約一樣的。

PS:這句話從Kruskal演算法看來的，我也沒看懂，但有了這兩個條件，推導過程如下： 所以，時間複雜度為O(ElogE)或者O(ElogV)，一般認為是前者。

Prim演算法時間複雜度：為O(V2V2)。

如果輸入的圖，用鄰接表表示，且使用了二叉堆（binaryheap）的資料結構，複雜度能降到O(ElogV)或O(VlogV)。

適用範圍：Prim一般用於稠密圖，因為其複雜度為O(VlogV)，則主要取決於點數，而與邊數無關。

Kruskal一般用於稀疏圖，因為其複雜度為O(ElogE)，則主要取決於邊數，而與點數無關。

堆優化的Prim演算法 思路 上面提到，如果使用二叉堆，prim演算法的複雜度能降到O(ElogV)，接下來本文將講解使用堆優化的Prim演算法。

之前實現的這個Prim演算法，是用鄰接矩陣表示圖。

而堆優化的Prim演算法，將用鄰接表來表示圖，且使用最小堆來尋找，連線MST集合和非MST集合的邊中，最小權值的那條邊。

基本思想：基本思想和原Prim演算法大體相同，但此演算法是，根據鄰接表，通過廣度優先遍歷（BFS）來遍歷所有節點，遍歷的總操作為O(V+E)次數。

同時使用最小堆儲存非MST集合中的節點，每次遍歷時用最小堆來選擇節點。

最小堆操作的時間複雜度為O(LogV)。

基本步驟： 1.建立一個大小為V的最小堆，V是圖的節點個數。

最小堆的每個元素，儲存的是節點id和節點的key值。

2.初始化時，讓堆的第一個元素作為最小生成樹的根節點，賦值根節點的key值為0。

其餘節點的key值賦值為無窮大。

3.只要最小堆不為空，就重複以下步驟： …(i)從最小堆中，抽取最小key值的節點，作為u。

…(ii)對於u的每個鄰接點v，檢查v是否在最小堆中（即還沒有加入到MST中）。

如果v在最小堆中，且v的key值是大於邊u-v的權值時，就更新v的key值為邊u-v的權值。

實際例子處理步驟： 與上面Prim演算法的一樣。

程式碼 程式碼來自Prim’sMSTusingminheap，稍微修改，因為原本是python2的程式碼，且加上了中文註釋方便讀者理解。

已知帶權值的無向連通圖如下： fromcollectionsimportdefaultdict classHeap(): def__init__(self): self.array=[]#用陣列形式儲存堆的樹結構 self.size=0#堆內節點個數 self.pos=[]#判斷節點是否在堆中 defnewMinHeapNode(self,v,dist): minHeapNode=[v,dist] returnminHeapNode #交換堆中兩個節點 defswapMinHeapNode(self,a,b): t=self.array[a] self.array[a]=self.array[b] self.array[b]=t defminHeapify(self,idx):#遞迴，下濾根節點 #符合完全二叉樹中，索引規律 smallest=idx left=2*idx+1 right=2*idx+2 print(self.array,self.size) print(self.pos) ifleft0andself.array[i][1]=size時，代表節點i已經不在堆中了，而是已經加入到了最小生成樹中了。

以當前例子分析，初始時，pos為[0,1,2…8]。

..5)在minHeap物件中的array陣列：用這個陣列來表示堆，由於之前提到的完全二叉樹的良好性質，大小為V。

其索引i代表的是堆中的各個位置，而array[i]代表的是，在堆的i索引位置存的節點以及該節點的key值。

且array[i]需要和size配合使用：對於小於size的i，這些array[i]都是堆中的元素；對於大於等於size的i，這些array[i]都不能看因為沒有意義（注意它們不是加入到MST中的元素，因為程式是這麼設計）。

初始時，array陣列是符合最小堆定義的，因為堆的0位置元素的key值為0，其餘位置元素的key值為INF。

而且值得注意的是，在程式執行過程中，一般都是這個堆除了前幾個元素的key值都為有限數字以外，其餘元素的key值都為INF，這是因為，連線MST集合與非MST集合的邊是有限的，屬於非MST集合的節點組成了堆，但只有這些邊在非MST集合那頭的節點的key才會是有限數字。

再看程式中函式的功能： ..1)PrimMST函式：主函式，用來構造最小生成樹，生成必須的資料結構，並對其進行初始化。

其中的while迴圈是其主要功能，每次迴圈中，抽取最小堆的根節點（即最小的key值的節點，此時最小堆已構建好）作為u，遍歷u的鄰接表即遍歷u的每個鄰接點v，判斷是否需要更新v的key值，是則更新key值，即對v進行鬆弛操作。

..2)extractMin函式：抽取最小堆的根節點root作為返回值，然後將root替換為堆中最後一個元素lastNode，size大小減小1，在函式的最後執行minHeapify函式，最後return。

..3)minHeapify函式：在替換root替換為堆中最後一個元素lastNode後，需要對堆重新構造，使其保持最小堆性質。

此函式是一個遞迴函式，功能為將根節點在堆中下濾，遞迴到不能下濾為止。

..4)decreaseKey函式：用於更新u的鄰接點v的key值，而且顧名思義，肯定是減小key值。

此函式功能為，將某更新過key值的節點在堆中上濾，此函式不用設計成遞迴的原因是，上濾最多能到達根節點，而下濾是沒有一個明確的終點的。

minHeapify函式和decreaseKey函式都是為了，在改變堆後，使得堆保持最小堆的性質。

時間複雜度分析： 觀察PrimMST函式的內部迴圈，因為在遍歷節點的過程類似BFS，所以是被執行O(V+E)次數。

在內部迴圈中，decreaseKey函式被執行，其執行時間為O(LogV)。

所以總時間為O(E+V)*O(LogV)=O(ELogV)，因為一般連通圖中V=O(E)。

相關文章 最小生成樹演算法【圖解】--一文帶你理解什麼是Prim演算法和Kruskal演算法 無向帶權圖的最小生成樹演算法——Prim及Kruskal演算法思路 圖的兩種最小生成樹演算法之C++封裝 最小生成樹演算法——Kruskal演算法、Prim演算法、堆優化的Prim演算法 每日一省之————加權無向圖的最小生成樹演算法（Prim/Kruskal演算法） 最小生成樹演算法程式碼 Kruskal演算法求最小生成樹-演算法設計與分析實驗3 最小生成樹演算法(python實現) 資料結構基礎溫故-5.圖（中）：最小生成樹演算法 最小生成樹演算法的兩個重要屬性CycleProperty和PartitionProperty 最小生成樹演算法——Prim演算法和Kruskal演算法的JS實現 基於矩陣實現的最小生成樹演算法 prim最小生成樹演算法原理 圖相關（三）圖的鄰接矩陣表示（C++）及最最小生成樹演算法（prim和kruskal） 使用Matlab完成層次聚類演算法（最小生成樹演算法） 分類導航 HTML/CSS HTML教程 HTML5教程 CSS教程 CSS3教程 JavaScript JavaScript教程 jQuery教程 Node.js教程 服務端 Python教程 Python3教程 Linux教程 Docker教程 Ruby教程 Java教程 JSP教程 C教程 C++教程 Perl教程 Go教程 PHP教程 正則表達式 資料庫 SQL教程 MySQL教程 PostgreSQL教程 SQLite教程 MongoDB教程 Redis教程 Memcached教程 行動端 IOS教程 Swift教程 Advertisement 三度辭典 Copyright©2016-2021IT閱讀  Itread01.comAllRightsReserved. 0.001291036605835