1.最小生成樹：無向連通圖的所有生成樹中有一棵邊的權(quán)值總和最小的生成樹

1.1 問題背景：
假設要在n個城市之間建立通信聯(lián)絡網(wǎng)，則連通n個城市只需要n—1條線路。這時，自然會考慮這樣一個問題，如何在最節(jié)省經(jīng)費的前提下建立這個通信網(wǎng)。在每兩個城市之間都可以設置一條線路，相應地都要付出一定的經(jīng)濟代價。n個城市之間，最多可能設置n(n-1)/2條線路，那么，如何在這些可能的線路中選擇n-1條，以使總的耗費最少呢?

1.2 分析問題（建立模型）：

可以用連通網(wǎng)來表示n個城市以及n個城市間可能設置的通信線路，其中網(wǎng)的頂點表示城市，邊表示兩城市之間的線路，賦于邊的權(quán)值表示相應的代價。對于n個頂點的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個通信網(wǎng)。即無向連通圖的生成樹不是唯一的。連通圖的一次遍歷所經(jīng)過的邊的集合及圖中所有頂點的集合就構(gòu)成了該圖的一棵生成樹，對連通圖的不同遍歷，就可能得到不同的生成樹。

圖 G5無向連通圖的生成樹 為(a)、(b)和(c)圖所示：

G5

G5的三棵生成樹：

可以證明，對于有n 個頂點的無向連通圖，無論其生成樹的形態(tài)如何，所有生成樹中都有且僅有n－1 條邊。

1.3最小生成樹的定義：

如果無向連通圖是一個網(wǎng)，那么，它的所有生成樹中必有一棵邊的權(quán)值總和最小的生成樹，我們稱這棵生成樹為最小生成樹，簡稱為最小生成樹。

最小生成樹的性質(zhì)：
假設N=(V,{ E}) 是個連通網(wǎng)，U是頂點集合V的一個非空子集，若（u,v）是個一條具有最小權(quán)值(代價)的邊，其中，

則必存在一棵包含邊（u,v）的最小生成樹。

1.4 解決方案：

兩種常用的構(gòu)造最小生成樹的算法：普里姆（Prim）和克魯斯卡爾（Kruskal）。他們都利用了最小生成樹的性質(zhì)

1.普里姆（Prim）算法：有線到點，適合邊稠密。時間復雜度O(N^2)

假設G＝（V，E）為連通圖，其中V 為網(wǎng)圖中所有頂點的集合，E 為網(wǎng)圖中所有帶權(quán)邊的集合。設置兩個新的集合U 和T，其中

集合U（頂點集） 用于存放G 的最小生成樹中的頂點，

集合T （邊集合）存放G 的最小生成樹中的邊。

T ，U的初始狀態(tài)：令集合U 的初值為U＝{u1}（假設構(gòu)造最小生成樹時，從頂點u1 出發(fā)），集合T 的初值為T＝{}。

Prim 算法的思想是：從所有u∈U，v∈V－U 的邊中，選取具有最小權(quán)值的邊（u，v）∈E，將頂點v 加入集合U 中，將邊（u，v）加入集合T 中，如此不斷重復，直到U＝V 時，最小生成樹構(gòu)造完畢，這時集合T 中包含了最小生成樹的所有邊。

Prim 算法可用下述過程描述，其中用wuv 表示頂點u 與頂點v 邊上的權(quán)值。
（1）U＝{u1},T={};
（2）while (U≠V)do
(u，v)＝min{wuv；u∈U，v∈V－U }
T＝T＋{(u，v)}
U＝U＋{v}
（3）結(jié)束。
按照Prim 方法，從頂點1 出發(fā)，該網(wǎng)的最小生成樹的產(chǎn)生過程如圖：

為實現(xiàn)Prim 算法，需設置兩個輔助closedge，用來保存U到集合V－U 的各個頂點中具有最小權(quán)值的邊的權(quán)值。對每個Vi∈（V-U ）在輔助數(shù)組中存在一個相應的分量closedge[i-1],它包括兩個域：

typedef struct ArcNode

