考研數(shù)據(jù)結(jié)構(gòu)圖的必背算法及知識(shí)點(diǎn)

1、1.最小生成樹(shù)：無(wú)向連通圖的所有生成樹(shù)中有一棵邊的權(quán)值總和最小的生成樹(shù)1.1 問(wèn)題背景：假設(shè)要在n個(gè)城市之間建立通信聯(lián)絡(luò)網(wǎng)，則連通n個(gè)城市只需要n1條線路。這時(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)可以建立許多

2、不同的生成樹(shù)，每一棵生成樹(shù)都可以是一個(gè)通信網(wǎng)。即無(wú)向連通圖的生成樹(shù)不是唯一的。連通圖的一次遍歷所經(jīng)過(guò)的邊的集合及圖中所有頂點(diǎn)的集合就構(gòu)成了該圖的一棵生成樹(shù)，對(duì)連通圖的不同遍歷，就可能得到不同的生成樹(shù)。圖 G5無(wú)向連通圖的生成樹(shù) 為(a)、(b)和(c)圖所示：G5G5的三棵生成樹(shù)：可以證明，對(duì)于有n 個(gè)頂點(diǎn)的無(wú)向連通圖，無(wú)論其生成樹(shù)的形態(tài)如何，所有生成樹(shù)中都有且僅有n1 條邊。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的

3、一個(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(N2)假設(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 的初值為Uu1（假設(shè)構(gòu)造最小生成樹(shù)時(shí)，從頂點(diǎn)u1

4、 出發(fā)），集合T 的初值為T。Prim 算法的思想是：從所有uU，vVU 的邊中，選取具有最小權(quán)值的邊（u，v）E，將頂點(diǎn)v 加入集合U 中，將邊（u，v）加入集合T 中，如此不斷重復(fù)，直到UV 時(shí)，最小生成樹(shù)構(gòu)造完畢，這時(shí)集合T 中包含了最小生成樹(shù)的所有邊。Prim 算法可用下述過(guò)程描述，其中用wuv 表示頂點(diǎn)u 與頂點(diǎn)v 邊上的權(quán)值。（1）Uu1,T=;（2）while (UV)do(u，v)minwuv；uU，vVU TT(u，v)UUv（3）結(jié)束。按照Prim 方法，從頂點(diǎn)1 出發(fā)，該網(wǎng)的最小生成樹(shù)的產(chǎn)生過(guò)程如圖：為實(shí)現(xiàn)Prim 算法，需設(shè)置兩個(gè)輔助closedge，用來(lái)保存U到集合V

5、U 的各個(gè)頂點(diǎn)中具有最小權(quán)值的邊的權(quán)值。對(duì)每個(gè)Vi（V-U ）在輔助數(shù)組中存在一個(gè)相應(yīng)的分量closedgei-1,它包括兩個(gè)域：typedef struct ArcNodeint adjvex; /adjex域存儲(chǔ)該邊依附的在U中的頂點(diǎn)VrType lowcost; /lowcost域存儲(chǔ)該邊上的權(quán)重closedgeMAX_VERTEX_NUM;顯然：初始狀態(tài)時(shí)，Uv1(u1 為出發(fā)的頂點(diǎn)),則到V-U 中各項(xiàng)中最小的邊，即依附頂點(diǎn)v1的各條邊中，找到一條代價(jià)最小的邊（u0，v0）= （1，3）為生成樹(shù)上一條邊。同時(shí)將v0（=v3）并入集合U中。然后修改輔助數(shù)組的值。1）將closedge2

6、.lowcost = 0；/表示頂點(diǎn)V3三已經(jīng)并入U(xiǎn)2) 由于邊（v2,v3）的權(quán)值小于closedge1.lowcost，故需修改closedge1為邊（v2,v3）及其權(quán)值，同理修改closedge4，closedge5.closedge1.adjvex = 3.closedge1.lowcost = 5.closedge4.adjvex = 1.closedge4.lowcost = 5.closedge5.adjvex = 3.closedge5.lowcost = 6.以此類推，直至U = V;下圖給出了在用上述算法構(gòu)造網(wǎng)圖7.16的最小生成樹(shù)的過(guò)程中：Prim 算法實(shí)現(xiàn)：按照算法框

7、架:（1）Uu1,T=;（2）while (UV)do(u，v)minwuv；uU，vVU TT(u，v)UUv（3）結(jié)束。當(dāng)無(wú)向網(wǎng)采用二維數(shù)組存儲(chǔ)的鄰接矩陣存儲(chǔ)時(shí)，Prim 算法的C 語(yǔ)言實(shí)現(xiàn)為：?1234567891011121314151617181920/記錄從頂點(diǎn)集U到VU的代價(jià)最小的邊的輔助數(shù)組定義：  / struct  / VertexType adjvex；  / VRType lowcost；  / closedge MAX_VERTEX_NUM void MiniSpanTree_PRIM (MGraph G，VertexType

8、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) closedgej =u ,G.arcskj.adj; / adjvex , lowcost  closedgek.lowcost =0； /初始，U=u  for( i=1；i<G.vexnum；+i) /選擇其余G.vexnum-1個(gè)頂點(diǎn)   k=minimum(closedge)；   p

9、rintf(closedgek.adjvex, G.vexsk);/輸出生成樹(shù)的邊   /第k頂點(diǎn)并入U(xiǎn)集   closedgek.lowcost=0;   for(j=0; j<G.vexnum; +j)    if (G.acrskj.adj<closedgej.lowcost) closedgej=G.vexsk,G.arcskj.adj;  /for /MiniSpanTree 假設(shè)網(wǎng)中有n個(gè)頂點(diǎn)，則第一個(gè)進(jìn)行初始化的循環(huán)語(yǔ)句的頻度為n，第二個(gè)循環(huán)語(yǔ)句的頻度為n-1。其中有兩

10、個(gè)內(nèi)循環(huán)：其一是在closedgev.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ù)的方法?；舅枷胧牵?) 設(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) 在

