1.最小生成樹：無(wú)向連通圖的所有生成樹中有一棵邊的權(quán)值總和最小的生成樹
1.1 問題背景：
假設(shè)要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要n—1條線路。這時(shí)，自然會(huì)考慮這樣一個(gè)問題，如何在最節(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ǎng)來(lái)表示n個(gè)城市以及n個(gè)城市間可能設(shè)置的通信線路，其中網(wǎng)的頂點(diǎn)表示城市，邊表示兩城市之間的線路，賦于邊的權(quán)值表示相應(yīng)的代價(jià)。對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個(gè)通信網(wǎng)。即無(wú)向連通圖的生成樹不是唯一的。連通圖的一次遍歷所經(jīng)過的邊的集合及圖中所有頂點(diǎn)的集合就構(gòu)成了該圖的一棵生成樹，對(duì)連通圖的不同遍歷，就可能得到不同的生成樹。
圖 G5無(wú)向連通圖的生成樹 為(a)、(b)和(c)圖所示：
G5
G5的三棵生成樹：
可以證明，對(duì)于有n 個(gè)頂點(diǎn)的無(wú)向連通圖，無(wú)論其生成樹的形態(tài)如何，所有生成樹中都有且僅有n－1 條邊。
1.3最小生成樹的定義：
如果無(wú)向連通圖是一個(gè)網(wǎng)，那么，它的所有生成樹中必有一棵邊的權(quán)值總和最小的生成樹，我們稱這棵生成樹為最小生成樹，簡(jiǎn)稱為最小生成樹。
最小生成樹的性質(zhì)：
假設(shè)N=(V,{ E}) 是個(gè)連通網(wǎng)，U是頂點(diǎn)集合V的一個(gè)非空子集，若（u,v）是個(gè)一條具有最小權(quán)值(代價(jià))的邊，其中，
則必存在一棵包含邊（u,v）的最小生成樹。
1.4 解決方案：
兩種常用的構(gòu)造最小生成樹的算法：普里姆（Prim）和克魯斯卡爾（Kruskal）。他們都利用了最小生成樹的性質(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 的最小生成樹中的頂點(diǎn)，
集合T （邊集合）存放G 的最小生成樹中的邊。
T ，U的初始狀態(tài)：令集合U 的初值為U＝{u1}（假設(shè)構(gòu)造最小生成樹時(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í)，最小生成樹構(gòu)造完畢，這時(shí)集合T 中包含了最小生成樹的所有邊。
Prim 算法可用下述過程描述，其中用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)的最小生成樹的產(chǎn)生過程如圖：
為實(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í)將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的最小生成樹的過程中：
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的最小生成樹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]);//輸出生成樹的邊
- //第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)的最小生成樹。
2.克魯斯卡爾（Kruskal） :由點(diǎn)到線，適合邊稀疏的網(wǎng)。時(shí)間復(fù)雜度：O(e * loge)
Kruskal 算法是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。
基本思想是：
1) 設(shè)無(wú)向連通網(wǎng)為G＝（V，E），令G 的最小生成樹為T，其初態(tài)為T＝（V，{}），即開始時(shí)，最小生成樹T 由圖G 中的n 個(gè)頂點(diǎn)構(gòu)成，頂點(diǎn)之間沒有一條邊，這樣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 的一棵最小生成樹。
按照Kruskal 方法構(gòu)造最小生成樹的過程如圖所示：
在構(gòu)造過程中，按照網(wǎng)中邊的權(quán)值由小到大的順序，不斷選取當(dāng)前未被選取的邊集中權(quán)值最小的邊。依據(jù)生成樹的概念，n 個(gè)結(jié)點(diǎn)的生成樹，有n－1 條邊，故反復(fù)上述過程，直到選取了n－1 條邊為止，就構(gòu)成了一棵最小生成樹。
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)所在樹的根結(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 的最小生成樹*/
- { 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 所在樹的根結(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è)問題可以被看成是一個(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ù)溆行蛐蛄兄?，則該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è)沒有前驅(qū)的頂點(diǎn)（該頂點(diǎn)的入度為0）并且輸出它；
2、從網(wǎng)中刪去該頂點(diǎn)，并且刪去從該頂點(diǎn)發(fā)出的全部有向邊；
3、重復(fù)上述兩步，直到剩余的網(wǎng)中不再存在沒有前驅(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沒有前驅(qū)，則可任選一個(gè)。假設(shè)先輸出v6, 在刪除v6及弧<v6，v4>，<v6，v5>之后，只有頂點(diǎn)v1沒有前驅(qū)，則輸出vl且刪去vl及弧<v1，v2>、<v1，v3>和<v1, v4>，之后v3和v4都沒有前驅(qū)。依次類推，可從中任選一個(gè)繼續(xù)進(jìn)行。最后得到該有向圖的拓?fù)溆行蛐蛄袨椋?br />
v6 - v1 - v4 - v3 - v2 - v5
圖AOV-網(wǎng)及其拓?fù)溆行蛐蛄挟a(chǎn)生的過程
(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、將沒有前驅(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)中沒有入度為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í)間是從開始點(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)的開銷（如該活動(dòng)持續(xù)的時(shí)間），則此帶權(quán)的有向圖稱為AOE網(wǎng)。
3.2 實(shí)際問題：
如果用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)可以開始。如v1表示整個(gè)工程開始，v9表示整個(gè)工程結(jié)束，v5表示a4和a5已經(jīng)完成，a7和a8可以開始。與每個(gè)活動(dòng)相聯(lián)系的數(shù)是執(zhí)行該活動(dòng)所需的時(shí)間。比如，活動(dòng)a1需要6天，a2需要4天等。
和AOV-網(wǎng)不同，對(duì)AOE-網(wǎng)有待研究的問題是：
(1)完成整項(xiàng)工程至少需要多少時(shí)間?
(2)哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵?
3.3 關(guān)鍵路徑
由于在AOE-網(wǎng)中有些活動(dòng)可以并行地進(jìn)行，所以完成工程的最短時(shí)間是從開始點(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í)間就是從開始點(diǎn)到完成點(diǎn)的最長(zhǎng)路勁長(zhǎng)度。
3)活動(dòng)最早開始時(shí)間(earlist time)(e(i))：從開始點(diǎn)到頂點(diǎn)vi的最長(zhǎng)路徑稱為事件vi的最早發(fā)生時(shí)間。這個(gè)時(shí)間決定了以vi為尾的弧表示的活動(dòng)的最早開始時(shí)間.
4)活動(dòng)最晚開始時(shí)間(latest time)(l(i))：在不推遲整個(gè)工程完成的前提下，活動(dòng)最遲開始的時(shí)間
5)完成活動(dòng)的時(shí)間余量：該活動(dòng)的最遲開始時(shí)間減去最早開始時(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)開始向前遞推
其中，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的最早開始時(shí)間e(s)和最遲開始時(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)鍵路徑：可見a2、a5和a7為關(guān)鍵活動(dòng)，組成一條從源點(diǎn)到匯點(diǎn)的關(guān)鍵路徑，如圖(b)所示。
圖(a)所示網(wǎng)的計(jì)算結(jié)果:
4. 最短路徑：最短路徑問題是圖研究中的一個(gè)經(jīng)典算法問題， 旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。
最短路徑問題是圖的又一個(gè)比較典型的應(yīng)用問題。例如，某一地區(qū)的一個(gè)公路網(wǎng)，給定了該網(wǎng)內(nèi)的n 個(gè)城市以及這些城市之間的相通公路的距離，能否找到城市A 到城市B 之間一條舉例最近的通路呢？
如果將城市用點(diǎn)表示，城市間的公路用邊表示，公路的長(zhǎng)度作為邊的權(quán)值，那么，這個(gè)問題就可歸結(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)的最短路徑問題：給定帶權(quán)有向圖G＝（V，E）和源點(diǎn)v∈V，求從v 到G 中其余各頂點(diǎn)的最短路徑。在下面的討論中假設(shè)源點(diǎn)為v0。
解決問題的迪杰斯特拉算法：
即由迪杰斯特拉（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)度值中的較小值。此過程不斷重復(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] 或者?。╲, vi）上的權(quán)值，或者是D[k]( vk∈S 和?。╲k, 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集
- //開始主循環(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í)有所幫助。