{

int adjvex; //adjex域存儲該邊依附的在U中的頂點
VrType lowcost; //lowcost域存儲該邊上的權(quán)重
}closedge[MAX_VERTEX_NUM];

顯然：

初始狀態(tài)時，U＝{v1}(u1 為出發(fā)的頂點),則到V-U 中各項中最小的邊，即依附頂點v1的各條邊中，找到一條代價最小的邊（u0，v0）= （1，3）為生成樹上一條邊。
同時將v0（=v3）并入集合U中。然后修改輔助數(shù)組的值。

1）將closedge[2].lowcost = 0；//表示頂點V3三已經(jīng)并入U

2) 由于邊（v2,v3）的權(quán)值小于closedge[1].lowcost，故需修改closedge[1]為邊（v2,v3）及其權(quán)值，同理修改closedge[4]，closedge[5].

closedge[1].adjvex = 3.

closedge[1].lowcost = 5.

closedge[4].adjvex = 1.

closedge[4].lowcost = 5.

closedge[5].adjvex = 3.

closedge[5].lowcost = 6.

以此類推，直至U = V;

下圖給出了在用上述算法構(gòu)造網(wǎng)圖7.16的最小生成樹的過程中：

Prim 算法實現(xiàn)：

按照算法框架:

（1）U＝{u1},T={};
（2）while (U≠V)do
(u，v)＝min{wuv；u∈U，v∈V－U }
T＝T＋{(u，v)}
U＝U＋{v}
（3）結(jié)束。
當無向網(wǎng)采用二維數(shù)組存儲的鄰接矩陣存儲時，Prim 算法的C 語言實現(xiàn)為：

//記錄從頂點集U到V—U的代價最小的邊的輔助數(shù)組定義： 
 // struct{ 
 // VertexType adjvex； 
 // VRType lowcost； 
 // }closedge[ MAX_VERTEX_NUM ] 
void MiniSpanTree_PRIM (MGraph G，VertexType u){ 
//用普里姆算法從第u個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹T，輸出T的各條邊。 
 k =LocateVex(G，u)； 
 for(j=0； j<G.vexnum； ++j) 
  if(j!=k) closedge[j] ={u ,G.arcs[k][j].adj}; // {adjvex , lowcost} 
 closedge[k].lowcost =0； //初始，U={u} 
 for( i=1；i<G.vexnum；++i){ //選擇其余G.vexnum-1個頂點 
  k=minimum(closedge)； 
  printf(closedge[k].adjvex, G.vexs[k]);//輸出生成樹的邊 
  //第k頂點并入U集 
  closedge[k].lowcost=0; 
  for(j=0; j<G.vexnum; ++j) 
   if (G.acrs[k][j].adj<closedge[j].lowcost) closedge[j]={G.vexs[k],G.arcs[k][j].adj}; 
 }//for 
}//MiniSpanTree 

假設網(wǎng)中有n個頂點，則第一個進行初始化的循環(huán)語句的頻度為n，第二個循環(huán)語句的頻度為n-1。其中有兩個內(nèi)循環(huán)：其一是在closedge[v].lowcost中求最小值，其頻度為n-1；其二是重新選擇具有最小代價的邊，其頻度為n。 由此，普里姆算法的時間復雜度為O(n2)，與網(wǎng)中的邊數(shù)無關(guān)，因此適用于求邊稠密的網(wǎng)的最小生成樹。
2.克魯斯卡爾（Kruskal） :由點到線，適合邊稀疏的網(wǎng)。時間復雜度：O(e * loge)

Kruskal 算法是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。

基本思想是：

1) 設無向連通網(wǎng)為G＝（V，E），令G 的最小生成樹為T，其初態(tài)為T＝（V，{}），即開始時，最小生成樹T 由圖G 中的n 個頂點構(gòu)成，頂點之間沒有一條邊，這樣T 中各頂點各自構(gòu)成一個連通分量。

2) 在E中選擇代價最小的邊，若該邊依附的頂點落在T中不同的連通分量，則將此邊加入到T中，否則舍棄此邊而選擇下一條邊（若該邊依附的兩個頂點屬于同一個連通分量，則舍去此邊，以免造成回路）。依此類推，當T 中的連通分量個數(shù)為1 時，此連通分量便為G 的一棵最小生成樹。