11、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ù)，有n1 條邊，故反復(fù)上述過(guò)程，直到選取了n1 條邊為止，就構(gòu)成了一棵最小生成樹(shù)。Kruskal 算法的實(shí)現(xiàn)：算法的框架：構(gòu)造非連通圖T（V，）k = i= 0；/k

12、為邊數(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è)定。?123456789101112131415161718192021222324252627282930313233typedef int elemtype; typedef struct elemtype v1; elemtype v2

13、; int cost; EdgeType; void Kruskal（EdgeType edges ，int n） /*用Kruskal 方法構(gòu)造有n 個(gè)頂點(diǎn)的圖edges 的最小生成樹(shù)*/ int fatherMAXEDGE; int i,j,vf1,vf2; for (i=0;i<n;i+) fatheri=-1; i=0;j=0; while(i<MAXEDGE && j<n-1) vf1=Find(father,edgesi.v1); vf2=Find(father,edgesi.v2); if (vf1!=vf2) fathervf2=vf1; j+

14、; printf(“%3d%3dn”,edgesi.v1,edgesi.v2); i+;   /find 函數(shù) int Find（int father ，int v） /*尋找頂點(diǎn)v 所在樹(shù)的根結(jié)點(diǎn)*/ int t; t=v; while(fathert>=0) t=fathert; return(t); 2. AOV網(wǎng)與拓?fù)渑判颍河善蚨x得到拓?fù)溆行虻牟僮鞅闶峭負(fù)渑判?。建立模型是AOV網(wǎng)2. 1AOV網(wǎng)(Activity on vertex network)所有的工程或者某種流程可以分為若干個(gè)小的工程或階段，這些小的工程或階段就稱為活動(dòng)。若以圖中的頂點(diǎn)來(lái)表示活動(dòng)，

15、有向邊（?。┍硎净顒?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)

16、系圖：該圖的拓?fù)溆行蛳盗校鹤⒁猓涸贏OV-網(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ù)渑判螂x散數(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ì)

17、每個(gè)a、bA 必有aRb 或bRa ，則R 是A上的全序關(guān)系。集合A 與關(guān)系R 一起稱為一個(gè)全序集合。直觀地看，偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。例如，圖7.25所示的兩個(gè)有向圖，圖中弧(x,y)表示xy，則(a)表示偏序，(b)表示全序。若在(a)的有向圖上人為地加一個(gè)表示v2v3的弧(符號(hào)“”表示v2領(lǐng)先于v3)，則(a)表示的亦為全序，且這個(gè)全序稱為拓?fù)溆行?Topological Order)，而由偏序定義得到拓?fù)溆行虻牟僮鞅闶峭負(fù)渑判颉?.3 拓?fù)渑判蛩惴▽?duì)AOV 網(wǎng)進(jìn)行拓?fù)渑判虻姆椒ê筒襟E是：1、從AOV 網(wǎng)中選擇一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)（該頂點(diǎn)的入

18、度為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都

19、沒(méi)有前驅(qū)。依次類推，可從中任選一個(gè)繼續(xù)進(jìn)行。最后得到該有向圖的拓?fù)溆行蛐蛄袨椋簐6 - 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

20、 * 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)。?1234567891011121314

