數(shù)據(jù)結(jié)構(gòu)與算法中什么是最小生成樹

前言

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

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

通俗易懂的講就是最小生成樹包含原圖的所有節(jié)點而只用最少的邊和最小的權(quán)值距離。因為n個節(jié)點最少需要n-1個邊聯(lián)通，而距離就需要采取某種策略選擇恰當(dāng)?shù)倪叀?/p>

學(xué)習(xí)最小生成樹實現(xiàn)算法之前我們要先高清最小生成樹的結(jié)構(gòu)和意義所在。咱么首先根據(jù)一些圖更好的祝你理解。

一個故事

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

城市道路鋪設(shè)可能經(jīng)歷以下幾個階段。

• 初始，各個城市沒有高速公路(鐵路)。

• 政府打算各個城市鋪設(shè)公路(鐵路)，每個城市都想成為交通樞紐，快速到達其他城市，但每個城市都有這種想法，如果實現(xiàn)下去造價太昂貴。并且造成巨大浪費。

• 最終國家選擇一些主要城市進行聯(lián)通，有個別城市只能稍微繞道而行，而繞道太遠的、人流量多的國家考慮新建公路(鐵路)，適當(dāng)提高效率。

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

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

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

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

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

Kruskal算法

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

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

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

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

而算法的具體步驟為：

1. 將圖中所有邊對象(邊長、兩端點)依次加入集合(優(yōu)先隊列)q1中。初始所有點相互獨立。

2. 取出集合(優(yōu)先隊列)q1最小邊，判斷邊的兩點是否聯(lián)通。

3. 如果聯(lián)通說明兩個點已經(jīng)有其它邊將兩點聯(lián)通了，跳過，如果不連通，則使用union（并查集合并）將兩個頂點合并，這條邊被使用(可以儲存或者計算數(shù)值)。

4. 重復(fù)2，3操作直到集合（優(yōu)先隊列）q1為空。此時被選擇的邊構(gòu)成最小生成樹。

Prim算法

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

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

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

1. 尋找圖中任意點，以它為起點，它的所有邊V加入集合(優(yōu)先隊列)q1,設(shè)置一個boolean數(shù)組bool[]標記該位置(邊有兩個點，每次加入沒有被標記那個點的所有邊)。

2. 從集合q1找到距離最小的那個邊v1并判斷邊是否存在未被標記的一點`p`，如果p不存在說明已經(jīng)確定過那么跳過當(dāng)前邊處理，如果未被標(訪問)記那么標記該點p,并且與p相連的未知點(未被標記)構(gòu)成的邊加入集合q1，邊v1(可以進行計算距離之類，該邊構(gòu)成最小生成樹).

3. 重復(fù)1，2直到q1為空，構(gòu)成最小生成樹 ！

大體步驟圖解為：

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

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

• 能夠保證所有節(jié)點連通(能夠滿足要求和條件)

• 能夠保證所有路徑之和最小(結(jié)果和目的相同)

• 最小生成樹不唯一，可能多樣的

代碼實現(xiàn)

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

prim

package圖論;

importjava.util.ArrayList;
importjava.util.Arrays;
importjava.util.Comparator;
importjava.util.List;
importjava.util.PriorityQueue;
importjava.util.Queue;

publicclassprim{

publicstaticvoidmain(String[]args){
intminlength=0;//最小生成樹的最短路徑長度
intmax=66666;
Stringcityname[]={"北京","武漢","南京","上海","杭州","廣州","深圳"};
intcity[][]={
{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}//深圳——杭州、廣州
};//地圖

booleanistrue[]=newboolean[7];
//南京
Queueq1=newPriorityQueue(newComparator(){
publicintcompare(sideo1,sideo2){
//TODOAuto-generatedmethodstub
returno1.lenth-o2.lenth;
}
});
for(inti=0;i<7;i++)
{
if(city[2][i]!=max)
{
istrue[2]=true;
q1.add(newside(city[2][i],2,i));
}
}
while(!q1.isEmpty())
{
sidenewside=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(inti=0;i<7;i++)
{
if(!istrue[i])
{
q1.add(newside(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(inti=0;i<7;i++)
{
if(!istrue[i])
{
q1.add(newside(city[newside.point2][i],newside.point2,i));
}
}
}
}

}
System.out.println(minlength);
}

staticclassside//邊
{
intlenth;
intpoint1;
intpoint2;
publicside(intlenth,intp1,intp2){
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圖論;

importjava.util.Comparator;
importjava.util.PriorityQueue;
importjava.util.Queue;

import圖論.prim.side;
/*
*作者：bigsai(公眾號)
*/
publicclasskruskal{

staticinttree[]=newint[10];//bing查集
publicstaticvoidinit(){
for(inti=0;i<10;i++)//初始
{
tree[i]=-1;
}
}
publicstaticintsearch(inta)//返回頭節(jié)點的數(shù)值
{
if(tree[a]>0)//說明是子節(jié)點
{
returntree[a]=search(tree[a]);//路徑壓縮
}
else
returna;
}
publicstaticvoidunion(inta,intb)//表示a，b所在的樹合并小樹合并大樹(不重要)
{
inta1=search(a);//a根
intb1=search(b);//b根
if(a1==b1){//System.out.println(a+"和"+b+"已經(jīng)在一棵樹上");
}
else{
if(tree[a1]//這個是負數(shù)，為了簡單減少計算，不在調(diào)用value函數(shù)
{
tree[a1]+=tree[b1];//個數(shù)相加注意是負數(shù)相加
tree[b1]=a1;//b樹成為a的子樹，直接指向a；
}
else
{
tree[b1]+=tree[a1];//個數(shù)相加注意是負數(shù)相加
tree[a1]=b1;//b樹成為a的子樹，直接指向a；
}
}
}
publicstaticvoidmain(String[]args){
//TODOAuto-generatedmethodstub
init();
intminlength=0;//最小生成樹的最短路徑長度
intmax=66666;
Stringcityname[]={"北京","武漢","南京","上海","杭州","廣州","深圳"};
booleanjud[][]=newboolean[7][7];//加入邊需要防止重復(fù)比如ba和ab等價的
intcity[][]={
{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}
};//地圖
booleanistrue[]=newboolean[7];
//南京
Queueq1=newPriorityQueue(newComparator(){//優(yōu)先隊列存邊+
publicintcompare(sideo1,sideo2){
//TODOAuto-generatedmethodstub
returno1.lenth-o2.lenth;
}
});
for(inti=0;i<7;i++)
{
for(intj=0;j<7;j++)
{
if(!jud[i][j]&&city[i][j]!=max)//是否加入隊列
{
jud[i][j]=true;jud[j][i]=true;
q1.add(newside(city[i][j],i,j));
}
}
}
while(!q1.isEmpty())//執(zhí)行算法
{
sidenewside=q1.poll();
intp1=newside.point1;
intp2=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);


}
staticclassside//邊
{
intlenth;
intpoint1;
intpoint2;
publicside(intlenth,intp1,intp2){
this.lenth=lenth;
this.point1=p1;
this.point2=p2;
}
}
}

輸出結(jié)果

上海 杭州 聯(lián)通
廣州 深圳 聯(lián)通
南京 上海 聯(lián)通
武漢 南京 聯(lián)通
北京 南京 聯(lián)通
武漢 廣州 聯(lián)通
28

總結(jié)

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

力扣1584就是一個最小生成樹的入門題，不過哪個有點區(qū)別的就是默認所有點是聯(lián)通的，所以需要你剪枝優(yōu)化。