最小生成樹

什么是最小生成樹

• 是一棵樹
  - 無回路
  - |V|個頂點一定有|V|-1條邊
• 是生成樹
  - 包含全部頂點
  - |V|-1條邊全在圖里

貪心算法

什么是“貪”：每一步都要最好的
什么是“好”：權(quán)重最小的邊
需要約束：

只能用圖里有的邊

只能正好用掉|V|-1條邊

不能有回路

普利姆（Prim）算法——讓一棵小樹長大

需要維護兩個數(shù)組：lowcost[n] 、adjvex[n]（n是圖中的頂點數(shù)）
①從圖中找第一個起始頂點v0，作為生成樹的第一個頂點，然后從這個頂點到其他頂點的所有邊中選一條權(quán)值最小的邊。然后把這條邊的另一個頂點v和這條邊加入到生成樹中。
②對剩下的其他所有頂點，分別檢查這些頂點與頂點v的權(quán)值是否比這些頂點在lowcost數(shù)組中對應(yīng)的權(quán)值小，如果更小，則用較小的權(quán)值更新lowcost數(shù)組。
③從更新后的lowcost數(shù)組中繼續(xù)挑選權(quán)值最小而且不在生成樹中的邊，然后加入到生成樹。
④反復(fù)執(zhí)行②③直到所有所有頂點都加入到生成樹中。
視頻講解