按照Kruskal 方法構(gòu)造最小生成樹的過程如圖所示：

在構(gòu)造過程中，按照網(wǎng)中邊的權(quán)值由小到大的順序，不斷選取當前未被選取的邊集中權(quán)值最小的邊。依據(jù)生成樹的概念，n 個結(jié)點的生成樹，有n－1 條邊，故反復上述過程，直到選取了n－1 條邊為止，就構(gòu)成了一棵最小生成樹。

Kruskal 算法的實現(xiàn)：
算法的框架：

構(gòu)造非連通圖T＝（V，{}）

k = i= 0；//k為邊數(shù)

while（k《< n-1） {

i++;

檢查邊E中第i條邊的權(quán)值

最小邊（u，v）

若（u，v） 加入T不是T產(chǎn)生回路，

則（u，v）加入T，且k++

}

c語言實現(xiàn)：

C 語言實現(xiàn)Kruskal 算法，其中函數(shù)Find 的作用是尋找圖中頂點所在樹的根結(jié)點在數(shù)組father 中的序號。需說明的是，在程序中將頂點的數(shù)據(jù)類型定義成整型，而在實際應用中，可依據(jù)實際需要來設定。

typedef int elemtype; 
typedef struct { 
elemtype v1; 
elemtype v2; 
int cost; 
}EdgeType; 
void Kruskal（EdgeType edges[ ]，int n） 
/*用Kruskal 方法構(gòu)造有n 個頂點的圖edges 的最小生成樹*/ 
{ int father[MAXEDGE]; 
int i,j,vf1,vf2; 
for (i=0;i<n;i++) father[i]=-1; 
i=0;j=0; 
while(i<MAXEDGE && j<n-1) 
{ vf1=Find(father,edges[i].v1); 
vf2=Find(father,edges[i].v2); 
if (vf1!=vf2) 
{ father[vf2]=vf1; 
j++; 
printf(“%3d%3d\n”,edges[i].v1,edges[i].v2); 
} 
i++; 
} 
} 
 
//find 函數(shù) 
int Find（int father[ ]，int v） 
/*尋找頂點v 所在樹的根結(jié)點*/ 
{ int t; 
t=v; 
while(father[t]>=0) 
t=father[t]; 
return(t); 
} 
 

2. AOV網(wǎng)與拓撲排序：由偏序定義得到拓撲有序的操作便是拓撲排序。建立模型是AOV網(wǎng)
2. 1．AOV網(wǎng)(Activity on vertex network)

所有的工程或者某種流程可以分為若干個小的工程或階段，這些小的工程或階段就稱為活動。若以圖中的頂點來表示活動，有向邊（?。┍硎净顒又g的優(yōu)先關(guān)系，則這樣活動在頂點上的有向圖稱為AOV 網(wǎng)（Activity On Vertex Network）。在AOV 網(wǎng)中，若從頂點i到頂點j之間存在一條有向路徑，稱頂點i是頂點j的前驅(qū)，或者稱頂點j 是頂點i的后繼。若<i,j>是圖中的弧，則稱頂點i是頂點j 的直接前驅(qū)，頂點j 是頂點i 的直接后驅(qū)。

AOV 網(wǎng)中的弧表示了活動之間存在的制約關(guān)系。例如，計算機專業(yè)的學生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè)。學生按照怎樣的順序來學習這些課程呢？這個問題可以被看成是一個大的工程，其活動就是學習每一門課程。這些課程的名稱與相應代號如表所示。

課程之間的優(yōu)先關(guān)系圖：

該圖的拓撲有序系列：

注意：
在AOV-網(wǎng)中不應該出現(xiàn)有向環(huán)，因為存在環(huán)意味著某項活動應以自己為先決條件。若設計出這樣的流程圖，工程便無法進行。而對程序的數(shù)據(jù)流圖來說，則表明存在一個死循環(huán)。因此，對給定的AOV-網(wǎng)應首先判定網(wǎng)中是否存在環(huán)。檢測的辦法是對有向圖構(gòu)造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV-網(wǎng)中必定不存在環(huán)。

