[[426679]]

前言

在數據結構與算法的圖論中，(生成)最小生成樹算法是一種常用并且和生活貼切比較近的一種算法。但是可能很多人對概念不是很清楚，什么是最小生成樹?

• 一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，并且有保持圖連通的最少的邊。最小生成樹可以用kruskal(克魯斯卡爾)算法或prim(普里姆)算法求出。

通俗易懂的講就是最小生成樹包含原圖的所有節點而只用最少的邊和最小的權值距離。因為n個節點最少需要n-1個邊聯通，而距離就需要采取某種策略選擇恰當的邊。

學習最小生成樹實現算法之前我們要先高清最小生成樹的結構和意義所在。咱么首先根據一些圖更好的祝你理解。

一個故事

在城市道路規劃中，是一門很需要科學的研究(只是假設學習不必當真)。在公路時代城市聯通的主要矛盾是時間慢，而造價相比運輸時間是次要矛盾。所以在公路時代我們盡量使得城市能夠直接聯通，縮短城市聯系時間，而稍微考慮建路成本!隨著科技發展、高級鐵路、信息傳輸相比公路運輸快非常非常多，從而事件的主要矛盾從運輸時間轉變為造價成本，故有時會關注聯通所有點的路程(最短)，這就用到最小生成樹算法。

城市道路鋪設可能經歷以下幾個階段。

• 初始，各個城市沒有高速公路(鐵路)。
• 政府打算各個城市鋪設公路(鐵路)，每個城市都想成為交通樞紐，快速到達其他城市，但每個城市都有這種想法，如果實現下去造價太昂貴。并且造成巨大浪費。
• 最終國家選擇一些主要城市進行聯通，有個別城市只能稍微繞道而行，而繞道太遠的、人流量多的國家考慮新建公路(鐵路)，適當提高效率。

不過上面鐵路規劃上由于龐大的人口可能不能夠滿足與"有鐵路"這個需求，人們對速度、距離、直達等條件一直在追求中……

但是你可以想象這個場景：有些東西造假非常非常昂貴，使用效率非常高，我這里假設成黃金鑲鉆電纜 鋪設，所以各個城市只要求不給自己落下，能通上就行(沒人敢跳了吧)。

要從有環圖中選取代價和最小的路線一方面代價最小(總距離最小最省黃金)另一方面聯通所有城市。

然而根據上圖我們可以得到以下最小生成樹,但是最么生成這個最小生成樹，就是下面要講的了。

而類似的還有局部區域島嶼聯通修橋，海底通道這些高成本的都多多少少會運用。

Kruskal算法

上面介紹了最小生成樹是什么，現在需要掌握和理解最小生成樹如何形成。給你一個圖，用一個規則生成一個最小生成樹。而在實現最小生成樹方面有prim和kruskal算法，這兩種算法的策略有所區別，但是時間復雜度一致。

Kruskal算法，和前面講到的并查集關系很大，它的主要思想為：

• 先構造一個只含 n 個頂點、而邊集為空的子圖，把子圖中各個頂點看成各棵樹上的根結點，之后，從網的邊集 E 中選取一條權值最小的邊，若該條邊的兩個頂點分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹，反之，若該條邊的兩個頂點已落在同一棵樹上，則不可取，而應該取下一條權值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有 n-1 條邊為止。

簡而言之，Kruskal算法進行調度的單位是邊,它的信仰為:所有邊能小則小，算法的實現方面要用到并查集判斷兩點是否在同一集合。

而算法的具體步驟為：

1. 將圖中所有邊對象(邊長、兩端點)依次加入集合(優先隊列)q1中。初始所有點相互獨立。
2. 取出集合(優先隊列)q1最小邊，判斷邊的兩點是否聯通。
3. 如果聯通說明兩個點已經有其它邊將兩點聯通了，跳過，如果不連通，則使用union(并查集合并)將兩個頂點合并，這條邊被使用(可以儲存或者計算數值)。
4. 重復2，3操作直到集合(優先隊列)q1為空。此時被選擇的邊構成最小生成樹。

Prim算法除了Kruskal算法以外，普里姆算法(Prim算法)也是常用的最小生成樹算法。雖然在效率上差不多。但是貪心的方式和Kruskal完全不同。

prim算法的核心信仰是：從已知擴散尋找最小。它的實現方式和Dijkstra算法相似但稍微有所區別，Dijkstra是求單源最短路徑，而每計算一個點需要對這個點重新更新距離，而prim不用更新距離。直接找已知點的鄰邊最小加入即可!prim和kruskal算法都是從邊入手處理。

對于具體算法具體步驟，大致為：