21、1516171819Status 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)求入度indegree0.vernum-1  InitStack(S)；  for(i=0；i<G.vexnum； +i)  if(!indegreei)Push(S，i) /建零入度頂點(diǎn)棧,s入度為0者進(jìn)棧  count=0； /對(duì)輸出頂點(diǎn)計(jì)數(shù)  while (!Stack

22、Empty(S)   Pop(S，i)；   printf(i，G.verticesi.data)； +count； /輸出i號(hào)頂點(diǎn)并計(jì)數(shù)   for(p=G.verticesi.firstarc；p； p=p>nextarc)    k=p>adivex； /對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1    if(！(-indegreek)Push(S，k)；/若入度減為0，則入棧   /for  /while  if(count&

23、lt;G.vexnum) return ERROR； /該有向圖有回路  else return OK； /TopologicalSort3. 關(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)工程，那么

24、，僅僅考慮各個(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

25、可以開(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)行的，所以完成工程的最短

26、時(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è)

27、工程中哪些是關(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)起

28、向后遞推其中，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ā)，令ve0=0，按拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最早發(fā)生時(shí)間vei (1in-1)。如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n，則說(shuō)明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終

29、止；否則執(zhí)行步驟(3)。(3)從匯點(diǎn)vn出發(fā)，令vln-1=ven-1，按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時(shí)間vli(n-2i0)；(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)鍵路徑的算法：?1234567891011121314151617181920212223242526272829303132333435363738Status TopologicalOrder(ALGraph G，Stack &T

30、) /有向網(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)求入度indegree0.vernum-1  for(i=0；i<G.vexnum； +i)   if(!indegreei)Push(S，i) /建零入度頂點(diǎn)棧,s入度為0者進(jìn)棧  InitStack(T)； count=0；ve0.G.vexnum-1=0； /初始化  while(

31、!StackEmpty(S) /j號(hào)頂點(diǎn)入T棧并計(jì)數(shù)   Pop(S，j)； Push(T，j)；+count;   for(p=G.verticesj.firstarc；p；p=p->nextarc)    k=p>adjvex； /對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減l    if(-indegreek=0)Push(S，k)； /若入度減為0，則入棧    if(vej+*(p->info)>vek ) vek=vej+*(p->inf

32、o)；      /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)。

33、60;if(!TopologicalOrder(G，T) return ERROR； /初始化頂點(diǎn)事件的最遲發(fā)生時(shí)間  vl0.G.vexnum-1=ve0.C.vexnum-1； /按拓?fù)淠嫘蚯蟾黜旤c(diǎn)的vl值  while(!StackEmpty(T)   for( Pop(T, j), p=G.verticesj.firstarc；p； p=p->nextarc)    k=p->adjvex； dut=*(p>info)； /dut<i，k>    if(vl

34、k-dut<vlj) vlj=vlk-dut； /for  for(j=0；j<G.vexnum；+j) /求ee，el和關(guān)鍵活動(dòng)   for(p=G.verticesj；p；p=p->nextarc)    k=p->adjvex； dut=*(p>info)；ee=vej；el=v1k-dut；tag = (ee=e1) ? *' ： '；    printf(j，k，dut，ee，el，tag)； /輸出關(guān)鍵活動(dòng) /CriticalPath圖(a)所示網(wǎng)

35、的關(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)之間的最

36、短路徑，并稱路徑上的第一個(gè)頂點(diǎn)為源點(diǎn)（Sourse），最后一個(gè)頂點(diǎn)為終點(diǎn)（Destination）。單源點(diǎn)的最短路徑問(wèn)題：給定帶權(quán)有向圖G（V，E）和源點(diǎn)vV，求從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 和TVS，集合S 中存放已找到最短路徑的頂點(diǎn)，集合T 存放當(dāng)前還未找到最短路徑的頂點(diǎn)。初始狀態(tài)

37、時(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è)分量Di 表示當(dāng)前所找到的從始點(diǎn)v 到每個(gè)終點(diǎn)vi 的最短路徑的長(zhǎng)度。它的初態(tài)為：若從v 到vi 有弧，則Di為弧上的權(quán)值；否則置Di為。顯然，長(zhǎng)度為：Dj=MinD

38、i| viV的路徑就是從v 出發(fā)的長(zhǎng)度最短的一條最短路徑。此路徑為（v ,vj）。那么，下一條長(zhǎng)度次短的最短是哪一條呢？假設(shè)該次短路徑的終點(diǎn)是vk ，則可想而知，這條路徑或者是（v, vk），或者是（v, vj, vk）。它的長(zhǎng)度或者是從v 到vk 的弧上的權(quán)值，或者是Dj和從vj 到vk 的弧上的權(quán)值之和。依據(jù)前面介紹的算法思想，在一般情況下，下一條長(zhǎng)度次短的最短路徑的長(zhǎng)度必是：Dj=MinDi| viV-S其中，Di 或者?。╲, vi）上的權(quán)值，或者是Dk( vkS 和?。╲k, vi）上的權(quán)值之和。根據(jù)以上分析，可以得到如下描述的算法：（1）假設(shè)用帶權(quán)的鄰接矩陣edges 來(lái)表示帶權(quán)有向圖，edgesij 表示弧vi, vj上的權(quán)值。若vi, vj不存在，則置edgesij為（在計(jì)算機(jī)上可用允許的最大值代替）。S 為已找到從v 出發(fā)的最短路徑的終點(diǎn)的集合，它的初始狀態(tài)為空集。那么，從v 出發(fā)到圖上其余各頂點(diǎn)（終點(diǎn)）vi 可能達(dá)到最短路徑長(zhǎng)度的初值為：Di= edgesLocate Vex(G,v)i viV（2）選擇vj，使得Dj=MinDi| viV-Svj 就是當(dāng)前求得的一條從v