2.2．拓撲排序

離散數(shù)學基礎(chǔ)知識：

首先復習一下離散數(shù)學中的偏序集合與全序集合兩個概念。

若集合A 中的二元關(guān)系R 是自反的、非對稱的和傳遞的，則R 是A 上的偏序關(guān)系。集合A 與關(guān)系R 一起稱為一個偏序集合。

若R 是集合A 上的一個偏序關(guān)系，如果對每個a、b∈A 必有aRb 或bRa ，則R 是A上的全序關(guān)系。集合A 與關(guān)系R 一起稱為一個全序集合。

直觀地看，偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。
[例如]，圖7.25所示的兩個有向圖，圖中弧(x,y)表示x≤y，則(a)表示偏序，(b)表示全序。若在(a)的有向圖上人為地加一個表示v2≤v3的弧(符號“≤”表示v2領(lǐng)先于v3)，則(a)表示的亦為全序，且這個全序稱為拓撲有序(Topological Order)，而由偏序定義得到拓撲有序的操作便是拓撲排序。

2.3 拓撲排序算法

對AOV 網(wǎng)進行拓撲排序的方法和步驟是：
1、從AOV 網(wǎng)中選擇一個沒有前驅(qū)的頂點（該頂點的入度為0）并且輸出它；
2、從網(wǎng)中刪去該頂點，并且刪去從該頂點發(fā)出的全部有向邊；
3、重復上述兩步，直到剩余的網(wǎng)中不再存在沒有前驅(qū)的頂點為止。

這樣操作的結(jié)果有兩種：一種是網(wǎng)中全部頂點都被輸出，這說明網(wǎng)中不存在有向回路；另一種就是網(wǎng)中頂點未被全部輸出，剩余的頂點均不前驅(qū)頂點，這說明網(wǎng)中存在有向回路。

以下圖(a)中的有向圖為例，圖中v1，和v6沒有前驅(qū)，則可任選一個。假設先輸出v6, 在刪除v6及弧<v6，v4>，<v6，v5>之后，只有頂點v1沒有前驅(qū)，則輸出vl且刪去vl及弧<v1，v2>、<v1，v3>和<v1, v4>，之后v3和v4都沒有前驅(qū)。依次類推，可從中任選一個繼續(xù)進行。最后得到該有向圖的拓撲有序序列為：

v6 - v1 - v4 - v3 - v2 - v5

圖AOV-網(wǎng)及其拓撲有序序列產(chǎn)生的過程
(a)AOV-網(wǎng)；(b)輸出v6之后；(c)輸出v1之后；(d)輸出v4之后；(e)輸出v3之后；(f)輸出v2之后
為了實現(xiàn)上述算法，對AOV 網(wǎng)采用鄰接表存儲方式，并且鄰接表中頂點結(jié)點中增加一個記錄頂點入度的數(shù)據(jù)域，即頂點結(jié)構(gòu)設為：

頂點表結(jié)點結(jié)構(gòu)的描述改為：
typedef struct vnode{ /*頂點表結(jié)點*/
int count /*存放頂點入度*/
VertexType vertex; /*頂點域*/
EdgeNode * firstedge; /*邊表頭指針*/
}VertexNode;
當然也可以不增設入度域，而另外設一個一維數(shù)組來存放每一個結(jié)點的入度。算法中可設置了一個堆棧，凡是網(wǎng)中入度為0 的頂點都將其入棧。為此，拓撲排序的算法步驟為：
1、將沒有前驅(qū)的頂點（count 域為0）壓入棧；
2、從棧中退出棧頂元素輸出，并把該頂點引出的所有有向邊刪去，即把它的各個鄰接頂點的入度減1；
3、將新的入度為0 的頂點再入堆棧；
4、重復②～④，直到棧為空為止。此時或者是已經(jīng)輸出全部頂點，或者剩下的頂點中沒有入度為0 的頂點。

為了避免重復檢測入度為零的頂點，可另設一棧暫存所有入度為零的頂點。