1. 尋找圖中任意點，以它為起點，它的所有邊V加入集合(優先隊列)q1,設置一個boolean數組bool[]標記該位置(邊有兩個點，每次加入沒有被標記那個點的所有邊)。
2. 從集合q1找到距離最小的那個邊v1并 判斷邊是否存在未被標記的一點`p` ，如果p不存在說明已經確定過那么跳過當前邊處理，如果未被標(訪問)記那么標記該點p,并且與p相連的未知點(未被標記)構成的邊加入集合q1， 邊v1(可以進行計算距離之類，該邊構成最小生成樹) .
3. 重復1，2直到q1為空，構成最小生成樹 !

大體步驟圖解為：

因為prim從開始到結束一直是一個整體在擴散，所以不需要考慮兩棵樹合并的問題，在這一點實現上稍微方便了一點。

當然，要注意的是最小生成樹并不唯一，甚至同一種算法生成的最小生成樹都可能有所不同，但是相同的是無論生成怎樣的最小生成樹：

• 能夠保證所有節點連通(能夠滿足要求和條件)
• 能夠保證所有路徑之和最小(結果和目的相同)
• 最小生成樹不唯一，可能多樣的

代碼實現

上面分析了邏輯實現。下面我們用代碼簡單實現上述的算法。

prim

package 圖論; 
 
import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.Comparator; 
import java.util.List; 
import java.util.PriorityQueue; 
import java.util.Queue; 
 
public class prim { 
 
    public static void main(String[] args) { 
        int minlength=0;//最小生成樹的最短路徑長度 
        int max=66666; 
        String cityname[]= {"北京","武漢","南京","上海","杭州","廣州","深圳"}; 
        int city[][]= { 
                { max, 8, 7, max, max, max, max }, //北京和武漢南京聯通 
                { 8, max,6, max,9, 8,max }, //武漢——北京、南京、杭州、廣州 
                { 7, 6, max, 3,4, max,max }, //南京——北京、武漢、上海、杭州 
                { max, max,3, max,2, max,max }, //上海——南京、杭州 
                { max, 9,4, 2,max, max,10 }, //杭州——武漢、南京、上海、深圳 
                { max, 8,max, max,max, max,2 }, //廣州——武漢、深圳 
                { max, max,max, max,10,2,max }//深圳——杭州、廣州 
        };// 地圖 
 
        boolean istrue[]=new boolean[7]; 
        //南京 
        Queue<side>q1=new PriorityQueue<side>(new Comparator<side>() { 
            public int compare(side o1, side o2) { 
                // TODO Auto-generated method stub 
                return o1.lenth-o2.lenth; 
            } 
        }); 
        for(int i=0;i<7;i++) 
        { 
            if(city[2][i]!=max) 
            { 
                istrue[2]=true; 
                q1.add(new side(city[2][i], 2, i)); 
            } 
        }        
        while(!q1.isEmpty()) 
        { 
            side newside=q1.poll();//拋出 
            if(istrue[newside.point1]&&istrue[newside.point2]) 
            { 
                continue; 
            } 
            else { 
                if(!istrue[newside.point1]) 
                { 
                    istrue[newside.point1]=true; 
                    minlength+=city[newside.point1][newside.point2]; 
                    System.out.println(cityname[newside.point1]+" "+cityname[newside.point2]+" 聯通"); 
                    for(int i=0;i<7;i++) 
                    { 
                        if(!istrue[i]) 
                        { 
                            q1.add(new side(city[newside.point1][i],newside.point1,i)); 
                        } 
                    } 
                } 
                else { 
                    istrue[newside.point2]=true; 
                    minlength+=city[newside.point1][newside.point2]; 
                    System.out.println(cityname[newside.point2]+" "+cityname[newside.point1]+" 聯通"); 
                    for(int i=0;i<7;i++) 
                    { 
                        if(!istrue[i]) 
                        { 
                            q1.add(new side(city[newside.point2][i],newside.point2,i)); 
                        } 
                    } 
                } 
            } 
 
        } 
        System.out.println(minlength);       
    } 
 
    static class side//邊 
    { 
        int lenth; 
        int point1; 
        int point2; 
        public side(int lenth,int p1,int p2) { 
            this.lenth=lenth; 
            this.point1=p1; 
            this.point2=p2; 
        } 
    } 
 
} 

輸出結果：

• 上海 南京 聯通
• 杭州 上海 聯通
• 武漢 南京 聯通
• 北京 南京 聯通
• 廣州 武漢 聯通
• 深圳 廣州 聯通
• 28

Kruskal:

package 圖論; 
 
