Prim演算法 1.概覽 普里姆演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖裡搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖裡的所有頂點（英語：Vertex (graph theory)），且其所有邊的權值之和亦為最小。該演算法於1930年由捷克數學家沃伊捷赫·亞爾尼 ...
Prim演算法
1.概覽
普里姆演算法（Prim演算法），圖論中的一種演算法，可在加權連通圖裡搜索最小生成樹。意即由此演算法搜索到的邊子集所構成的樹中，不但包括了連通圖裡的所有頂點
2.演算法簡單描述
1).輸入：一個加權連通圖，其中頂點集合為V，邊集合為E；
2).初始化：Vnew = {x}，其中x為集合V中的任一節點（起始點），Enew = {},為空；
3).重覆下列操作，直到Vnew = V：
a.在集合E中選取權值最小的邊<u, v>，其中u為集合Vnew中的元素，而v不在Vnew集合當中，並且v∈V（如果存在有多條滿足前述條件即具有相同權值的邊，則可任意選取其中之一）；
b.將v加入集合Vnew中，將<u, v>邊加入集合Enew中；
4).輸出：使用集合Vnew和Enew來描述所得到的最小生成樹。
示例圖演示:
下麵對演算法的圖例描述:
| 圖例 | 說明 | 不可選 | 可選 | 已選（Vnew） |
|---|---|---|---|---|
|
|
此為原始的加權連通圖。每條邊一側的數字代表其權值。 | - | - | - |
|
|
頂點D被任意選為起始點。頂點A、B、E和F通過單條邊與D相連。A是距離D最近的頂點，因此將A及對應邊AD以高亮表示。 | C, G | A, B, E, F | D |
|
|
下一個頂點為距離D或A最近的頂點。B距D為9，距A為7，E為15，F為6。因此，F距D或A最近，因此將頂點F與相應邊DF以高亮表示。 | C, G | B, E, F | A, D |
 |