Status Topological Sort(ALGraph G){ 
//有向圖G采用鄰接表存儲結(jié)構(gòu)。 
//若G無回路，則輸出G的頂點的1個拓撲序列并返回OK，否則ERROR。 
 FindInDegree(G，indegree)； //對各頂點求入度indegree[0..vernum-1] 
 InitStack(S)； 
 for(i=0；i<G.vexnum； ++i) 
 if(!indegree[i])Push(S，i) //建零入度頂點棧,s入度為0者進棧 
 count=0； //對輸出頂點計數(shù) 
 while (!StackEmpty(S)) { 
  Pop(S，i)； 
  printf(i，G.vertices[i].data)； ++count； //輸出i號頂點并計數(shù) 
  for(p=G.vertices[i].firstarc；p； p=p—>nextarc) { 
   k=p—>adivex； //對i號頂點的每個鄰接點的入度減1 
   if(！(--indegree[k]))Push(S，k)；//若入度減為0，則入棧 
  }//for 
 }//while 
 if(count<G.vexnum) return ERROR； //該有向圖有回路 
 else return OK； 
}//TopologicalSort 

3. 關(guān)鍵路徑(AOE網(wǎng))：在AOE-網(wǎng)中有些活動可以并行地進行，所以完成工程的最短時間是從開始點到完成點的最長路徑的長度，路徑長度最長的路徑叫做關(guān)鍵路徑(Critical Path)。

3.1AOE網(wǎng)：（Activity on edge network）
AOE網(wǎng)示意圖若在帶權(quán)的有向圖中，以頂點表示事件，以有向邊表示活動，邊上的權(quán)值表示活動的開銷（如該活動持續(xù)的時間），則此帶權(quán)的有向圖稱為AOE網(wǎng)。

3.2 實際問題：

如果用AOE網(wǎng)來表示一項工程，那么，僅僅考慮各個子工程之間的優(yōu)先關(guān)系還不夠，更多的是關(guān)心整個工程完成的最短時間是多少；哪些活動的延期將會影響整個工程的進度，而加速這些活動是否會提高整個工程的效率。因此，通常在AOE網(wǎng)中列出完成預定工程計劃所需要進行的活動，每個活動計劃完成的時間，要發(fā)生哪些事件以及這些事件與活動之間的關(guān)系，從而可以確定該項工程是否可行，估算工程完成的時間以及確定哪些活動是影響工程進度的關(guān)鍵。

如圖是一個假想的有11項活動的AOE-網(wǎng)：

其中有9個事件v1，v2，v3，…，v9，每個事件表示在它之前的活動已經(jīng)完成，在它之后的活動可以開始。如v1表示整個工程開始，v9表示整個工程結(jié)束，v5表示a4和a5已經(jīng)完成，a7和a8可以開始。與每個活動相聯(lián)系的數(shù)是執(zhí)行該活動所需的時間。比如，活動a1需要6天，a2需要4天等。

和AOV-網(wǎng)不同，對AOE-網(wǎng)有待研究的問題是：
(1)完成整項工程至少需要多少時間?
(2)哪些活動是影響工程進度的關(guān)鍵?

3.3 關(guān)鍵路徑

由于在AOE-網(wǎng)中有些活動可以并行地進行，所以完成工程的最短時間是從開始點到完成點的最長路徑的長度(這里所說的路徑長度是指路徑上各活動持續(xù)時間之和，不是路徑上弧的數(shù)目)。路徑長度最長的路徑叫做關(guān)鍵路徑(Critical Path)。

AOE網(wǎng)有關(guān)的概念：
1)路徑長度：路徑上各個活動的持續(xù)時間之和

