詳解圖的應(yīng)用（最小生成樹(shù)、拓?fù)渑判颉㈥P(guān)鍵路徑、最短路徑）
1.最小生成樹(shù)：無(wú)向連通圖的所有生成樹(shù)中有一棵邊的權(quán)值總和最小的生成樹(shù)
1.1 問(wèn)題背景：
假設(shè)要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要n—1條線路。這時(shí)，自然會(huì)考慮這樣一個(gè)問(wèn)題，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通信網(wǎng)。在每?jī)蓚€(gè)城市之間都可以設(shè)置一條線路，相應(yīng)地都要付出一定的經(jīng)濟(jì)代價(jià)。n個(gè)城市之間，最多可能設(shè)置n(n-1)/2條線路，那么，如何在這些可能的線路中選擇n-1條，以使總的耗費(fèi)最少呢?
1.2 分析問(wèn)題（建立模型）：
可以用連通網(wǎng)來(lái)表示n個(gè)城市以及n個(gè)城市間可能設(shè)置的通信線路，其中網(wǎng)的頂點(diǎn)表示城市，邊表示兩城市之間的線路，賦于邊的權(quán)值表示相應(yīng)的代價(jià)。對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹(shù)，每一棵生成樹(shù)都可以是一個(gè)通信網(wǎng)。即無(wú)向連通圖的生成樹(shù)不是唯一的。連通圖的一次遍歷所經(jīng)過(guò)的邊的集合及圖中所有頂點(diǎn)的集合就構(gòu)成了該圖的一棵生成樹(shù)，對(duì)連通圖的不同遍歷，就可能得到不同的生成樹(shù)。
圖 G5無(wú)向連通圖的生成樹(shù) 為(a)、(b)和(c)圖所示：
G5
G5的三棵生成樹(shù)：
可以證明，對(duì)于有n 個(gè)頂點(diǎn)的無(wú)向連通圖，無(wú)論其生成樹(shù)的形態(tài)如何，所有生成樹(shù)中都有且僅有n－1 條邊。
1.3最小生成樹(shù)的定義：
如果無(wú)向連通圖是一個(gè)網(wǎng)，那么，它的所有生成樹(shù)中必有一棵邊的權(quán)值總和最小的生成樹(shù)，我們稱這棵生成樹(shù)為最小生成樹(shù)，簡(jiǎn)稱為最小生成樹(shù)。
最小生成樹(shù)的性質(zhì)：
假設(shè)N=(V,{ E}) 是個(gè)連通網(wǎng)，U是頂點(diǎn)集合V的一個(gè)非空子集，若（u,v）是個(gè)一條具有最小權(quán)值(代價(jià))的邊，其中，
則必存在一棵包含邊（u,v）的最小生成樹(shù)。
1.4 解決方案：
兩種常用的構(gòu)造最小生成樹(shù)的算法：普里姆（Prim）和克魯斯卡爾（Kruskal）。他們都利用了最小生成樹(shù)的性質(zhì)
1.普里姆（Prim）算法：有線到點(diǎn)，適合邊稠密。時(shí)間復(fù)雜度O(N^2)
假設(shè)G＝（V，E）為連通圖，其中V 為網(wǎng)圖中所有頂點(diǎn)的集合，E 為網(wǎng)圖中所有帶權(quán)邊的集合。設(shè)置兩個(gè)新的集合U 和T，其中
集合U（頂點(diǎn)集） 用于存放G 的最小生成樹(shù)中的頂點(diǎn)，
集合T （邊集合）存放G 的最小生成樹(shù)中的邊。
T ，U的初始狀態(tài)：令集合U 的初值為U＝{u1}（假設(shè)構(gòu)造最小生成樹(shù)時(shí)，從頂點(diǎn)u1 出發(fā)），集合T 的初值為T＝{}。
Prim 算法的思想是：從所有u∈U，v∈V－U 的邊中，選取具有最小權(quán)值的邊（u，v）∈E，將頂點(diǎn)v 加入集合U 中，將邊（u，v）加入集合T 中，如此不斷重復(fù)，直到U＝V 時(shí)，最小生成樹(shù)構(gòu)造完畢，這時(shí)集合T 中包含了最小生成樹(shù)的所有邊。
Prim 算法可用下述過(guò)程描述，其中用wuv 表示頂點(diǎn)u 與頂點(diǎn)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 方法，從頂點(diǎn)1 出發(fā)，該網(wǎng)的最小生成樹(shù)的產(chǎn)生過(guò)程如圖：
為實(shí)現(xiàn)Prim 算法，需設(shè)置兩個(gè)輔助closedge，用來(lái)保存U到集合V－U 的各個(gè)頂點(diǎn)中具有最小權(quán)值的邊的權(quán)值。對(duì)每個(gè)Vi∈（V-U ）在輔助數(shù)組中存在一個(gè)相應(yīng)的分量closedge[i-1],它包括兩個(gè)域：
typedef struct ArcNode
{
int adjvex; //adjex域存儲(chǔ)該邊依附的在U中的頂點(diǎn)
VrType lowcost; //lowcost域存儲(chǔ)該邊上的權(quán)重
}closedge[MAX_VERTEX_NUM];
顯然：
初始狀態(tài)時(shí)，U＝{v1}(u1 為出發(fā)的頂點(diǎn)),則到V-U 中各項(xiàng)中最小的邊，即依附頂點(diǎn)v1的各條邊中，找到一條代價(jià)最小的邊（u0，v0）= （1，3）為生成樹(shù)上一條邊。
同時(shí)將v0（=v3）并入集合U中。然后修改輔助數(shù)組的值。
1）將closedge[2].lowcost = 0；//表示頂點(diǎn)V3三已經(jīng)并入U(xiǎn)
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的最小生成樹(shù)的過(guò)程中：
Prim 算法實(shí)現(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é)束。
當(dāng)無(wú)向網(wǎng)采用二維數(shù)組存儲(chǔ)的鄰接矩陣存儲(chǔ)時(shí)，Prim 算法的C 語(yǔ)言實(shí)現(xiàn)為：
//記錄從頂點(diǎn)集U到V—U的代價(jià)最小的邊的輔助數(shù)組定義：
// struct{
// VertexType adjvex；
// VRType lowcost；
// }closedge[ MAX_VERTEX_NUM ]
void MiniSpanTree_PRIM (MGraph G，VertexType u){
//用普里姆算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)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個(gè)頂點(diǎn)
k=minimum(closedge)；
printf(closedge[k].adjvex, G.vexs[k]);//輸出生成樹(shù)的邊
//第k頂點(diǎn)并入U(xiǎn)集
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
假設(shè)網(wǎng)中有n個(gè)頂點(diǎn)，則第一個(gè)進(jìn)行初始化的循環(huán)語(yǔ)句的頻度為n，第二個(gè)循環(huán)語(yǔ)句的頻度為n-1。其中有兩個(gè)內(nèi)循環(huán)：其一是在closedge[v].lowcost中求最小值，其頻度為n-1；其二是重新選擇具有最小代價(jià)的邊，其頻度為n。 由此，普里姆算法的時(shí)間復(fù)雜度為O(n2)，與網(wǎng)中的邊數(shù)無(wú)關(guān)，因此適用于求邊稠密的網(wǎng)的最小生成樹(shù)。
2.克魯斯卡爾（Kruskal） :由點(diǎn)到線，適合邊稀疏的網(wǎng)。時(shí)間復(fù)雜度：O(e * loge)
Kruskal 算法是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹(shù)的方法。
基本思想是：
1) 設(shè)無(wú)向連通網(wǎng)為G＝（V，E），令G 的最小生成樹(shù)為T，其初態(tài)為T＝（V，{}），即開(kāi)始時(shí)，最小生成樹(shù)T 由圖G 中的n 個(gè)頂點(diǎn)構(gòu)成，頂點(diǎn)之間沒(méi)有一條邊，這樣T 中各頂點(diǎn)各自構(gòu)成一個(gè)連通分量。
2) 在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同的連通分量，則將此邊加入到T中，否則舍棄此邊而選擇下一條邊（若該邊依附的兩個(gè)頂點(diǎn)屬于同一個(gè)連通分量，則舍去此邊，以免造成回路）。依此類推，當(dāng)T 中的連通分量個(gè)數(shù)為1 時(shí)，此連通分量便為G 的一棵最小生成樹(shù)。
按照Kruskal 方法構(gòu)造最小生成樹(shù)的過(guò)程如圖所示：
在構(gòu)造過(guò)程中，按照網(wǎng)中邊的權(quán)值由小到大的順序，不斷選取當(dāng)前未被選取的邊集中權(quán)值最小的邊。依據(jù)生成樹(shù)的概念，n 個(gè)結(jié)點(diǎn)的生成樹(shù)，有n－1 條邊，故反復(fù)上述過(guò)程，直到選取了n－1 條邊為止，就構(gòu)成了一棵最小生成樹(shù)。
Kruskal 算法的實(shí)現(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語(yǔ)言實(shí)現(xiàn)：
C 語(yǔ)言實(shí)現(xiàn)Kruskal 算法，其中函數(shù)Find 的作用是尋找圖中頂點(diǎn)所在樹(shù)的根結(jié)點(diǎn)在數(shù)組father 中的序號(hào)。需說(shuō)明的是，在程序中將頂點(diǎn)的數(shù)據(jù)類型定義成整型，而在實(shí)際應(yīng)用中，可依據(jù)實(shí)際需要來(lái)設(shè)定。
typedef int elemtype;
typedef struct {
elemtype v1;
elemtype v2;
int cost;
}EdgeType;
void Kruskal（EdgeType edges[ ]，int n）
/*用Kruskal 方法構(gòu)造有n 個(gè)頂點(diǎn)的圖edges 的最小生成樹(shù)*/
{ 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）
/*尋找頂點(diǎn)v 所在樹(shù)的根結(jié)點(diǎn)*/
{ int t;
t=v;
while(father[t]>=0)
t=father[t];
return(t);
}
2. AOV網(wǎng)與拓?fù)渑判颍?/strong>由偏序定義得到拓?fù)溆行虻牟僮鞅闶峭負(fù)渑判?。建立模型是AOV網(wǎng)
2. 1．AOV網(wǎng)(Activity on vertex network)
所有的工程或者某種流程可以分為若干個(gè)小的工程或階段，這些小的工程或階段就稱為活動(dòng)。若以圖中的頂點(diǎn)來(lái)表示活動(dòng)，有向邊（弧）表示活動(dòng)之間的優(yōu)先關(guān)系，則這樣活動(dòng)在頂點(diǎn)上的有向圖稱為AOV 網(wǎng)（Activity On Vertex Network）。在AOV 網(wǎng)中，若從頂點(diǎn)i到頂點(diǎn)j之間存在一條有向路徑，稱頂點(diǎn)i是頂點(diǎn)j的前驅(qū)，或者稱頂點(diǎn)j 是頂點(diǎn)i的后繼。若<i,j>是圖中的弧，則稱頂點(diǎn)i是頂點(diǎn)j 的直接前驅(qū)，頂點(diǎn)j 是頂點(diǎn)i 的直接后驅(qū)。
AOV 網(wǎng)中的弧表示了活動(dòng)之間存在的制約關(guān)系。例如，計(jì)算機(jī)專業(yè)的學(xué)生必須完成一系列規(guī)定的基礎(chǔ)課和專業(yè)課才能畢業(yè)。學(xué)生按照怎樣的順序來(lái)學(xué)習(xí)這些課程呢？這個(gè)問(wèn)題可以被看成是一個(gè)大的工程，其活動(dòng)就是學(xué)習(xí)每一門課程。這些課程的名稱與相應(yīng)代號(hào)如表所示。
課程之間的優(yōu)先關(guān)系圖：
該圖的拓?fù)溆行蛳盗校?/p>
注意：
在AOV-網(wǎng)中不應(yīng)該出現(xiàn)有向環(huán)，因?yàn)榇嬖诃h(huán)意味著某項(xiàng)活動(dòng)應(yīng)以自己為先決條件。若設(shè)計(jì)出這樣的流程圖，工程便無(wú)法進(jìn)行。而對(duì)程序的數(shù)據(jù)流圖來(lái)說(shuō)，則表明存在一個(gè)死循環(huán)。因此，對(duì)給定的AOV-網(wǎng)應(yīng)首先判定網(wǎng)中是否存在環(huán)。檢測(cè)的辦法是對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該AOV-網(wǎng)中必定不存在環(huán)。
2.2．拓?fù)渑判?/strong>
離散數(shù)學(xué)基礎(chǔ)知識(shí)：
首先復(fù)習(xí)一下離散數(shù)學(xué)中的偏序集合與全序集合兩個(gè)概念。
若集合A 中的二元關(guān)系R 是自反的、非對(duì)稱的和傳遞的，則R 是A 上的偏序關(guān)系。集合A 與關(guān)系R 一起稱為一個(gè)偏序集合。
若R 是集合A 上的一個(gè)偏序關(guān)系，如果對(duì)每個(gè)a、b∈A 必有aRb 或bRa ，則R 是A上的全序關(guān)系。集合A 與關(guān)系R 一起稱為一個(gè)全序集合。
直觀地看，偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。
[例如]，圖7.25所示的兩個(gè)有向圖，圖中弧(x,y)表示x≤y，則(a)表示偏序，(b)表示全序。若在(a)的有向圖上人為地加一個(gè)表示v2≤v3的弧(符號(hào)“≤”表示v2領(lǐng)先于v3)，則(a)表示的亦為全序，且這個(gè)全序稱為拓?fù)溆行?Topological Order)，而由偏序定義得到拓?fù)溆行虻牟僮鞅闶峭負(fù)渑判颉?/p>
2.3 拓?fù)渑判蛩惴?/strong>
對(duì)AOV 網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ê筒襟E是：
1、從AOV 網(wǎng)中選擇一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)（該頂點(diǎn)的入度為0）并且輸出它；
2、從網(wǎng)中刪去該頂點(diǎn)，并且刪去從該頂點(diǎn)發(fā)出的全部有向邊；
3、重復(fù)上述兩步，直到剩余的網(wǎng)中不再存在沒(méi)有前驅(qū)的頂點(diǎn)為止。
這樣操作的結(jié)果有兩種：一種是網(wǎng)中全部頂點(diǎn)都被輸出，這說(shuō)明網(wǎng)中不存在有向回路；另一種就是網(wǎng)中頂點(diǎn)未被全部輸出，剩余的頂點(diǎn)均不前驅(qū)頂點(diǎn)，這說(shuō)明網(wǎng)中存在有向回路。
以下圖(a)中的有向圖為例，圖中v1，和v6沒(méi)有前驅(qū)，則可任選一個(gè)。假設(shè)先輸出v6, 在刪除v6及弧<v6，v4>，<v6，v5>之后，只有頂點(diǎn)v1沒(méi)有前驅(qū)，則輸出vl且刪去vl及弧<v1，v2>、<v1，v3>和<v1, v4>，之后v3和v4都沒(méi)有前驅(qū)。依次類推，可從中任選一個(gè)繼續(xù)進(jìn)行。最后得到該有向圖的拓?fù)溆行蛐蛄袨椋?br />
v6 - v1 - v4 - v3 - v2 - v5
圖AOV-網(wǎng)及其拓?fù)溆行蛐蛄挟a(chǎn)生的過(guò)程
(a)AOV-網(wǎng)；(b)輸出v6之后；(c)輸出v1之后；(d)輸出v4之后；(e)輸出v3之后；(f)輸出v2之后
為了實(shí)現(xiàn)上述算法，對(duì)AOV 網(wǎng)采用鄰接表存儲(chǔ)方式，并且鄰接表中頂點(diǎn)結(jié)點(diǎn)中增加一個(gè)記錄頂點(diǎn)入度的數(shù)據(jù)域，即頂點(diǎn)結(jié)構(gòu)設(shè)為：
頂點(diǎn)表結(jié)點(diǎn)結(jié)構(gòu)的描述改為：
typedef struct vnode{ /*頂點(diǎn)表結(jié)點(diǎn)*/
int count /*存放頂點(diǎn)入度*/
VertexType vertex; /*頂點(diǎn)域*/
EdgeNode * firstedge; /*邊表頭指針*/
}VertexNode;
當(dāng)然也可以不增設(shè)入度域，而另外設(shè)一個(gè)一維數(shù)組來(lái)存放每一個(gè)結(jié)點(diǎn)的入度。算法中可設(shè)置了一個(gè)堆棧，凡是網(wǎng)中入度為0 的頂點(diǎn)都將其入棧。為此，拓?fù)渑判虻乃惴ú襟E為：
1、將沒(méi)有前驅(qū)的頂點(diǎn)（count 域?yàn)?）壓入棧；
2、從棧中退出棧頂元素輸出，并把該頂點(diǎn)引出的所有有向邊刪去，即把它的各個(gè)鄰接頂點(diǎn)的入度減1；
3、將新的入度為0 的頂點(diǎn)再入堆棧；
4、重復(fù)②～④，直到棧為空為止。此時(shí)或者是已經(jīng)輸出全部頂點(diǎn)，或者剩下的頂點(diǎn)中沒(méi)有入度為0 的頂點(diǎn)。
為了避免重復(fù)檢測(cè)入度為零的頂點(diǎn)，可另設(shè)一棧暫存所有入度為零的頂點(diǎn)。
Status Topological Sort(ALGraph G){
//有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。
//若G無(wú)回路，則輸出G的頂點(diǎn)的1個(gè)拓?fù)湫蛄胁⒎祷豋K，否則ERROR。
FindInDegree(G，indegree)； //對(duì)各頂點(diǎn)求入度indegree[0..vernum-1]
InitStack(S)；
for(i=0；i<G.vexnum； ++i)
if(!indegree[i])Push(S，i) //建零入度頂點(diǎn)棧,s入度為0者進(jìn)棧
count=0； //對(duì)輸出頂點(diǎn)計(jì)數(shù)
while (!StackEmpty(S)) {
Pop(S，i)；
printf(i，G.vertices[i].data)； ++count； //輸出i號(hào)頂點(diǎn)并計(jì)數(shù)
for(p=G.vertices[i].firstarc；p； p=p—>nextarc) {
k=p—>adivex； //對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減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)中有些活動(dòng)可以并行地進(jìn)行，所以完成工程的最短時(shí)間是從開(kāi)始點(diǎn)到完成點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度，路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑(Critical Path)。
3.1AOE網(wǎng)：（Activity on edge network）
AOE網(wǎng)示意圖若在帶權(quán)的有向圖中，以頂點(diǎn)表示事件，以有向邊表示活動(dòng)，邊上的權(quán)值表示活動(dòng)的開(kāi)銷（如該活動(dòng)持續(xù)的時(shí)間），則此帶權(quán)的有向圖稱為AOE網(wǎng)。
3.2 實(shí)際問(wèn)題：
如果用AOE網(wǎng)來(lái)表示一項(xiàng)工程，那么，僅僅考慮各個(gè)子工程之間的優(yōu)先關(guān)系還不夠，更多的是關(guān)心整個(gè)工程完成的最短時(shí)間是多少；哪些活動(dòng)的延期將會(huì)影響整個(gè)工程的進(jìn)度，而加速這些活動(dòng)是否會(huì)提高整個(gè)工程的效率。因此，通常在AOE網(wǎng)中列出完成預(yù)定工程計(jì)劃所需要進(jìn)行的活動(dòng)，每個(gè)活動(dòng)計(jì)劃完成的時(shí)間，要發(fā)生哪些事件以及這些事件與活動(dòng)之間的關(guān)系，從而可以確定該項(xiàng)工程是否可行，估算工程完成的時(shí)間以及確定哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵。
如圖是一個(gè)假想的有11項(xiàng)活動(dòng)的AOE-網(wǎng)：
其中有9個(gè)事件v1，v2，v3，…，v9，每個(gè)事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)可以開(kāi)始。如v1表示整個(gè)工程開(kāi)始，v9表示整個(gè)工程結(jié)束，v5表示a4和a5已經(jīng)完成，a7和a8可以開(kāi)始。與每個(gè)活動(dòng)相聯(lián)系的數(shù)是執(zhí)行該活動(dòng)所需的時(shí)間。比如，活動(dòng)a1需要6天，a2需要4天等。
和AOV-網(wǎng)不同，對(duì)AOE-網(wǎng)有待研究的問(wèn)題是：
(1)完成整項(xiàng)工程至少需要多少時(shí)間?
(2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵?
3.3 關(guān)鍵路徑
由于在AOE-網(wǎng)中有些活動(dòng)可以并行地進(jìn)行，所以完成工程的最短時(shí)間是從開(kāi)始點(diǎn)到完成點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度(這里所說(shuō)的路徑長(zhǎng)度是指路徑上各活動(dòng)持續(xù)時(shí)間之和，不是路徑上弧的數(shù)目)。路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑(Critical Path)。
AOE網(wǎng)有關(guān)的概念：
1)路徑長(zhǎng)度：路徑上各個(gè)活動(dòng)的持續(xù)時(shí)間之和
2)完成工程的最短時(shí)間：由于AOE網(wǎng)中有活動(dòng)是并行進(jìn)行的，所以完成工程的最短時(shí)間就是從開(kāi)始點(diǎn)到完成點(diǎn)的最長(zhǎng)路勁長(zhǎng)度。
3)活動(dòng)最早開(kāi)始時(shí)間(earlist time)(e(i))：從開(kāi)始點(diǎn)到頂點(diǎn)vi的最長(zhǎng)路徑稱為事件vi的最早發(fā)生時(shí)間。這個(gè)時(shí)間決定了以vi為尾的弧表示的活動(dòng)的最早開(kāi)始時(shí)間.
4)活動(dòng)最晚開(kāi)始時(shí)間(latest time)(l(i))：在不推遲整個(gè)工程完成的前提下，活動(dòng)最遲開(kāi)始的時(shí)間
5)完成活動(dòng)的時(shí)間余量：該活動(dòng)的最遲開(kāi)始時(shí)間減去最早開(kāi)始時(shí)間
6)關(guān)鍵路徑(critical path)：路徑長(zhǎng)度最長(zhǎng)的路徑稱為關(guān)鍵路徑
7)關(guān)鍵活動(dòng)(critical activity):關(guān)鍵路徑上的活動(dòng)稱為關(guān)鍵活動(dòng)，關(guān)鍵活動(dòng)的特點(diǎn)是:e(i)=l(i)分析關(guān)鍵路徑的目的就是辨別在整個(gè)工程中哪些是關(guān)鍵活動(dòng)，以便爭(zhēng)取提高關(guān)鍵活動(dòng)的工作效率，縮短整個(gè)工程的工期。
3.4 解決方案：
由上分析可知，辨別關(guān)鍵活動(dòng)就是要找e(i)=l(i)的活動(dòng)。為了求得AOE-網(wǎng)中活動(dòng)的e(i)和l(i)， 首先求事件的最早發(fā)生時(shí)間ve(j)和最遲發(fā)生時(shí)間vl(j)。如果活動(dòng)ai由弧<j,k>表示，其持續(xù)時(shí)間記為dut(<j,k>),則有如下關(guān)系：
e(i ) = ve(j)
l(i) = vl(k)-dut(<j,k>)
求ve(j)和vl(j)需分兩步進(jìn)行：
（1）從ve(0)開(kāi)始向前遞推
其中，T是所有以第j個(gè)頂點(diǎn)為頭的弧的結(jié)合。
（2）從vl(n-1)=ve(n-1)起向后遞推
其中，S是所有以第i個(gè)頂點(diǎn)為尾的弧的集合。
這兩個(gè)遞推公式的計(jì)算必須分別在拓?fù)溆行蚝湍嫱負(fù)溆行虻那疤嵯逻M(jìn)行。也就是說(shuō)ve(j-1)必須在vj的所有前驅(qū)的最早發(fā)生時(shí)間求得之后才能確定，而vl(j-1)則必須在vj的所有后繼的最遲發(fā)生時(shí)間求得之后才能確定。因此，可以在拓?fù)渑判虻幕A(chǔ)上計(jì)算ve(j-1)和vl(j-1)。
3.5 關(guān)鍵路徑的算法：
(1)輸入e條弧<j，k>，建立AOE-網(wǎng)的存儲(chǔ)結(jié)構(gòu)；
(2)從源點(diǎn)v0出發(fā)，令ve[0]=0，按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時(shí)間ve[i] (1≤i≤n-1)。如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n，則說(shuō)明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行步驟(3)。
(3)從匯點(diǎn)vn出發(fā)，令vl[n-1]=ve[n-1]，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間vl[i](n-2≥i≥0)；
(4)根據(jù)各頂點(diǎn)的ve和vl值，求每條弧s的最早開(kāi)始時(shí)間e(s)和最遲開(kāi)始時(shí)間 l(s)。若某條弧滿足條件e(s)=l(s)，則為關(guān)鍵活動(dòng)。
先將拓?fù)渑判蛩惴ǎ篢opologicalOrder（）
CriticalPath便為求關(guān)鍵路徑的算法：
Status TopologicalOrder(ALGraph G，Stack &T){
//有向網(wǎng)G采用鄰接表存儲(chǔ)結(jié)構(gòu)，求各頂點(diǎn)事件的最早發(fā)生時(shí)間ve(全局變量)。
//T為拓?fù)湫蛄许旤c(diǎn)棧，s為零入度頂點(diǎn)棧。若G無(wú)回路，返回G的一拓?fù)湫蛄校瘮?shù)值為OK，否則ERROR。
FindInDegree(G，indegree)；//對(duì)各頂點(diǎn)求入度indegree[0..vernum-1]
for(i=0；i<G.vexnum； ++i)
if(!indegree[i])Push(S，i) //建零入度頂點(diǎn)棧,s入度為0者進(jìn)棧
InitStack(T)； count=0；ve[0..G.vexnum-1]=0； //初始化
while(!StackEmpty(S)){ //j號(hào)頂點(diǎn)入T棧并計(jì)數(shù)
Pop(S，j)； Push(T，j)；++count;
for(p=G.vertices[j].firstarc；p；p=p->nextarc){
k=p—>adjvex； //對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減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的各項(xiàng)關(guān)鍵活動(dòng)。
if(!TopologicalOrder(G，T)) return ERROR； //初始化頂點(diǎn)事件的最遲發(fā)生時(shí)間
vl[0..G.vexnum-1]=ve[0..C.vexnum-1]； //按拓?fù)淠嫘蚯蟾黜旤c(diǎn)的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)鍵活動(dòng)
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)鍵活動(dòng)
}
}//CriticalPath
圖(a)所示網(wǎng)的關(guān)鍵路徑：可見(jiàn)a2、a5和a7為關(guān)鍵活動(dòng)，組成一條從源點(diǎn)到匯點(diǎn)的關(guān)鍵路徑，如圖(b)所示。
圖(a)所示網(wǎng)的計(jì)算結(jié)果:
4. 最短路徑：最短路徑問(wèn)題是圖研究中的一個(gè)經(jīng)典算法問(wèn)題， 旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。
最短路徑問(wèn)題是圖的又一個(gè)比較典型的應(yīng)用問(wèn)題。例如，某一地區(qū)的一個(gè)公路網(wǎng)，給定了該網(wǎng)內(nèi)的n 個(gè)城市以及這些城市之間的相通公路的距離，能否找到城市A 到城市B 之間一條舉例最近的通路呢？
如果將城市用點(diǎn)表示，城市間的公路用邊表示，公路的長(zhǎng)度作為邊的權(quán)值，那么，這個(gè)問(wèn)題就可歸結(jié)為在網(wǎng)圖中，求點(diǎn)A 到點(diǎn)B 的所有路徑中，邊的權(quán)值之和最短的那一條路徑。這條路徑就是兩點(diǎn)之間的最短路徑，并稱路徑上的第一個(gè)頂點(diǎn)為源點(diǎn)（Sourse），最后一個(gè)頂點(diǎn)為終點(diǎn)（Destination）。
單源點(diǎn)的最短路徑問(wèn)題：給定帶權(quán)有向圖G＝（V，E）和源點(diǎn)v∈V，求從v 到G 中其余各頂點(diǎn)的最短路徑。在下面的討論中假設(shè)源點(diǎn)為v0。
解決問(wèn)題的迪杰斯特拉算法：
即由迪杰斯特拉（Dijkstra）提出的一個(gè)按路徑長(zhǎng)度遞增的次序產(chǎn)生最短路徑的算法。首先求出長(zhǎng)度最短的一條最短路徑，然后參照它求出長(zhǎng)度次短的一條最短路徑，依次類推，直到從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑全部求出為止。
算法的基本思想是：
設(shè)置兩個(gè)頂點(diǎn)的集合S 和T＝V－S，集合S 中存放已找到最短路徑的頂點(diǎn)，集合T 存放當(dāng)前還未找到最短路徑的頂點(diǎn)。
初始狀態(tài)時(shí)，集合S 中只包含源點(diǎn)v0，然后不斷從集合T 中選取到頂點(diǎn)v0 路徑長(zhǎng)度最短的頂點(diǎn)u 加入到集合S 中，集合S 每加入一個(gè)新的頂點(diǎn)u，都要修改頂點(diǎn)v0 到集合T 中剩余頂點(diǎn)的最短路徑長(zhǎng)度值，集合T 中各頂點(diǎn)新的最短路徑長(zhǎng)度值為原來(lái)的最短路徑長(zhǎng)度值與頂點(diǎn)u 的最短路徑長(zhǎng)度值加上u 到該頂點(diǎn)的路徑長(zhǎng)度值中的較小值。此過(guò)程不斷重復(fù)，直到集合T 的頂點(diǎn)全部加入到S 中為止。
Dijkstra 算法的實(shí)現(xiàn):
首先，引進(jìn)一個(gè)輔助向量D，它的每個(gè)分量D[i] 表示當(dāng)前所找到的從始點(diǎn)v 到每個(gè)終點(diǎn)vi 的最短路徑的長(zhǎng)度。它的初態(tài)為：若從v 到vi 有弧，則D[i]為弧上的權(quán)值；否則置D[i]為∞。顯然，長(zhǎng)度為：
D[j]=Min{D[i]| vi∈V}
的路徑就是從v 出發(fā)的長(zhǎng)度最短的一條最短路徑。此路徑為（v ,vj）。
那么，下一條長(zhǎng)度次短的最短是哪一條呢？假設(shè)該次短路徑的終點(diǎn)是vk ，則可想而知，這條路徑或者是（v, vk），或者是（v, vj, vk）。它的長(zhǎng)度或者是從v 到vk 的弧上的權(quán)值，或者是D[j]和從vj 到vk 的弧上的權(quán)值之和。
依據(jù)前面介紹的算法思想，在一般情況下，下一條長(zhǎng)度次短的最短路徑的長(zhǎng)度必是：
D[j]=Min{D[i]| vi∈V-S}
其中，D[i] 或者弧（v, vi）上的權(quán)值，或者是D[k]( vk∈S 和弧（vk, vi）上的權(quán)值之和。
根據(jù)以上分析，可以得到如下描述的算法：
（1）假設(shè)用帶權(quán)的鄰接矩陣edges 來(lái)表示帶權(quán)有向圖，edges[i][j] 表示弧〈vi, vj〉上的權(quán)值。若〈vi, vj〉不存在，則置edges[i][j]為∞（在計(jì)算機(jī)上可用允許的最大值代替）。S 為已找到從v 出發(fā)的最短路徑的終點(diǎn)的集合，它的初始狀態(tài)為空集。那么，從v 出發(fā)到圖上其余各頂點(diǎn)（終點(diǎn)）vi 可能達(dá)到最短路徑長(zhǎng)度的初值為：
D[i]= edges[Locate Vex(G,v)][i] vi∈V
（2）選擇vj，使得
D[j]=Min{D[i]| vi∈V-S}
vj 就是當(dāng)前求得的一條從v 出發(fā)的最短路徑的終點(diǎn)。令
S＝S∪{j}
（3）修改從v 出發(fā)到集合V-S 上任一頂點(diǎn)vk 可達(dá)的最短路徑長(zhǎng)度。如果
D[j]+ edges[j][k]<D[k]
則修改D[k]為
D[k]=D[j]+ edges[j][k]
重復(fù)操作（2）、（3）共n-1 次。由此求得從v 到圖上其余各頂點(diǎn)的最短路徑是依路徑長(zhǎng)度遞增的序列。
如圖8.26 所示一個(gè)有向網(wǎng)圖G8 的帶權(quán)鄰接矩陣為：
有向網(wǎng)圖G8 的帶權(quán)鄰接矩陣
用C 語(yǔ)言描述的Dijkstra 算法：
void ShortestPath_DIJ(MGraph G，int v0，PathMatrix &P，ShortPathTable &D){
//用Dijkstra算法求有向網(wǎng)G的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑P[v]及其帶權(quán)長(zhǎng)度D[v]。
//若P[v][w]為TRUE，則w是從v0到v當(dāng)前求得最短路徑上的頂點(diǎn)。
//final[v]為TRUE當(dāng)且僅當(dāng)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；//設(shè)空路徑
if (D[v]<INFINITY) { P[v][v0]=TRUE； P[v][v]=TRUE；}
}//for
D[v0] = 0； final[v0] = TRUE； //初始化，v0頂點(diǎn)屬于S集
//開(kāi)始主循環(huán)，每次求得v0到某個(gè)v頂點(diǎn)的最短路徑，并加v到s集。
for(i=1; i<G.vexnum；++i){ //其余G.vexnum-1個(gè)頂點(diǎn)
min = INFINITY； //當(dāng)前所知離v0頂點(diǎn)的最近距離
for(w=0；w<G.vexnum；++w)
if(!final[w]) //w頂點(diǎn)在V-S中
if(D[w]<min){v=w；min=D[w]；} //w頂點(diǎn)離v0頂點(diǎn)更近
final[v]=TRUE； //離v0頂點(diǎn)最近的v加入S集
for(w=0；w<G.vexnum；++w) //更新當(dāng)前最短路徑及距離
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
以上就是圖的應(yīng)用全部詳細(xì)介紹，希望對(duì)大家的學(xué)習(xí)有所幫助。
- python最小生成樹(shù)kruskal與prim算法詳解
- C++使用Kruskal和Prim算法實(shí)現(xiàn)最小生成樹(shù)
- JS使用Prim算法和Kruskal算法實(shí)現(xiàn)最小生成樹(shù)
- C語(yǔ)言實(shí)現(xiàn)最小生成樹(shù)構(gòu)造算法
- Prim(普里姆)算法求最小生成樹(shù)的思想及C語(yǔ)言實(shí)例講解
- 使用C語(yǔ)言實(shí)現(xiàn)最小生成樹(shù)求解的簡(jiǎn)單方法
- 最小生成樹(shù)算法之Prim算法
- 最小生成樹(shù)算法C語(yǔ)言代碼實(shí)例
- 淺談算法之最小生成樹(shù)Kruskal的Python實(shí)現(xiàn)
相關(guān)文章
解決C語(yǔ)言數(shù)組元素循環(huán)右移的問(wèn)題
今天小編就為大家分享一篇解決C語(yǔ)言數(shù)組元素循環(huán)右移的問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧2018-07-07
C++實(shí)現(xiàn)LeetCode(138.拷貝帶有隨機(jī)指針的鏈表)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(138.拷貝帶有隨機(jī)指針的鏈表),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
以下是對(duì)C語(yǔ)言中typedef的四個(gè)用途進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過(guò)來(lái)參考下2013-08-08
右值引用，一般是在深拷貝的類，實(shí)現(xiàn)移動(dòng)構(gòu)造和移動(dòng)賦值，能夠解決左值引用無(wú)法做到的傳返回值的效率問(wèn)題，下面跟隨小編一起學(xué)習(xí)下C++11語(yǔ)法之右值引用的問(wèn)題2022-04-04
針對(duì)Ruby的Selenium WebDriver安裝指南
這篇文章主要介紹了針對(duì)Ruby的Selenium WebDriver安裝指南,Selenium直接運(yùn)行于瀏覽器之中,是進(jìn)行各種調(diào)試的一大神器,需要的朋友可以參考下2015-07-07
今天小編就為大家分享一篇關(guān)于C++線程安全的單例模式講解，小編覺(jué)得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來(lái)看看吧2019-01-01
基于QT設(shè)計(jì)一個(gè)春聯(lián)自動(dòng)生成器
春節(jié)是中國(guó)最隆重的傳統(tǒng)節(jié)日，一到過(guò)年家家戶戶肯定是要貼春聯(lián)；在春節(jié)前夕，會(huì)用大紅紙張，加上濃墨書(shū)寫(xiě)祝福詞語(yǔ)。本文將利用Qt框架設(shè)計(jì)一個(gè)春聯(lián)自動(dòng)生成器，需要的可以參考一下2022-01-01
C/C++實(shí)現(xiàn)捕獲所有信號(hào)的示例詳解
Linux的信號(hào)機(jī)制大部分情況下用不到,但是由于大部分信號(hào)的默認(rèn)處理是終止進(jìn)程,不正確處理會(huì)惹麻煩,所以我們來(lái)看看如何使用C/C++實(shí)現(xiàn)捕獲所有信號(hào)吧2024-03-03
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)延遲的三個(gè)方法，文中的示例代碼講解詳細(xì)，對(duì)我們深入了解C++有一定的幫助，感興趣的小伙伴可以學(xué)習(xí)一下2022-12-12
這篇文章主要介紹了C++ 前置聲明詳解及實(shí)例的相關(guān)資料,需要的朋友可以參考下2017-06-06