import java.util.Comparator; 
import java.util.PriorityQueue; 
import java.util.Queue; 
 
import 圖論.prim.side; 
/* 
 * 作者：bigsai(公眾號) 
 */ 
public class kruskal { 
 
    static int tree[]=new int[10];//bing查集 
    public static void init() { 
        for(int i=0;i<10;i++)//初始 
        { 
            tree[i]=-1; 
        } 
    } 
    public static int search(int a)//返回頭節點的數值 
    { 
        if(tree[a]>0)//說明是子節點 
        { 
            return tree[a]=search(tree[a]);//路徑壓縮 
        } 
        else 
            return a; 
    } 
    public static void union(int a,int b)//表示 a，b所在的樹合并小樹合并大樹(不重要) 
    { 
        int a1=search(a);//a根 
        int b1=search(b);//b根 
        if(a1==b1) {//System.out.println(a+"和"+b+"已經在一棵樹上"); 
        } 
        else { 
        if(tree[a1]<tree[b1])//這個是負數，為了簡單減少計算，不在調用value函數 
        { 
            tree[a1]+=tree[b1];//個數相加  注意是負數相加 
            tree[b1]=a1;       //b樹成為a的子樹，直接指向a； 
        } 
        else 
        { 
            tree[b1]+=tree[a1];//個數相加  注意是負數相加 
            tree[a1]=b1;       //b樹成為a的子樹，直接指向a； 
        } 
        } 
    } 
    public static void main(String[] args) { 
        // TODO Auto-generated method stub 
        init(); 
        int minlength=0;//最小生成樹的最短路徑長度 
        int max=66666; 
        String cityname[]= {"北京","武漢","南京","上海","杭州","廣州","深圳"}; 
        boolean jud[][]=new boolean[7][7];//加入邊需要防止重復 比如 ba和ab等價的 
        int city[][]= { 
                { max, 8, 7, max, max, max, max },  
                { 8, max,6, max,9, 8,max },  
                { 7, 6, max, 3,4, max,max },  
                { max, max,3, max,2, max,max },  
                { max, 9,4, 2,max, max,10 },  
                { max, 8,max, max,max, max,2 },  
                { max, max,max, max,10,2,max } 
        };// 地圖 
        boolean istrue[]=new boolean[7]; 
        //南京 
        Queue<side>q1=new PriorityQueue<side>(new Comparator<side>() {//優先隊列存邊+ 
            public int compare(side o1, side o2) { 
                // TODO Auto-generated method stub 
                return o1.lenth-o2.lenth; 
            } 
        }); 
        for(int i=0;i<7;i++) 
        { 
            for(int j=0;j<7;j++) 
            { 
                if(!jud[i][j]&&city[i][j]!=max)//是否加入隊列 
                { 
                    jud[i][j]=true;jud[j][i]=true; 
                    q1.add(new side(city[i][j], i, j)); 
                } 
            } 
        } 
        while(!q1.isEmpty())//執行算法 
        { 
            side newside=q1.poll(); 
            int p1=newside.point1; 
            int p2=newside.point2; 
            if(search(p1)!=search(p2)) 
            { 
                union(p1, p2); 
                System.out.println(cityname[p1]+" "+cityname[p2]+" 聯通"); 
                minlength+=newside.lenth; 
            } 
        } 
        System.out.println(minlength); 
 
 
    } 
    static class side//邊 
    { 
        int lenth; 
        int point1; 
        int point2; 
        public side(int lenth,int p1,int p2) { 
            this.lenth=lenth; 
            this.point1=p1; 
            this.point2=p2; 
        } 
    } 
} 

輸出結果

• 上海 杭州 聯通
• 廣州 深圳 聯通
• 南京 上海 聯通
• 武漢 南京 聯通
• 北京 南京 聯通
• 武漢 廣州 聯通
• 28

總結

最小生成樹算法理解起來也相對簡單，實現起來也不是很難。Kruskal和Prim主要是貪心算法的兩種角度。一個從整體開始找最小邊，遇到關聯不斷合并，另一個從局部開始擴散找身邊的最小不斷擴散直到生成最小生成樹。在學習最小生成樹之前最好學習一下dijkstra算法和并查集，這樣在實現起來能夠快一點，清晰一點。

力扣1584就是一個最小生成樹的入門題，不過哪個有點區別的就是默認所有點是聯通的，所以需要你剪枝優化。這里就不帶大家一起看啦，有問題下面也可交流!

最后，如果你那天真的獲得一大筆資金去修建這么一條昂貴的黃金路線，可以適當采取此方法，另外剩下的大批，茍富貴，勿相忘。