2)完成工程的最短時間：由于AOE網(wǎng)中有活動是并行進行的，所以完成工程的最短時間就是從開始點到完成點的最長路勁長度。
3)活動最早開始時間(earlist time)(e(i))：從開始點到頂點vi的最長路徑稱為事件vi的最早發(fā)生時間。這個時間決定了以vi為尾的弧表示的活動的最早開始時間.
4)活動最晚開始時間(latest time)(l(i))：在不推遲整個工程完成的前提下，活動最遲開始的時間
5)完成活動的時間余量：該活動的最遲開始時間減去最早開始時間
6)關(guān)鍵路徑(critical path)：路徑長度最長的路徑稱為關(guān)鍵路徑
7)關(guān)鍵活動(critical activity):關(guān)鍵路徑上的活動稱為關(guān)鍵活動，關(guān)鍵活動的特點是:e(i)=l(i)分析關(guān)鍵路徑的目的就是辨別在整個工程中哪些是關(guān)鍵活動，以便爭取提高關(guān)鍵活動的工作效率，縮短整個工程的工期。
3.4 解決方案：
由上分析可知，辨別關(guān)鍵活動就是要找e(i)=l(i)的活動。為了求得AOE-網(wǎng)中活動的e(i)和l(i)， 首先求事件的最早發(fā)生時間ve(j)和最遲發(fā)生時間vl(j)。如果活動ai由弧<j,k>表示，其持續(xù)時間記為dut(<j,k>),則有如下關(guān)系：

e(i ) = ve(j)

l(i) = vl(k)-dut(<j,k>)

求ve(j)和vl(j)需分兩步進行：
（1）從ve(0)開始向前遞推

其中，T是所有以第j個頂點為頭的弧的結(jié)合。
（2）從vl(n-1)=ve(n-1)起向后遞推

其中，S是所有以第i個頂點為尾的弧的集合。

這兩個遞推公式的計算必須分別在拓撲有序和逆拓撲有序的前提下進行。也就是說ve(j-1)必須在vj的所有前驅(qū)的最早發(fā)生時間求得之后才能確定，而vl(j-1)則必須在vj的所有后繼的最遲發(fā)生時間求得之后才能確定。因此，可以在拓撲排序的基礎(chǔ)上計算ve(j-1)和vl(j-1)。

3.5 關(guān)鍵路徑的算法：
(1)輸入e條弧<j，k>，建立AOE-網(wǎng)的存儲結(jié)構(gòu)；
(2)從源點v0出發(fā)，令ve[0]=0，按拓撲有序求其余各頂點的最早發(fā)生時間ve[i] (1≤i≤n-1)。如果得到的拓撲有序序列中頂點個數(shù)小于網(wǎng)中頂點數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行步驟(3)。
(3)從匯點vn出發(fā)，令vl[n-1]=ve[n-1]，按逆拓撲有序求其余各頂點的最遲發(fā)生時間vl[i](n-2≥i≥0)；
(4)根據(jù)各頂點的ve和vl值，求每條弧s的最早開始時間e(s)和最遲開始時間 l(s)。若某條弧滿足條件e(s)=l(s)，則為關(guān)鍵活動。

先將拓撲排序算法：TopologicalOrder（）

CriticalPath便為求關(guān)鍵路徑的算法：