Void MiniSpanTree_Prim(MGraph G){int min,i,j,k;int adjvex[MAXVEX]; //保存鄰接頂點下標(biāo)的數(shù)組int lowcost[MAXVEX]; //記錄當(dāng)前生成樹到剩余頂點的最小權(quán)值lowcost[0]=0; //將0號頂點(以0號頂點作為第一個頂點)加入生成樹adjvex[0]=0; //由于剛開始生成樹只有一個頂點 不存在邊 干脆都設(shè)為0for(i=1;i<G.vexnum;i++){ //除下標(biāo)為0以外的所有頂點lowcost[i]=G.arc[0][i]; //將與下標(biāo)為0的頂點有邊的權(quán)值存入Lowcost數(shù)組adjvex[i]=0; //這些頂點的adjvex數(shù)組全部初始化為0}//算法核心for(i=1;i<G.vexnum;i++){//只需要循環(huán)N-1次，N為頂點數(shù)min=65535; //tip：因為要找最小值，不妨先設(shè)取一個最大的值來比較j=0;k=0;//找出lowcost最小的 最小權(quán)值給min，下標(biāo)給kwhile(j<G.vexnum){ //從1號頂點開始找if(lowcost[j]!=0 && lowcost[j]<min){ //不在生成樹中的頂點而且權(quán)值更小的min=lowcost[j]; //更新更小的值k=j; //找到了新的點下標(biāo)給k}j++; //再看下一個頂點}printf(“(%d->%d)”,adjvex[k],k); //打印權(quán)值最小的邊lowcost[k]=0; //將這個頂點加入生成樹//生成樹加入了新的頂點 從下標(biāo)為1的頂點開始更新lowcost數(shù)組值for(j=0;j<G.vexnum;j++){ if(lowcost[j]!=0 && G.arc[k][j]<lowcost[j]){ //如果新加入樹的頂點k使得權(quán)值變小lowcost[j]=G.arc[k][j]; //更新更小的權(quán)值adjvex[j]=k; //修改這條邊鄰接的頂點 也就是表示這條邊是從選出的頂點k指過來的 方便打印 }}} }

算法分析

普利姆算法是雙重循環(huán)，外層循環(huán)次數(shù)為n-1，內(nèi)層并列的兩個循環(huán)次數(shù)都是n。故普利姆算法時間復(fù)雜度為O(n2)
而且時間復(fù)雜度只和n有關(guān)，所以適合稠密圖

克魯斯卡爾（Kruskal）算法——把森林合并成樹

我們知道生成樹是包含n個頂點，n-1條邊的
換一種思路，我們可以從網(wǎng)中的邊這個角度，找最小權(quán)值的邊，直到找到n-1條邊。

思路

將圖中邊按照權(quán)值從小到大排列，然后從最小的邊開始掃描，設(shè)置一個邊的集合來記錄，如果該邊并入不構(gòu)成回路的話，則將該邊并入當(dāng)前生成樹。直到所有的邊都檢測完為止。

排列： 請參考→ 堆
不構(gòu)成回路：請參考→ 并查集

#define MaxSize 100 typedef struct {int a,b; //邊的兩個頂點int weight; //邊的權(quán)值 }Edge; //邊結(jié)構(gòu)體 int Find(int *parent,int x){while(parent[x]>=0) x=parent[x]; //循環(huán)向上尋找下標(biāo)為x頂點的根return x; //while循環(huán)結(jié)束時找到了根的下標(biāo) } Edge edges[MaxEdge]; //邊數(shù)組 int parent[MaxVex]; //父親頂點數(shù)組(并查集) Void MiniSpanTree_Kruskal(MGraph G){int i , n , m;sort(edges); //按權(quán)值由小到大對邊排列（省略了細節(jié)）for(i=0 ; i<G.vexnum ; i++)parent[i]=-1; //初始化：各個頂點單獨形成一個集合for(i=0 ; i<G.arcnum ; i++){ //掃描每條邊n=Find(parent,edges[i].a); //n是這條邊第一個頂點的根頂點所在下標(biāo)m=Find(parent,edges[i].b); //m是這條邊第二個頂點的根頂點所在下標(biāo)if(n!=m){ //根頂點不相同 這條邊不會構(gòu)成環(huán)parent[n]=m; //并操作//作為生成樹的一條邊打印出來printf(“(%d->%d) ”,edges[i].a,edges[i].b); }} }

看一個例子，視頻講解

克魯斯卡爾算法操作分為對邊的權(quán)值排序部分和一個單重for循環(huán)，它們是并列關(guān)系，由于排序耗費時間大于單重循環(huán)，所以克魯斯卡爾算法的主要時間耗費在排序上。排序和圖中邊的數(shù)量有關(guān)系，所以適合稀疏圖。

最短路徑

問題分類

單源最短路徑問題：從某固定源點出發(fā)，求其到所有其他頂點的最短路徑
多源最短路徑問題：求任意兩頂點間的最短路徑

迪杰斯特拉算法

該算法設(shè)置一個集合S記錄已求得的最短路徑的頂點，可用一個數(shù)組s[]來實現(xiàn)，初始化為0，當(dāng)s[vi]=1時表示將頂點vi放入S中，初始時把源點v0放入S中。此外，在構(gòu)造過程中還設(shè)置了兩個輔助數(shù)組：
dist[]：記錄了從源點v0到其他各頂點當(dāng)前的最短路徑長度，dist[i]初值為arcs[v0][i]。
path[]：path[i]表示從源點到頂點i之間的最短路徑的前驅(qū)結(jié)點，在算法結(jié)束時，可根據(jù)其值追溯得到源點v0到頂點vi的最短路徑。

假設(shè)從頂點0出發(fā)，也就是頂點0為源點，集合S最初只包含頂點0，鄰接矩陣arcs表示帶權(quán)有向圖，arcs[i][j]表示有向邊<i，j>的權(quán)值，若不存在有向邊<i，j>，則arcs[i][j]為∞。Dijkstra算法的步驟如下：
1）初始化：集合S初始為{0}，dist[]的初始值dist[i]=arcs[0][i]，i=1，2，…，n-1。
2）找出dist[]中的最小值dist[j]，將頂點j加入集合S，即修改s[vj]=1。
3）修改從v0出發(fā)到集合V-S上任一頂點vk可達的最短路徑長度：如果dist[j] + arcs[j][k]< dist[k]，則令dist[k]=dist[j] + arcs[j][k]。另外更新path[k]=j(也就是頂點j加入集合之后如果有新的路徑使得到頂點k路徑變短的話就將到頂點k的路徑長度修改成較短的)
4）重復(fù)2）～3）操作共n-1次，直到所有的頂點都包含在S中。

具體過程可參考 視頻講解

Void Dijkstra(MGraph G,int v,int path[ ],int dist[ ]){ //v是源點的下標(biāo) int s[maxSize]; //數(shù)組s記錄當(dāng)前找到了到哪些頂點的最短路徑 找到了對應(yīng)值為1 沒找的對應(yīng)值為0int i,j,min,u; //初始化 將path dist s 數(shù)組的初值確定for(i=0 ; i<G.vexnum ; i++){dist[i]=G.edge[v][i]; //dist初值為源點到各個頂點的邊的權(quán)值s[i]=0; //一開始沒有一個頂點if(G.edge[v][i]<65535)path[i]=v; //與源點連通的頂點的path值存源點下標(biāo)else path[i]=-1;//剛開始到源點沒有路徑的頂點path值為-1}s[v]=1; //源點加入集合spath[v]=-1; //源點不存在到自身的路徑//下面的循環(huán)中包含兩部分作用：//①內(nèi)層第一個for循環(huán)是找到 到剩余頂點中距離最小的 頂點u 并把它加入最短路徑//②內(nèi)層第二個for循環(huán)是由新加入的頂點u來判斷是否找到了新的更短路徑，如果有就更新，沒有就不做任何操作for(i=0;i<G.vexnum;i++){min=65535;for(j=0;j<G.vexnum;j++){if(s[j]==0&&dist[j]<min){ //從剩余的頂點中找到距離最小的頂點u=j; //u用于保存當(dāng)前找到的距離最小的頂點下標(biāo) 當(dāng)循環(huán)結(jié)束u保存的就是最小距離的頂點下標(biāo)min=dist[j]; }}s[u]=1;//到u的距離是最小的，所以把頂點u加入最短路徑for(i=0;i<G.vexnum;i++){min=65535;for(j=0;j<G.vexnum;j++){if(s[j]==0&&dist[j]<min){ //從剩余的頂點中找到距離最小的頂點u=j; //u用于保存當(dāng)前找到的距離最小的頂點下標(biāo) 當(dāng)循環(huán)結(jié)束u保存的就是最小距離的頂點下標(biāo)min=dist[j]; }} s[u]=1;//到u的距離是最小的，所以把頂點u加入最短路徑for(j=0;j<G.vexnum;j++){if(s[j]==0 && dist[u]+G.Edges[u][j]<dist[j]){dist[j]=dist[u]+G.Edges[u][i];//如果由新加入最短路徑的頂點u到其他剩余頂點的距離變短了則//修改到剩余頂點的距離為較小值 path[j]=u;//這條較短的路徑是由頂點u過來的 } }}} }

時間復(fù)雜度

迪杰斯特拉算法的核心部分在于一個雙重循環(huán)，這個雙重循環(huán)的內(nèi)循環(huán)又是兩個并列的單重for循環(huán)組成(找距離最小頂點和更新距離),任意取其中一個循環(huán)中的操作為基本操作，都可以得出迪杰斯特拉算法的時間復(fù)雜度為O(n2) 其中n為圖中的頂點數(shù)。
迪杰斯特拉算法不能用于權(quán)值有負數(shù)的圖，不然結(jié)果會出錯！

弗洛伊德算法

算法思想

遞推產(chǎn)生一個n階方陣序列A(?1)，A(0)，…，A(k)，…，A(n?1)
其中A(k)[i][j]表示從頂點vi到頂點vj的路徑長度，k表示繞行第k個頂點的運算步驟。初始時，對于任意兩個頂點vi和vj，若它們之間存在邊，則以此邊上的權(quán)值作為它們之間的最短路徑長度；若它們之間不存在有向邊，則以∞作為它們之間的最短路徑長度。以后逐步嘗試在原路徑中加入頂點k(k=0，1，…，n-1)作為中間頂點。如果增加中間頂點后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑。

void Floyd(MGraph G,int Path[][]){int i, j, k ;int A[MaxSize][MaxSize];//對數(shù)組A[][]和Path[][]進行初始化for(i=0; i<G.vexnums; i++){for(j=0; j<G.vexnums; j++){A[i][j]=G.Edges[i][j];Path[i][j]=-1;}}for(k=0; k<G.vexnums; k++){for(i=0; i<G.vexnums; i++){for(j=0; j<G.vexnums; j++){if(A[i][j]>A[i][k]+A[k][j]){//如果頂點i到頂點j的距離比頂點i經(jīng)過頂點k到頂點j的距離長，則更新從頂點i到頂點j的距離為較小值，并且存儲k表示路徑經(jīng)過頂點kA[i][j]=A[i][k]+A[k][j];Path[i][j]=k;}}}} }

弗洛伊德算法的核心為一個三重循環(huán)，所以時間復(fù)雜度為O(n3) 其中n是圖中的頂點數(shù)。

拓撲排序

AOV

如果我們把每個環(huán)節(jié)看成圖中一個頂點，在這樣一個有向圖中，用頂點表示活動，用弧表示活動之間的優(yōu)先關(guān)系，那么這樣的有向圖稱為AOV網(wǎng)(Activity On Vertex)
由于弧是用來表示活動之間的優(yōu)先關(guān)系，或者說AOV網(wǎng)具有實際的意義，那么AOV網(wǎng)顯然是不能有回路的
有向無環(huán)圖也叫做DAG圖

拓撲序列是對圖中所有的頂點，如果存在一條從頂點A到頂點B的路徑，那么在排序中頂點A出現(xiàn)在頂點B的前面。

拓撲排序就是對一個有向圖構(gòu)造拓撲序列的過程，構(gòu)造會有兩種結(jié)果：

如果此圖全部頂點都被輸出了，說明它是不存在回路的AOV網(wǎng)；

如果沒有輸出全部頂點，則說明這個圖存在回路，不是AOV網(wǎng)。

拓撲排序算法

從AOV網(wǎng)中選擇一個入度為0的頂點輸出，然后刪去此頂點，并刪除以此頂點為弧尾的弧。重復(fù)這個步驟直到輸出圖中全部頂點，或者找不到入度為0的頂點為止。
一個DAG的拓撲排序不唯一
由于拓撲排序需要刪除邊和頂點，所以使用鄰接表存儲圖比較方便。

bool TopologicalSort(Graph G){InitStack(S); //初始化棧，存儲入度為0的頂點for(int i=0;i<G.vexnum;i++)if(indegree[i]==0)Push(S,i); //將所有入度為0的頂點進棧int count=0; //計數(shù)，記錄當(dāng)前已經(jīng)輸出的頂點數(shù)while(!IsEmpty(S)){ //棧不空，則存在入度為0的頂點Pop(S,i); //棧頂元素出棧pritnf(“%d”,G.adjlist[i]);for(ArcNode *p=G.vertices[i].firstarc; p; p=p->nextarc){v=p->adjvex; //取這條弧指向的頂點if(!(--indegree[v]))Push(S,v); //入度減1為0，則入棧}}if(count<G.vexnum)return false; //排序失敗，有向圖中有回路else return true; //拓撲排序成功 }

拓撲排序?qū)OV圖需要打印圖中所有頂點，而且由于要刪除邊(實際沒有刪除，只是尋找入度為0的頂點)所以對所有邊也要進行掃描，所以這個算法的時間復(fù)雜度為$O(|V|+|E|)$

拓撲排序從入度為0的頂點開始篩選，對應(yīng)的實際意義是工程可以從這個活動開始或者繼續(xù)。

拓撲序列可以不唯一，當(dāng)活動排成線性，則拓撲序列是唯一的。

對于一般的圖，如果它的鄰接矩陣是三角矩陣，則存在拓撲序列；反之則不一定成立
只要按照序號從小到大或者從大到小的順序就能得到這個鄰接矩陣為三角矩陣的圖的拓撲序列。

上三角：0 1 2 3 下三角：3 2 1 0

關(guān)鍵路徑

AOE(Activity On Edge):在一個表示工程的帶權(quán)有向圖中，用頂點表示事件，用有向邊表示活動，用邊上的權(quán)值表示活動的持續(xù)時間，這種有向圖的邊表示活動的網(wǎng)稱為AOE網(wǎng)。

活動是在邊上，邊上的權(quán)值表示的是這個活動所需要耗費的時間。AOE網(wǎng)是在AOE的基礎(chǔ)上來分析工程的最少需要時間。或者是為了縮短工期，需要找出哪些活動是要加快的。
開始時間為0 設(shè)定造好各個模塊的時間為5 因為最長路徑為5
造輪子最早發(fā)生的時間：0 最晚發(fā)生的時間：3
造零件最早發(fā)生的時間：0 最晚發(fā)生的時間：4
造發(fā)動機最早發(fā)生的時間：0 最晚發(fā)生的時間：0
關(guān)鍵活動的最早發(fā)生時間和最晚發(fā)生時間是一樣的！

例子：

參考資料

王道數(shù)據(jù)結(jié)構(gòu)

超強干貨來襲 云風(fēng)專訪：近40年碼齡，通宵達旦的技術(shù)人生

總結(jié)

以上是生活随笔為你收集整理的【数据结构】图的应用（普利姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、拓扑排序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。