演算法繼續重覆上面的步驟。距離A為7的頂點B被高亮表示。 | C | B, E, G | A, D, F |
|
|
在當前情況下，可以在C、E與G間進行選擇。C距B為8，E距B為7，G距F為11。E最近，因此將頂點E與相應邊BE高亮表示。 | 無 | C, E, G | A, D, F, B |
|
|
這裡，可供選擇的頂點只有C和G。C距E為5，G距E為9，故選取C，並與邊EC一同高亮表示。 | 無 | C, G | A, D, F, B, E |
|
|
頂點G是唯一剩下的頂點，它距F為11，距E為9，E最近，故高亮表示G及相應邊EG。 | 無 | G | A, D, F, B, E, C |
|
|
現在，所有頂點均已被選取，圖中綠色部分即為連通圖的最小生成樹。在此例中，最小生成樹的權值之和為39。 | 無 | 無 | A, D, F, B, E, C, G |
3.簡單證明prim演算法
反證法：假設prim生成的不是最小生成樹
1).設prim生成的樹為G0
2).假設存在Gmin使得cost(Gmin)<cost(G0) 則在Gmin中存在<u,v>不屬於G0
3).將<u,v>加入G0中可得一個環，且<u,v>不是該環的最長邊(這是因為<u,v>∈Gmin)
4).這與prim每次生成最短邊矛盾
5).故假設不成立，命題得證.
Kruskal演算法
1.概覽
Kruskal演算法是一種用來尋找最小生成樹的演算法，由Joseph Kruskal在1956年發表。用來解決同樣問題的還有Prim演算法和Boruvka演算法等。三種演算法都是貪婪演算法的應用。和Boruvka演算法不同的地方是，Kruskal演算法在圖中存在相同權值的邊時也有效。
2.演算法簡單描述
1).記Graph中有v個頂點，e個邊
2).新建圖Graphnew，Graphnew中擁有原圖中相同的e個頂點，但沒有邊
3).將原圖Graph中所有e個邊按權值從小到大排序
4).迴圈：從權值最小的邊開始遍歷每條邊 直至圖Graph中所有的節點都在同一個連通分量中
if 這條邊連接的兩個節點於圖Graphnew中不在同一個連通分量中
添加這條邊到圖Graphnew中
示例圖演示:
圖例描述：
首先第一步，我們有一張圖Graph，有若幹點和邊
將所有的邊的長度排序，用排序的結果作為我們選擇邊的依據。這裡再次體現了貪心演算法的思想。資源排序，對局部最優的資源進行選擇，排序完成後，我們率先選擇了邊AD。這樣我們的圖就變成了右圖
在剩下的變中尋找。我們找到了CE。這裡邊的權重也是5
依次類推我們找到了6,7,7，即DF，AB，BE。
下麵繼續選擇， BC或者EF儘管現在長度為8的邊是最小的未選擇的邊。但是現在他們已經連通了（對於BC可以通過CE,EB來連接，類似的EF可以通過EB,BA,AD,DF來接連）。所以不需要選擇他們。類似的BD也已經連通了（這裡上圖的連通線用紅色表示了）。
最後就剩下EG和FG了。當然我們選擇了EG。最後成功的圖就是右：
3.簡單證明Kruskal演算法
對圖的頂點數n做歸納，證明Kruskal演算法對任意n階圖適用。
歸納基礎：
n=1，顯然能夠找到最小生成樹。
歸納過程：
假設Kruskal演算法對n≤k階圖適用，那麼，在k+1階圖G中，我們把最短邊的兩個端點a和b做一個合併操作，即把u與v合為一個點v'，把原來接在u和v的邊都接到v'上去，這樣就能夠得到一個k階圖G'(u,v的合併是k+1少一條邊)，G'最小生成樹T'可以用Kruskal演算法得到。
我們證明T'+{<u,v>}是G的最小生成樹。
用反證法，如果T'+{<u,v>}不是最小生成樹，最小生成樹是T，即W(T)<W(T'+{<u,v>})。顯然T應該包含<u,v>，否則，可以用<u,v>加入到T中，形成一個環，刪除環上原有的任意一條邊，形成一棵更小權值的生成樹。而T-{<u,v>}，是G'的生成樹。所以W(T-{<u,v>})<=W(T')，也就是W(T)<=W(T')+W(<u,v>)=W(T'+{<u,v>})，產生了矛盾。於是假設不成立，T'+{<u,v>}是G的最小生成樹，Kruskal演算法對k+1階圖也適用。
由數學歸納法，Kruskal演算法得證。
下麵使用java程式演示Prim演算法：
代碼如下:
package com.itheima.primer; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * 最小生成樹(普里姆演算法(Prim演算法)) * @author zhangming * @date 2016/04/20 */ public class MinTreePrimer { private static List<Vertex> visitedVertexs,leftedVertexs; //分別為添加到集合U中的節點集和剩餘的集合V中的節點集 private static List<Edge> searchEdges; //初始化圖的信息 public static void initGraph(Graph g){ visitedVertexs = new ArrayList<Vertex>(); leftedVertexs = new ArrayList<Vertex>(); searchEdges = new ArrayList<Edge>(); Scanner sc = new Scanner(System.in); System.out.print("輸入頂點數: "); int vertexNumber = sc.nextInt(); System.out.print("請輸入邊數: "); int edgeNumber = sc.nextInt(); String[] allVertex = new String[vertexNumber]; String[] allEdge = new String[edgeNumber]; System.out.println("================================="); System.out.println("請輸入各個頂點:"); Scanner scanner = new Scanner(System.in); for(int i=0;i<vertexNumber;i++){ System.out.print("頂點"+(i+1)+":"); allVertex[i] = scanner.nextLine(); } System.out.println("================================="); for(int i=0;i<edgeNumber;i++){ System.out.print("輸入邊(Vi,Vj)中的頂點名稱和權值W(如:A B 7): "); allEdge[i] = scanner.nextLine(); } g.vertex = new Vertex[allVertex.length]; g.edge = new Edge[allEdge.length]; g.minWeight = 0; for(int i=0;i<allVertex.length;i++){ g.vertex[i] = new Vertex(); g.vertex[i].vName = allVertex[i]; leftedVertexs.add(g.vertex[i]); //初始化剩餘點集合 } for(int i=0;i<allEdge.length;i++){ g.edge[i] = new Edge(); g.edge[i].startVertex = new Vertex(); g.edge[i].endVertex = new Vertex(); String edgeInfo[] = allEdge[i].split(" "); g.edge[i].startVertex.vName = edgeInfo[0]; g.edge[i].endVertex.vName = edgeInfo[1]; g.edge[i].weight = Integer.parseInt(edgeInfo[2]); } } public static void onChangeVertex(Vertex vertex){ visitedVertexs.add(vertex); //添加初始節點,作為預設的開始節點 leftedVertexs.remove(vertex); } public static Vertex findOneVertex(Graph g){ int minValue = Integer.MAX_VALUE; Vertex findVertex = new Vertex(); Edge findEdge = new Edge(); for(int i=0;i<visitedVertexs.size();i++){ for(int j=0;j<leftedVertexs.size();j++){ Vertex v1 = visitedVertexs.get(i); Vertex v2 = leftedVertexs.get(j); //獲取兩個頂點的名稱 for(int k=0;k<g.edge.length;k++){ String startName = g.edge[k].startVertex.vName; String endName = g.edge[k].endVertex.vName; if((v1.vName.equals(startName) && v2.vName.equals(endName))
||(v1.vName.equals(endName) && v2.vName.equals(startName))){ if(g.edge[k].weight < minValue){ findEdge = g.edge[k]; minValue = g.edge[k].weight; if(leftedVertexs.contains(v1)){ //會調用對象的equals方法比較對象,需重寫equals方法 findVertex = v1; }else if(leftedVertexs.contains(v2)){ findVertex = v2; } } } } } } g.minWeight+= minValue; searchEdges.add(findEdge); return findVertex; } public static void prim(Graph g){ while(leftedVertexs.size()>0){ //直到剩餘節點集為空時結束迴圈 Vertex findVertex = findOneVertex(g); onChangeVertex(findVertex); } System.out.print("\n最短路徑包含的邊: "); for(int i=0;i<searchEdges.size();i++){ System.out.print("("+searchEdges.get(i).startVertex.vName+","+searchEdges.get(i).endVertex.vName+")"+" "); } System.out.println("\n最短路徑長度: "+g.minWeight); } public static void main(String[] args) { Graph g = new Graph(); initGraph(g); onChangeVertex(g.vertex[0]); prim(g); } } /** * 頂點類Vertex */ class Vertex{ String vName; //頂點的名稱 @Override public boolean equals(Object obj) { if(obj instanceof Vertex){ Vertex vertex = (Vertex)obj; return this.vName.equals(vertex.vName); } return super.equals(obj); } } /** * 邊類Edge */ class Edge{ Vertex startVertex; Vertex endVertex; int weight; } /** * 圖的存儲結構 */ class Graph{ Vertex[] vertex; //頂點集 Edge[] edge; //邊集 int minWeight; //最短路徑 }
運行結果截圖:
