最小生成树问题的算法笔记
最小生成樹問題
前提
在一給定的無向圖G = (V, E) 中，(u, v) 代表連接頂點 u 與頂點 v 的邊（即），而 w(u, v) 代表此邊的權重，若存在 T 為 E 的子集且為無循環圖，使得聯通所有結點的的 w(T) 最小，則此 T 為 G 的最小生成樹。
最小生成樹其實是最小權重生成樹的簡稱。
先回憶回憶什么是樹、什么是圖、什么是最小生成樹。
1 描述最小生成樹問題算法的輸入、輸出
1.1 最小生成樹問題算法的輸入：由實際生活中的點和邊構成的圖，如基電站和電纜線路、景點和公路等抽象化出來的圖；
1.2 最小生成樹問題算法的輸出：由輸入的圖經過Prim算法或者Kruskal 算法等處理最終得到一個各條邊權值之和最小的樹，而得到的這棵樹叫做最小生成樹，該生成樹往往是修公路的費用最小化的修路方式、修電站的通信的電線的費用最小化的修造方式。
1.3 最小生成樹要解決的兩個問題：
（1）盡可能選取權值小的邊，但不能構成回路；
（2）選取n-1條恰當的邊以連接網的n個頂點。
1.4 構成網的一棵最小生成樹，即：在e條帶權的邊中選取n-1條邊（不構成回路），使“權值之和”為最小。
2 普里姆算法（Prim）
2.1 本質：加點法
2.2 基本思想：
取圖中任意一個頂點V作為生成樹的根，之后往生成樹上添加新的頂點W。在添加的頂點W和已經在生成樹上的頂點V之間必定存在一條邊，該邊的權值在所有連通項點V和W之間的邊中取值為最小。之后繼續往生成樹上添加頂點，直至生成樹上含有n個頂點為止。
2.3 具體做法：
在生成樹的構造過程中，讓連通圖中n個頂點分屬兩個集合：已經加入到生成樹上的頂點集合U和（原連通圖上）還沒加入到生成樹上的頂點集合V-U；每次在V-U集合里選中一個和生成樹上某一個頂點連線中權值最小的，將此頂點加入到生成樹里。
2.4 實例：
（1）如下帶權無向連通圖1：
圖1（2）從頂點a開始加點：
說明：可能考慮的邊的權值，這一列的數據，標志為紅色是指這權值為X1的邊的兩個頂點為U集合；標志為藍色是指這權值為X2的邊再次被遇到，但這邊不能在本次最小生成樹；為空，則表示Prim算法結束。
（3）最終得到最小生成樹，如下圖中的用紅色邊連通的頂點所構成的樹：
（4）主要代碼（用java實現）：
（5）測試結果截圖（截圖過小，請您見諒）：
3 克魯斯卡爾算法（Kruskal）
3.1 本質：加邊法。為使最小生成樹上的邊的權值之和達到最小，則應使生成樹中的每條邊的權值盡可能地小。
3.2 基本思想：
先構造一個只含有n個頂點的子圖SG，即只選原圖中的所有的頂點n作為原圖的子圖，然后從權值最小的邊開始（一條一條地分別加入，加入的過程只要保證子圖不產生回路就可以，因為我們最終要找到的生成樹是一棵樹，所以它是不能有回路的，那么在這個加邊的過程中只要保證這一點就可以，因為我們每次都要選權值最小的，只要不產生回路就滿足了最小生成樹的條件，直到最后這n-1條邊全部加入完成，這個算法就可結束），若它的添加不能使SG中產生回路，則在SG上加上這條邊，如此重復，直到加上 n-1 條邊為止。
3.3 實例：
（1）如下帶權無向連通圖2：
（2）加邊過程（自個兒花時間做PPT，再截圖）：
提示：從上往下看，最后一張為紅色邊加頂點構成最小生成樹。
（3）代碼（C，僅供參考）：
#include <stdio.h> #include <stdlib.h> #define Max 50typedef struct road *Road; typedef struct road {int a , b;int w; }road;typedef struct graph *Graph; typedef struct graph {int e , n;Road data; }graph;Graph initGraph(int m , int n) {Graph g = (Graph)malloc(sizeof(graph));g->n = m;g->e = n;g->data = (Road)malloc(sizeof(road) * (g->e));return g; }void create(Graph g) {int i;for(i = 1 ; i <= g->e ; i++){int x , y, w;scanf("%d %d %d",&x,&y,&w);if(x < y){g->data[i].a = x;g->data[i].b = y;} else{g->data[i].a = y;g->data[i].b = x;}g->data[i].w = w;} }int getRoot(int v[], int x) {while(v[x] != x){x = v[x];}return x; }//這里沒有用到效率更高的堆排序 void sort(Road data, int n) {int i , j;for(i = 1 ; i <= n-1 ; i++){for(j = 1 ; j <= n-i ; j++){if(data[j].w > data[j+1].w){road t = data[j];data[j] = data[j+1];data[j+1] = t;}}} }int Kruskal(Graph g) {int sum = 0;//并查集int v[Max];int i;//初始化步驟for(i = 1 ; i <= g->n ; i++){v[i] = i;}sort(g->data , g->e);//mainfor(i = 1 ; i <= g->e ; i++){int a , b;a = getRoot(v,g->data[i].a);b = getRoot(v,g->data[i].b);if(a != b){v[a] = b;sum += g->data[i].w;}}return sum; }3.4 最后溫馨提示：
（一）圖的生成樹不唯一，從不同的頂點出發進行遍歷，可以得到不同的生成樹；
（二）即使從相同的頂點出發，在選擇最小邊時，可能有多條同樣的邊可選，此時任選其一；
4 最小生成樹問題的代碼解決
4.1 將通信網絡抽象為無向圖，將各個基站抽象為圖的頂點，將預計可能要修的線路抽象為圖的邊，將修造各條線路的費用抽象為圖的邊的權值，線路便宜即是邊的權值小，線路貴即邊的權值大，最便宜的連通線路（含費用的意義）加基站構成最小生成樹。
4.2 進行Java代碼（Prim算法）實現：
（1）代碼（java）：
package JavaTestBag; import java.util.ArrayList; import java.util.List; import java.util.Scanner;/** 最小生成樹(普里姆算法(Prim算法))簡單版*/// 頂點類Vertex class Vertex{String vName; //頂點的名稱@Overridepublic 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; //最短路徑 }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("請輸入各個基站的代號(如：A):");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);} }（2）測試結果圖如下：
參考文獻
[1] Jon Kleinberg，Eva Tardos 著，張立昂，屈婉玲 譯. 算法設計. .北京：清華大學出版社，2007.3
[2] Eric，Lehaman. 計算機科學中的數學-信息與智能時代的必修課. 北京：電子工業出版社
總結
以上是生活随笔為你收集整理的最小生成树问题的算法笔记的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 中国各省市json地图，包括雄安
- 下一篇： 基于51单片机红外热释电人体感应蓝牙防盗