Status TopologicalOrder(ALGraph G，Stack &T){ 
//有向網(wǎng)G采用鄰接表存儲結(jié)構(gòu)，求各頂點事件的最早發(fā)生時間ve(全局變量)。 
//T為拓撲序列頂點棧，s為零入度頂點棧。若G無回路，返回G的一拓撲序列，函數(shù)值為OK，否則ERROR。 
 FindInDegree(G，indegree)；//對各頂點求入度indegree[0..vernum-1] 
 for(i=0；i<G.vexnum； ++i)  
 if(!indegree[i])Push(S，i) //建零入度頂點棧,s入度為0者進棧 
 InitStack(T)； count=0；ve[0..G.vexnum-1]=0； //初始化 
 while(!StackEmpty(S)){ //j號頂點入T棧并計數(shù) 
  Pop(S，j)； Push(T，j)；++count; 
  for(p=G.vertices[j].firstarc；p；p=p->nextarc){ 
   k=p—>adjvex； //對i號頂點的每個鄰接點的入度減l 
   if(--indegree[k]==0)Push(S，k)； //若入度減為0，則入棧 
   if(ve[j]+*(p->info)>ve[k] ) ve[k]=ve[j]+*(p->info)； 
 
   }//for *(p->info)=dut(<j,k>) 
 
 }//while 
 if(count<G.vexnum) return ERROR； //該有向網(wǎng)有回路 
 else return OK； 
 
}//TopologicalOrder 
 
 
 
 
Status CriticalPath (ALGraph G){ //G為有向網(wǎng)，輸出G的各項關(guān)鍵活動。 
 if(!TopologicalOrder(G，T)) return ERROR； //初始化頂點事件的最遲發(fā)生時間 
 vl[0..G.vexnum-1]=ve[0..C.vexnum-1]； //按拓撲逆序求各頂點的vl值 
 while(!StackEmpty(T)) 
  for( Pop(T, j), p=G.vertices[j].firstarc；p； p=p->nextarc){ 
   k=p->adjvex； dut=*(p—>info)； //dut<i，k> 
   if(vl[k]-dut<vl[j]) vl[j]=vl[k]-dut； }//for 
 for(j=0；j<G.vexnum；++j) //求ee，el和關(guān)鍵活動 
  for(p=G.vertices[j]；p；p=p->nextarc){ 
   k=p->adjvex； dut=*(p—>info)；ee=ve[j]；el=v1[k]-dut；tag = (ee==e1) ? ‘*' ： ‘'； 
   printf(j，k，dut，ee，el，tag)； //輸出關(guān)鍵活動 
} 
}//CriticalPath 

圖(a)所示網(wǎng)的關(guān)鍵路徑：可見a2、a5和a7為關(guān)鍵活動，組成一條從源點到匯點的關(guān)鍵路徑，如圖(b)所示。

圖(a)所示網(wǎng)的計算結(jié)果:

4. 最短路徑：最短路徑問題是圖研究中的一個經(jīng)典算法問題， 旨在尋找圖（由結(jié)點和路徑組成的）中兩結(jié)點之間的最短路徑。
最短路徑問題是圖的又一個比較典型的應用問題。例如，某一地區(qū)的一個公路網(wǎng)，給定了該網(wǎng)內(nèi)的n 個城市以及這些城市之間的相通公路的距離，能否找到城市A 到城市B 之間一條舉例最近的通路呢？

如果將城市用點表示，城市間的公路用邊表示，公路的長度作為邊的權(quán)值，那么，這個問題就可歸結(jié)為在網(wǎng)圖中，求點A 到點B 的所有路徑中，邊的權(quán)值之和最短的那一條路徑。這條路徑就是兩點之間的最短路徑，并稱路徑上的第一個頂點為源點（Sourse），最后一個頂點為終點（Destination）。

單源點的最短路徑問題：給定帶權(quán)有向圖G＝（V，E）和源點v∈V，求從v 到G 中其余各頂點的最短路徑。在下面的討論中假設源點為v0。

解決問題的迪杰斯特拉算法：

即由迪杰斯特拉（Dijkstra）提出的一個按路徑長度遞增的次序產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，然后參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。

算法的基本思想是：

設置兩個頂點的集合S 和T＝V－S，集合S 中存放已找到最短路徑的頂點，集合T 存放當前還未找到最短路徑的頂點。

初始狀態(tài)時，集合S 中只包含源點v0，然后不斷從集合T 中選取到頂點v0 路徑長度最短的頂點u 加入到集合S 中，集合S 每加入一個新的頂點u，都要修改頂點v0 到集合T 中剩余頂點的最短路徑長度值，集合T 中各頂點新的最短路徑長度值為原來的最短路徑長度值與頂點u 的最短路徑長度值加上u 到該頂點的路徑長度值中的較小值。此過程不斷重復，直到集合T 的頂點全部加入到S 中為止。

Dijkstra 算法的實現(xiàn):

首先，引進一個輔助向量D，它的每個分量D[i] 表示當前所找到的從始點v 到每個終點vi 的最短路徑的長度。它的初態(tài)為：若從v 到vi 有弧，則D[i]為弧上的權(quán)值；否則置D[i]為∞。顯然，長度為：

D[j]=Min{D[i]| vi∈V}
的路徑就是從v 出發(fā)的長度最短的一條最短路徑。此路徑為（v ,vj）。

