數(shù)據(jù)結(jié)構(gòu)與算法之最小生成樹，秒懂！
前言
在數(shù)據(jù)結(jié)構(gòu)與算法的圖論中，(生成)最小生成樹算法是一種常用并且和生活貼切比較近的一種算法。但是可能很多人對(duì)概念不是很清楚，什么是最小生成樹?
- 一個(gè)有 n 個(gè)結(jié)點(diǎn)的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個(gè)結(jié)點(diǎn)，并且有保持圖連通的最少的邊。最小生成樹可以用kruskal(克魯斯卡爾)算法或prim(普里姆)算法求出。
通俗易懂的講就是最小生成樹包含原圖的所有節(jié)點(diǎn)而只用最少的邊和最小的權(quán)值距離。因?yàn)閚個(gè)節(jié)點(diǎn)最少需要n-1個(gè)邊聯(lián)通，而距離就需要采取某種策略選擇恰當(dāng)?shù)倪叀?/p>
學(xué)習(xí)最小生成樹實(shí)現(xiàn)算法之前我們要先高清最小生成樹的結(jié)構(gòu)和意義所在。咱么首先根據(jù)一些圖更好的祝你理解。
一個(gè)故事
在城市道路規(guī)劃中，是一門很需要科學(xué)的研究(只是假設(shè)學(xué)習(xí)不必當(dāng)真)。在公路時(shí)代城市聯(lián)通的主要矛盾是時(shí)間慢，而造價(jià)相比運(yùn)輸時(shí)間是次要矛盾。所以在公路時(shí)代我們盡量使得城市能夠直接聯(lián)通，縮短城市聯(lián)系時(shí)間，而稍微考慮建路成本!隨著科技發(fā)展、高級(jí)鐵路、信息傳輸相比公路運(yùn)輸快非常非常多，從而事件的主要矛盾從運(yùn)輸時(shí)間轉(zhuǎn)變?yōu)樵靸r(jià)成本，故有時(shí)會(huì)關(guān)注聯(lián)通所有點(diǎn)的路程(最短)，這就用到最小生成樹算法。
城市道路鋪設(shè)可能經(jīng)歷以下幾個(gè)階段。
- 初始，各個(gè)城市沒有高速公路(鐵路)。
- 政府打算各個(gè)城市鋪設(shè)公路(鐵路)，每個(gè)城市都想成為交通樞紐，快速到達(dá)其他城市，但每個(gè)城市都有這種想法，如果實(shí)現(xiàn)下去造價(jià)太昂貴。并且造成巨大浪費(fèi)。
- 最終國(guó)家選擇一些主要城市進(jìn)行聯(lián)通，有個(gè)別城市只能稍微繞道而行，而繞道太遠(yuǎn)的、人流量多的國(guó)家考慮新建公路(鐵路)，適當(dāng)提高效率。
不過上面鐵路規(guī)劃上由于龐大的人口可能不能夠滿足與"有鐵路"這個(gè)需求，人們對(duì)速度、距離、直達(dá)等條件一直在追求中……
但是你可以想象這個(gè)場(chǎng)景：有些東西造假非常非常昂貴，使用效率非常高，我這里假設(shè)成黃金鑲鉆電纜 鋪設(shè)，所以各個(gè)城市只要求不給自己落下，能通上就行(沒人敢跳了吧)。
要從有環(huán)圖中選取代價(jià)和最小的路線一方面代價(jià)最小(總距離最小最省黃金)另一方面聯(lián)通所有城市。
然而根據(jù)上圖我們可以得到以下最小生成樹,但是最么生成這個(gè)最小生成樹，就是下面要講的了。
而類似的還有局部區(qū)域島嶼聯(lián)通修橋，海底通道這些高成本的都多多少少會(huì)運(yùn)用。
Kruskal算法
上面介紹了最小生成樹是什么，現(xiàn)在需要掌握和理解最小生成樹如何形成。給你一個(gè)圖，用一個(gè)規(guī)則生成一個(gè)最小生成樹。而在實(shí)現(xiàn)最小生成樹方面有prim和kruskal算法，這兩種算法的策略有所區(qū)別，但是時(shí)間復(fù)雜度一致。
Kruskal算法，和前面講到的并查集關(guān)系很大，它的主要思想為：
- 先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)、而邊集為空的子圖，把子圖中各個(gè)頂點(diǎn)看成各棵樹上的根結(jié)點(diǎn)，之后，從網(wǎng)的邊集 E 中選取一條權(quán)值最小的邊，若該條邊的兩個(gè)頂點(diǎn)分屬不同的樹，則將其加入子圖，即把兩棵樹合成一棵樹，反之，若該條邊的兩個(gè)頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直到森林中只有一棵樹，也即子圖中含有 n-1 條邊為止。
簡(jiǎn)而言之，Kruskal算法進(jìn)行調(diào)度的單位是邊,它的信仰為:所有邊能小則小，算法的實(shí)現(xiàn)方面要用到并查集判斷兩點(diǎn)是否在同一集合。
而算法的具體步驟為：
- 將圖中所有邊對(duì)象(邊長(zhǎng)、兩端點(diǎn))依次加入集合(優(yōu)先隊(duì)列)q1中。初始所有點(diǎn)相互獨(dú)立。
- 取出集合(優(yōu)先隊(duì)列)q1最小邊，判斷邊的兩點(diǎn)是否聯(lián)通。
- 如果聯(lián)通說明兩個(gè)點(diǎn)已經(jīng)有其它邊將兩點(diǎn)聯(lián)通了，跳過，如果不連通，則使用union(并查集合并)將兩個(gè)頂點(diǎn)合并，這條邊被使用(可以儲(chǔ)存或者計(jì)算數(shù)值)。
- 重復(fù)2，3操作直到集合(優(yōu)先隊(duì)列)q1為空。此時(shí)被選擇的邊構(gòu)成最小生成樹。
Prim算法除了Kruskal算法以外，普里姆算法(Prim算法)也是常用的最小生成樹算法。雖然在效率上差不多。但是貪心的方式和Kruskal完全不同。
prim算法的核心信仰是：從已知擴(kuò)散尋找最小。它的實(shí)現(xiàn)方式和Dijkstra算法相似但稍微有所區(qū)別，Dijkstra是求單源最短路徑，而每計(jì)算一個(gè)點(diǎn)需要對(duì)這個(gè)點(diǎn)重新更新距離，而prim不用更新距離。直接找已知點(diǎn)的鄰邊最小加入即可!prim和kruskal算法都是從邊入手處理。
對(duì)于具體算法具體步驟，大致為：
- 尋找圖中任意點(diǎn)，以它為起點(diǎn)，它的所有邊V加入集合(優(yōu)先隊(duì)列)q1,設(shè)置一個(gè)boolean數(shù)組bool[]標(biāo)記該位置(邊有兩個(gè)點(diǎn)，每次加入沒有被標(biāo)記那個(gè)點(diǎn)的所有邊)。
- 從集合q1找到距離最小的那個(gè)邊v1并 判斷邊是否存在未被標(biāo)記的一點(diǎn)`p` ，如果p不存在說明已經(jīng)確定過那么跳過當(dāng)前邊處理，如果未被標(biāo)(訪問)記那么標(biāo)記該點(diǎn)p,并且與p相連的未知點(diǎn)(未被標(biāo)記)構(gòu)成的邊加入集合q1， 邊v1(可以進(jìn)行計(jì)算距離之類，該邊構(gòu)成最小生成樹) .
- 重復(fù)1，2直到q1為空，構(gòu)成最小生成樹 !
大體步驟圖解為：
因?yàn)閜rim從開始到結(jié)束一直是一個(gè)整體在擴(kuò)散，所以不需要考慮兩棵樹合并的問題，在這一點(diǎn)實(shí)現(xiàn)上稍微方便了一點(diǎn)。
當(dāng)然，要注意的是最小生成樹并不唯一，甚至同一種算法生成的最小生成樹都可能有所不同，但是相同的是無論生成怎樣的最小生成樹：
- 能夠保證所有節(jié)點(diǎn)連通(能夠滿足要求和條件)
- 能夠保證所有路徑之和最小(結(jié)果和目的相同)
- 最小生成樹不唯一，可能多樣的
代碼實(shí)現(xiàn)
上面分析了邏輯實(shí)現(xiàn)。下面我們用代碼簡(jiǎn)單實(shí)現(xiàn)上述的算法。
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;//最小生成樹的最短路徑長(zhǎng)度
- int max=66666;
- String cityname[]= {"北京","武漢","南京","上海","杭州","廣州","深圳"};
- int city[][]= {
- { max, 8, 7, max, max, max, max }, //北京和武漢南京聯(lián)通
- { 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]+" 聯(lián)通");
- 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]+" 聯(lián)通");
- 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;
- }
- }
- }
輸出結(jié)果：
- 上海 南京 聯(lián)通
- 杭州 上海 聯(lián)通
- 武漢 南京 聯(lián)通
- 北京 南京 聯(lián)通
- 廣州 武漢 聯(lián)通
- 深圳 廣州 聯(lián)通
- 28
Kruskal:
- package 圖論;
- import java.util.Comparator;
- import java.util.PriorityQueue;
- import java.util.Queue;
- import 圖論.prim.side;
- /*
- * 作者：bigsai(公眾號(hào))
- */
- 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)//返回頭節(jié)點(diǎn)的數(shù)值
- {
- if(tree[a]>0)//說明是子節(jié)點(diǎn)
- {
- 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+"已經(jīng)在一棵樹上");
- }
- else {
- if(tree[a1]<tree[b1])//這個(gè)是負(fù)數(shù)，為了簡(jiǎn)單減少計(jì)算，不在調(diào)用value函數(shù)
- {
- tree[a1]+=tree[b1];//個(gè)數(shù)相加 注意是負(fù)數(shù)相加
- tree[b1]=a1; //b樹成為a的子樹，直接指向a；
- }
- else
- {
- tree[b1]+=tree[a1];//個(gè)數(shù)相加 注意是負(fù)數(shù)相加
- tree[a1]=b1; //b樹成為a的子樹，直接指向a；
- }
- }
- }
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- init();
- int minlength=0;//最小生成樹的最短路徑長(zhǎng)度
- int max=66666;
- String cityname[]= {"北京","武漢","南京","上海","杭州","廣州","深圳"};
- boolean jud[][]=new boolean[7][7];//加入邊需要防止重復(fù) 比如 ba和ab等價(jià)的
- 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>() {//優(yōu)先隊(duì)列存邊+
- 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)//是否加入隊(duì)列
- {
- jud[i][j]=true;jud[j][i]=true;
- q1.add(new side(city[i][j], i, j));
- }
- }
- }
- while(!q1.isEmpty())//執(zhí)行算法
- {
- 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]+" 聯(lián)通");
- 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;
- }
- }
- }
輸出結(jié)果
- 上海 杭州 聯(lián)通
- 廣州 深圳 聯(lián)通
- 南京 上海 聯(lián)通
- 武漢 南京 聯(lián)通
- 北京 南京 聯(lián)通
- 武漢 廣州 聯(lián)通
- 28
總結(jié)
最小生成樹算法理解起來也相對(duì)簡(jiǎn)單，實(shí)現(xiàn)起來也不是很難。Kruskal和Prim主要是貪心算法的兩種角度。一個(gè)從整體開始找最小邊，遇到關(guān)聯(lián)不斷合并，另一個(gè)從局部開始擴(kuò)散找身邊的最小不斷擴(kuò)散直到生成最小生成樹。在學(xué)習(xí)最小生成樹之前最好學(xué)習(xí)一下dijkstra算法和并查集，這樣在實(shí)現(xiàn)起來能夠快一點(diǎn)，清晰一點(diǎn)。
力扣1584就是一個(gè)最小生成樹的入門題，不過哪個(gè)有點(diǎn)區(qū)別的就是默認(rèn)所有點(diǎn)是聯(lián)通的，所以需要你剪枝優(yōu)化。這里就不帶大家一起看啦，有問題下面也可交流!
最后，如果你那天真的獲得一大筆資金去修建這么一條昂貴的黃金路線，可以適當(dāng)采取此方法，另外剩下的大批，茍富貴，勿相忘。