那么，下一條長度次短的最短是哪一條呢？假設該次短路徑的終點是vk ，則可想而知，這條路徑或者是（v, vk），或者是（v, vj, vk）。它的長度或者是從v 到vk 的弧上的權(quán)值，或者是D[j]和從vj 到vk 的弧上的權(quán)值之和。

依據(jù)前面介紹的算法思想，在一般情況下，下一條長度次短的最短路徑的長度必是：
D[j]=Min{D[i]| vi∈V-S}
其中，D[i] 或者弧（v, vi）上的權(quán)值，或者是D[k]( vk∈S 和?。╲k, vi）上的權(quán)值之和。

根據(jù)以上分析，可以得到如下描述的算法：
（1）假設用帶權(quán)的鄰接矩陣edges 來表示帶權(quán)有向圖，edges[i][j] 表示弧〈vi, vj〉上的權(quán)值。若〈vi, vj〉不存在，則置edges[i][j]為∞（在計算機上可用允許的最大值代替）。S 為已找到從v 出發(fā)的最短路徑的終點的集合，它的初始狀態(tài)為空集。那么，從v 出發(fā)到圖上其余各頂點（終點）vi 可能達到最短路徑長度的初值為：
D[i]= edges[Locate Vex(G,v)][i] vi∈V
（2）選擇vj，使得
D[j]=Min{D[i]| vi∈V-S}
vj 就是當前求得的一條從v 出發(fā)的最短路徑的終點。令
S＝S∪{j}
（3）修改從v 出發(fā)到集合V-S 上任一頂點vk 可達的最短路徑長度。如果
D[j]+ edges[j][k]<D[k]
則修改D[k]為
D[k]=D[j]+ edges[j][k]
重復操作（2）、（3）共n-1 次。由此求得從v 到圖上其余各頂點的最短路徑是依路徑長度遞增的序列。

如圖8.26 所示一個有向網(wǎng)圖G8 的帶權(quán)鄰接矩陣為：

有向網(wǎng)圖G8 的帶權(quán)鄰接矩陣

用C 語言描述的Dijkstra 算法：

void ShortestPath_DIJ(MGraph G，int v0，PathMatrix &P，ShortPathTable &D){ 
 //用Dijkstra算法求有向網(wǎng)G的v0頂點到其余頂點v的最短路徑P[v]及其帶權(quán)長度D[v]。 
 //若P[v][w]為TRUE，則w是從v0到v當前求得最短路徑上的頂點。 
 //final[v]為TRUE當且僅當v∈S，即已經(jīng)求得從v0到v的最短路徑。 
  for(v=0； v<G.vexnum； ++v) { 
  final[v]=FALSE； D[v]=G.arcs[v0][v]； 
  for(w=0； w<G.vexnum； ++w) P[v][w] = FALSE；//設空路徑 
  if (D[v]<INFINITY) { P[v][v0]=TRUE； P[v][v]=TRUE；} 
  }//for 
  D[v0] = 0； final[v0] = TRUE； //初始化，v0頂點屬于S集 
 //開始主循環(huán)，每次求得v0到某個v頂點的最短路徑，并加v到s集。 
  for(i=1; i<G.vexnum；++i){ //其余G.vexnum-1個頂點 
  min = INFINITY； //當前所知離v0頂點的最近距離 
  for(w=0；w<G.vexnum；++w) 
   if(!final[w]) //w頂點在V-S中 
   if(D[w]<min){v=w；min=D[w]；} //w頂點離v0頂點更近 
  final[v]=TRUE； //離v0頂點最近的v加入S集 
  for(w=0；w<G.vexnum；++w) //更新當前最短路徑及距離 
   if(!final[w]&&(min+G.arcs[v][w]<D[w])){ //修改D[w]和P[w] 
   D[w]=min+G.arcs[v][w]；P[w]=P[v]； P[w][w]=TRUE； //P[w]=P[v]+[w] 
   }//if 
  }//for 
 }//ShortestPath_DIJ 

以上就是圖的應用全部詳細介紹，希望對大家的學習有所幫助。

最新評論