數(shù)據(jù)結(jié)構(gòu)簡明教程（第3版）課件 第7章圖(下)

第7章圖7.1圖的基本概念7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4生成樹和最小生成樹7.5最短路徑7.6拓撲排序7.7AOE網(wǎng)與關鍵路徑第7章圖1/747.4生成樹和最小生成樹在一個無向連通圖G中，如果取它的全部頂點和一部分邊構(gòu)成一個子圖G'，即V(G')=V(G)和E(G')

E(G)。若邊集E(G')中的邊既將圖G中的所有頂點連通又不形成回路，則稱子圖G'是原圖G的一棵生成樹。7.4.1什么是圖的生成樹和最小生成樹7.4生成樹和最小生成樹2/74通過深度優(yōu)先遍歷產(chǎn)生的生成樹稱為深度優(yōu)先生成樹。通過廣度優(yōu)先遍歷產(chǎn)生的生成樹稱為廣度優(yōu)先生成樹。7.4生成樹和最小生成樹可以通過遍歷方式產(chǎn)生一個無向圖的生成樹。3/74連通圖：僅需要從圖中任一頂點出發(fā)，進行深度優(yōu)先遍歷或廣度優(yōu)先遍歷便可以訪問到圖中所有頂點，因此連通圖的一次遍歷所經(jīng)過的邊的集合及圖中所有頂點的集合就構(gòu)成了該圖的一棵生成樹。非連通圖：它由多個連通分量構(gòu)成的，則需要從每個連通分量的任一頂點出發(fā)進行遍歷，每次從一個新起點出發(fā)進行遍歷過程得到的頂點訪問序列恰為各個連通分量中的頂點集。每個連通分量產(chǎn)生的生成樹合起來構(gòu)成整個非連通圖的生成樹。

7.4生成樹和最小生成樹無向圖進行遍歷時：4/74由一個帶權(quán)無向圖可能產(chǎn)生多棵生成樹，把具有權(quán)之和最小的生成樹稱為圖的最小生成樹（MinimumCostSpanningTree，簡稱MCST）。構(gòu)造一個圖的最小生成樹主要有兩個算法，即普里姆算法和克魯斯卡爾算法。7.4生成樹和最小生成樹5/747.4.2普里姆算法普里姆（Prim）算法是一種構(gòu)造性算法。G=(V,E)

T=(U,TE)是G的從頂點v出發(fā)構(gòu)造的最小生成樹，步驟如下：（1）初始化U={v}。以v到其他頂點的所有邊為候選邊；（2）重復以下步驟n-1次，使得其他n-1個頂點被加入到U中：

①從候選邊中挑選權(quán)值最小的邊加入TE，設該邊在V-U中的頂點是k，將k加入U中；

②考察當前V-U中的所有頂點j，修改候選邊：若(k,j)的權(quán)值小于原來和頂點j關聯(lián)的候選邊，則用(k,j)取代后者作為候選邊。7.4生成樹和最小生成樹6/74采用普里姆算法求最小生成樹的過程01243123546870124312354687UV-U7.4生成樹和最小生成樹7/740124312354687UV-U0124312354687UV-U7.4生成樹和最小生成樹8/740124312354687UV-U012431246最小生成樹7.4生成樹和最小生成樹9/74實現(xiàn)普里姆算法（1/3）：建立了兩個輔助數(shù)組closest和lowcost。所有頂點分為U和V-U兩個頂點集。U中的頂點i：lowcost[i]=0；V-U中的頂點j：lowcost[j]>0。iU中i：lowcost[i]=0jV-U中j：lowcost[j]>07.4生成樹和最小生成樹10/74由于是無向圖，U到V-U的邊與V-U到U的邊相同。這里考慮V-U到U的邊。對于V-U中的每個頂點j，記錄它到U中的一條最小邊：closest[j]存儲該邊依附的在U中的頂點編號，lowcost[j]存儲該邊的權(quán)值。kU中k：lowcost[k]=0jV-U中j：lowcost[j]>0vlowcost[j]closest[j]=k實現(xiàn)普里姆算法（2/3）：7.4生成樹和最小生成樹11/74實現(xiàn)普里姆算法（3/3）：U中頂點的增量添加的：一個一個添加U中添加頂點k之前的情況：jvlowcost[j]closest[j]U中添加頂點k之后的情況：對于j：若g.edges[k][j]<lowcost[j]

調(diào)整；否則不變

kjvlowcost[j]closest[j]g.edges[k][j]7.4生成樹和最小生成樹12/74為了方便，假設圖G采用鄰接矩陣g存儲，對應的Prim(g,v)算法如下：voidPrim(MatGraphg,intv) //輸出求得的最小生樹的所有邊{intlowcost[MAXVEX]; //建立數(shù)組lowcost

intclosest[MAXVEX]; //建立數(shù)組closest

intmin,i,j,k;

for(i=0;i<g.n;i++) //給lowcost[]和closest[]置初值

{ lowcost[i]=g.edges[v][i]; closest[i]=v;

}7.4生成樹和最小生成樹13/74for(i=1;i<g.n;i++) //構(gòu)造n-1條邊

{min=INF;k=-1;

for(j=0;j<g.n;j++) //在(V-U)中找出離U最近的頂點k

if(lowcost[j]!=0&&lowcost[j]<min)

{min=lowcost[j];

k=j;

//k為最近頂點的編號

}

printf("邊(%d,%d),權(quán)值為%d\n",closest[k],k,min);

lowcost[k]=0;

//標記k已經(jīng)加入U

for(j=0;j<g.n;j++) //修正數(shù)組lowcost和closest

if(lowcost[j]!=0&&g.edges[k][j]<lowcost[j])

{

lowcost[j]=g.edges[k][j];

closest[j]=k;

}

}}普里姆算法中有兩重for循環(huán)，所以時間復雜度為O(n2)，其中n為圖的頂點個數(shù)。由于與e無關，所以普里姆算法特別適合于稠密圖求最小生成樹。7.4生成樹和最小生成樹14/747.4.3克魯斯卡爾算法克魯斯卡爾（Kruskal）算法是一種按權(quán)值的遞增次序選擇合適的邊來構(gòu)造最小生成樹的方法。G=(V,E)

T=(U,TE)，構(gòu)造最小生成樹T的步驟如下：（1）置U的初值等于V（即包含有G中的全部頂點），TE的初值為空集（即圖T中每一個頂點都構(gòu)成一個連通分量）。（2）將圖G中的邊按權(quán)值從小到大的順序依次選?。喝暨x取的邊未使生成樹T形成回路，則加入TE；否則舍棄，直到TE中包含n-1條邊為止。7.4生成樹和最小生成樹15/74實現(xiàn)克魯斯卡爾算法的關鍵是如何判斷選取的邊是否與生成樹中已保留的邊形成回路？為此設置一個輔助數(shù)組vset[0..n-1]，它用于判定兩個頂點之間是否連通。數(shù)組元素vset[i]（初值為i）代表編號為i的頂點所屬的連通子圖的編號。對于邊（i，j），若vset[i]=vset[j]

不選；否則選取。一旦選取邊（i，j），將兩個連通分量的所有vset值改為vset[i]或者vset[j]。7.4生成樹和最小生成樹16/74首先需要對所有邊按權(quán)值遞增排序，為此定義一個具有如下類型的邊數(shù)組E[]：typedefstruct{intu; //邊的起始頂點intv; //邊的終止頂點

intw; //邊的權(quán)值}Edge; //邊數(shù)組元素類型從圖的鄰接矩陣g中提取出邊數(shù)組E，然后按邊權(quán)值遞增排序。7.4生成樹和最小生成樹17/74構(gòu)造最小生成樹012431235468712346012430123400007.4生成樹和最小生成樹18/74實現(xiàn)克魯斯卡爾算法：假設采用直接插入排序法對邊集E按權(quán)值遞增排序。voidSortEdge(EdgeE[],inte)//直接插入排序：對E數(shù)組按權(quán)值遞增排序{inti,j,k=0;

Edgetemp;

for(i=1;i<e;i++){ temp=E[i]; j=i-1;

//從右向左在有序區(qū)E[0..i-1]中找E[i]的插入位置

while(j>=0&&temp.w<E[j].w)

{E[j+1]=E[j]; //將權(quán)值大于E[i].w的記錄后移

j--; }

E[j+1]=temp; //在j+1處插入E[i]

}}7.4生成樹和最小生成樹19/74voidKruskal(MatGraphg) //輸出求得的最小生樹的所有邊{inti,j,u1,v1,sn1,sn2,k;

intvset[MAXVEX]; //建立數(shù)組vset

EdgeE[MAXE]; //建立存放所有邊的數(shù)組E

k=0;

//k統(tǒng)計E數(shù)組中邊數(shù)

for(i=0;i<g.n;i++) //由圖的鄰接矩陣g產(chǎn)生的邊集數(shù)組E{for(j=0;j<=i;j++) //提取鄰接矩陣中部分元素

{

if(g.edges[i][j]!=0&&g.edges[i][j]!=INF)

{ E[k].u=i;E[k].v=j; E[k].w=g.edges[i][j];

k++; //累加邊數(shù)

}}}

SortEdge(E,k);

//對E數(shù)組按權(quán)值遞增排序

for(i=0;i<g.n;i++)vset[i]=i;

//初始化輔助數(shù)組7.4生成樹和最小生成樹20/74k=1; //k表示當前構(gòu)造生成樹的第幾條邊,初值為1

j=0; //j為E數(shù)組下標,初值為0

while(k<g.n) //生成的邊數(shù)小于n時循環(huán)

{u1=E[j].u;v1=E[j].v; //取一條邊的頭尾頂點

sn1=vset[u1];

sn2=vset[v1]; //分別得到兩頂點所屬的集合編號

if(sn1!=sn2)

//兩頂點屬不同的集合,取該邊{printf("邊(%d,%d),權(quán)值為%d\n",u1,v1,E[j].w);

k++;

//生成的邊數(shù)增1

for(i=0;i<g.n;i++) //兩個集合統(tǒng)一編號

{

if(vset[i]==sn2)//集合編號為sn2的改為sn1

vset[i]=sn1;}

}

j++; //掃描下一條邊

}}7.4生成樹和最小生成樹21/74上述克魯斯卡爾算法不是最優(yōu)算法，在改進后可達到O(elog2e)。一般認為克魯斯卡爾算法的時間復雜度是O(elog2e)。由于僅僅與e有關，所以克魯斯卡爾算法特別適合于稀疏圖求最小生成樹。7.4生成樹和最小生成樹22/747.5最短路徑求從一個頂點到其他各頂點的最短路徑，稱之為單源最短路徑問題；求每對頂點之間的最短路徑，稱之為多源最短路徑問題。7.5最短路徑求帶權(quán)有向圖最短路徑問題分為兩種情況：23/747.5.1單源最短路徑算法求單源最短路徑算法是由狄克斯特拉（Dijkstra）提出的，稱為狄克斯特拉算法。給定一個圖G和一個起始頂點即源點v，求v到其他頂點的最短路徑長度及最短路徑。7.5最短路徑24/74狄克斯特拉算法的具體步驟如下：初始時，頂點集S只包含源點，即S={v}，頂點v到自已的距離為0。頂點集U包含除v外的其他頂點，源點v到U中頂點i的距離為邊上的權(quán)（若v與i有邊<v,i>）或∞（若頂點i不是v的出邊相鄰點）。從U中選取一個頂點u，它是源點v到U中距離最小的一個頂點，然后把頂點u加入S中（該選定的距離就是源點v到頂點u的最短路徑長度）。vjSU=V-Su7.5最短路徑25/74以頂點u為新考慮的中間點，修改源點v到U中各頂點j（j∈U）的距離。重復步驟②和③直到S包含所有的頂點即U為空。vujwujcvucvj兩條路徑中選最小者7.5最短路徑26/74實現(xiàn)狄克斯特拉算法：設置一個數(shù)組dist[0..n-1]，dist[i]用來保存從源點v到頂點i的目前最短路徑長度。path[j]保存源點到頂點j的最短路徑，實際上為最短路徑上的前一個頂點u，即path[j]=u。當求出最短路徑后由path[j]向前推出源點到頂點j的最短路徑。path[j]=uvuj7.5最短路徑27/740132456461685662417Udistpath最小點u012345601234561,2,3,4,5,60466∞∞∞0000-1-1-117.5最短路徑28/740132456461685662417Udistpath最小點u012345601234561,2,3,4,5,60466∞∞∞0000-1-1-112,3,4,5,6045611∞∞00101-1-127.5最短路徑29/740132456461685662417Udistpath最小點u012345601234561,2,3,4,5,60466∞∞∞0000-1-1-112,3,4,5,6045611∞∞00101-1-123,4,5,60456119∞001012-137.5最短路徑30/740132456461685662417Udistpath最小點u012345601234561,2,3,4,5,60466∞∞∞0000-1-1-112,3,4,5,6045611∞∞00101-1-123,4,5,60456119∞001012-134,5,60456119∞001012-157.5最短路徑31/740132456461685662417Udistpath最小點u012345601234561,2,3,4,5,60466∞∞∞0000-1-1-112,3,4,5,6045611∞∞00101-1-123,4,5,60456119∞001012-134,5,60456119∞001012-154,6045610917001052547.5最短路徑32/740132456461685662417Udistpath最小點u012345601234561,2,3,4,5,60466∞∞∞0000-1-1-112,3,4,5,6045611∞∞00101-1-123,4,5,60456119∞001012-134,5,60456119∞001012-154,60456109170010525460456109160010524604561091600105247.5最短路徑33/74最后求出頂點0到1～6各頂點的最短距離分別為4、5、6、10、9和16。path值為{0,0,1,0,5,2,4}。以求頂點0到頂點4的最短路徑為例說明通過path求最短路徑的過程：path[4]=5，path[5]=2，path[2]=1，path[1]=0（源點），則頂點0到頂點4的最短路徑逆為4、5、2、1、0，則正向最短路徑為0→1→2→5→4。7.5最短路徑34/74對應的狄克斯特拉算法如下（v為源點編號）：voidDijkstra(MatGraphg,intv)//求從v到其他頂點的最短路徑{intdist[MAXVEX]; //建立dist數(shù)組

intpath[MAXVEX];

//建立path數(shù)組

intS[MAXVEX];

//建立S數(shù)組

intmindis,i,j,u=0;

for(i=0;i<g.n;i++)

{ dist[i]=g.edges[v][i];//距離初始化

S[i]=0;

//S[]置空

if(g.edges[v][i]<INF)//路徑初始化

path[i]=v;

//v→i有邊時，置i前一頂點為v else

//v→i沒邊時，置i前一頂點為-1

path[i]=-1;

}7.5最短路徑35/74S[v]=1; //源點編號v放入S中

for(i=0;i<g.n-1;i++) //循環(huán)向S中添加n-1個頂點

{mindis=INF; //mindis置最小長度初值

for(j=0;j<g.n;j++) //選取不在S中且有最小距離頂點u{if(S[j]==0&&dist[j]<mindis)

{u=j;

mindis=dist[j];

}}

S[u]=1;

//頂點u加入S中

for(j=0;j<g.n;j++) //修改不在s中的頂點的距離{

if(S[j]==0)

{if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])

{dist[j]=dist[u]+g.edges[u][j];

path[j]=u;

}}}

}}狄克斯特拉算法Dijkstra(g,v)的時間復雜度為O(n2)。7.5最短路徑36/747.5.2多源最短路徑算法求解每對頂點之間的最短路徑的一個辦法是：每次以一個頂點為源點，重復執(zhí)行Dijkstra算法n次，這樣便可以求得每一對頂點之間的最短路徑。解決該問題的另一種方法是弗洛伊德（Floyd）算法。7.5最短路徑37/74假設有向圖G=(V,E)采用鄰接矩陣g表示，另外設置一個二維數(shù)組A用于存放當前頂點之間的最短路徑長度，即分量A[i][j]表示當前頂點i到頂點j的最短路徑長度。弗洛伊德算法的基本思想是遞推產(chǎn)生一個矩陣序列A0、A1、…、Ak、…、An-1，其中Ak[i][j]表示從頂點i到頂點j的路徑上所經(jīng)過的頂點編號不大于k的最短路徑長度。7.5最短路徑38/74歸納起來，弗洛伊德思想可用如下的表達式來描述：A-1[i][j]=g.edges[i][j]Ak[i][j]=MIN{Ak-1[i][j],Ak-1[i][k]+Ak-1[k][j]}0≤k≤n-1ikjAk-1[i][j]兩條路徑中選最小者Ak[i][j]=MIN{

Ak-1[i][j]，

Ak-1[i][k]+Ak-1[k][j]}Ak-1[k][j]Ak-1[i][k]7.5最短路徑39/74另外用二維數(shù)組path保存最短路徑，它與當前迭代的次數(shù)有關，即當?shù)戤?，path[i][j]存放從頂點i到頂點j的最短路徑的前一個頂點的編號。ikjAk-1[i][j]Ak-1[k][j]Ak-1[i][k]abpathk-1[i][j]=b，pathk-1[k][j]=a若Ak-1[i][j]>Ak-1[i][k]+Ak-1[k][j]，選擇經(jīng)過頂點k的路徑，即pathk[i][j]=a=pathk-1[k][j]。否則不改變。7.5最短路徑40/74012353273124A-1path-105∞7-10-10∞042-1-111330222-12∞∞10-1-13-1弗洛伊德算法求多源最短路徑7.5最短路徑41/74012353273124A0path005∞7-10-10∞042-1-111330222-12∞∞10-1-13-1在考慮頂點0時：沒有任何最短路徑得到修改！7.5最短路徑42/74012353273124在考慮頂點1時：0→2：由無路徑改為0→1→2，長度為9，path[0][2]改為1A1path10597-1010∞042-1-111330222-12∞∞10-1-13-17.5最短路徑43/74012353273124在考慮頂點2時：1→0：由無路徑改為1→2→0，長度為7，path[1][0]改為23→0：由無路徑改為3→2→0，長度為4，path[3][0]改為23→1：由無路徑改為3→2→1，長度為4，path[3][1]改為2A2path20597-101070422-111330222-124410223-17.5最短路徑44/74012353273124在考慮頂點3時：0→2：由0→1→2改為0→3→2，長度為8，path[0][2]改為31→0：由1→2→0改為1→3→2→0，長度為6，path[1][0]改為21→2：由1→2改為1→3→2，長度為3，path[1][2]改為3A3path30587-103060322-131330222-124410223-17.5最短路徑45/74在得到A3和path3后，由A3數(shù)組可以直接得到兩個頂點之間的最短路徑長度，如A3[1][0]=6，說明頂點1到0的最短路徑長度為6。path[1][0]=2，說明頂點0的前一頂點是頂點2，path[1][2]=3，表示頂點2的前一個頂點是頂點3，path[1][3]=1，表示頂點3的前一個頂點是頂點1，找到起點。依次得到的頂點序列為0、2、3、1，則頂點1到0的最短路徑為1→3→2→0。A3path30587-103060322-131330222-124410223-17.5最短路徑46/74弗洛伊德算法如下：voidFloyd(MatGraphg) //求每對頂點之間的最短路徑{intA[MAXVEX][MAXVEX]; //建立A數(shù)組

intpath[MAXVEX][MAXVEX]; //建立path數(shù)組

inti,j,k;

for(i=0;i<g.n;i++) //給數(shù)組A和path置初值{for(j=0;j<g.n;j++)

{A[i][j]=g.edges[i][j];

if(i!=j&&g.edges[i][j]<INF)

path[i][j]=i; //i和j頂點之間有一條邊時

else

//i和j頂點之間沒有一條邊時

path[i][j]=-1;

}}7.5最短路徑47/74for(k=0;k<g.n;k++)

//求Ak[i][j]{for(i=0;i<g.n;i++)

{

for(j=0;j<g.n;j++)

{if(A[i][j]>A[i][k]+A[k][j])

//找到更短路徑

{A[i][j]=A[i][k]+A[k][j];//修改路徑長度

path[i][j]=path[k][j];//修改最短路徑

}}

}} 弗洛伊德算法Floyd(g)中有三重循環(huán)，其時間復雜度為O(n3)。ikjAk-1[i][j]Ak-1[k][j]Ak-1[i][k]7.5最短路徑48/74

【例7.13】給定n個村莊之間的交通圖，如下圖所示，若村莊i與村莊j之間有路可通，則將頂點i與頂點j之間用邊連接，邊上的權(quán)值wij表示這條道路的長度。

現(xiàn)打算在這n個村莊中選定一個村莊建一所醫(yī)院。設計一個算法求該醫(yī)院應建在哪個村莊（稱為最佳村莊），能使其他所有村莊到醫(yī)院的路徑總和最短（當有多個這樣的村莊時，求出任一個村莊即可）。4302136412967.5最短路徑49/74先采用Floyd算法求出圖中每對頂點之間的最短路徑長度數(shù)組A。再累加每行的元素之和并放到B數(shù)組中，其中B[i]表示頂點i到其他所有頂點的最短路徑長度之和，最后求出B中最小元素B[minv]，并返回minv。假設村莊圖采用鄰接矩陣g表示。50/740123400129931120610152960410391040643151060求出的A:033143229329434求出的B:最佳村莊編號為2或者37.5最短路徑51/747.6拓撲排序設G=(V,E)是一個具有n個頂點的有向圖，圖中用頂點表示活動，用邊表示活動之間的優(yōu)先關系，這樣的有向圖稱為用頂點表示活動的網(wǎng)，簡稱AOV（ActivityOnvertexNetwork）網(wǎng)。該網(wǎng)中頂點序列v1、v2、…、vn稱為一個拓撲序列，當且僅當該頂點序列滿足下列條件：若<vi,vj>是圖中的邊（即從頂點vi到頂點vj有一條路徑），則在序列中頂點vi必須排在頂點vj之前。在一個有向圖中找一個拓撲序列的過程稱為拓撲排序。7.6拓撲排序52/74例如，計算機專業(yè)的學生必須完成一系列規(guī)定的基礎課和專業(yè)課才能畢業(yè)，假設這些課程的名稱與相應編號如下表所示。課程編號課程名稱先修課程C1高等數(shù)學無C2程序設計無C3離散數(shù)學C1C4數(shù)據(jù)結(jié)構(gòu)C2，C3C5編譯原理C2，C4C6操作系統(tǒng)C4，C7C7計算機組成原理C2C1C3C4C6C5C2C77.6拓撲排序53/74對這個有向圖進行拓撲排序可得到拓撲序列：

C1

C3

C2

C4

C7

C6

C5

C2

C7

C1

C3

C4

C5

C6C1C3C4C6C5C2C7課程學習安排：第1學期第2學期7.6拓撲排序54/74拓撲排序步驟如下：（1）從AOV網(wǎng)中選擇一個沒有前驅(qū)（即入度為0）的頂點并且輸出它。（2）從AOV網(wǎng)中刪去該頂點，并且刪去從該頂點發(fā)出的全部有向邊。（3）重復上述兩步，直到剩余的網(wǎng)中不再存在沒有前驅(qū)的頂點為止。7.6拓撲排序55/74C1C3C4C6C5C2C7拓撲排序過程：拓撲序列：C1C3C2C4C7C6C5拓撲排序完成！7.6拓撲排序56/74對任一有向圖進行拓撲排序有兩種結(jié)果：圖中全部頂點都包含在拓撲序列中，這說明該圖中不存在有向回路；圖中部分頂點未被包含在拓撲序列中，這說明該圖中存在有向回路。所以可以采用拓撲排序判斷一個有向圖中是否存在回路。7.6拓撲排序57/74【例7.14】給出下圖G11的全部可能的拓撲排序序列。

從圖中看到，入度為0有兩個頂點，即0和4。

先考慮頂點0：刪除0及相關邊，入度為0者有4；刪除4及相關邊，入度為0者有1和5；考慮頂點1，刪除1及相關邊，入度為0者有2和5；如此得到拓撲序列：041253，041523，045123。0123457.6拓撲排序58/74

再考察頂點4，類似地得到拓撲序列：450123，401253，405123，401523。因此，所有的拓撲序列為：041253，041523，045123，450123，401253，405123，401523。0123457.6拓撲排序59/74用帶權(quán)有向圖（DAG）描述工程的預計進度，以頂點表示事件，有向邊表示活動，邊e的權(quán)c(e)表示完成活動e所需的時間（比如天數(shù)），或者說活動e持續(xù)時間。圖中入度為0的頂點表示工程的開始事件（如開工儀式），稱為源點；出度為0的頂點表示工程結(jié)束事件，稱為匯點。則稱這樣的有向圖為AOE網(wǎng)（ActivityOnEdge）。7.7AOE網(wǎng)與關鍵路徑7.7AOE網(wǎng)與關鍵路徑60/747

整個工程完成的時間為：從有向圖的源點到匯點的最長路徑，具有最大長度的路徑叫關鍵路徑。abcdefghk6452118244例如:

“關鍵活動”指的是：該邊上的權(quán)值增加將使有向圖上的最長路徑的長度增加。

注意：在一個AOE網(wǎng)中，可以有不止一條的關鍵路徑。源點匯點7.7AOE網(wǎng)與關鍵路徑61/74求關鍵路徑求關鍵活動關鍵路徑是由關鍵活動構(gòu)成的。下面介紹求關鍵活動的步驟。7.7AOE網(wǎng)與關鍵路徑62/74事件的最早開始和最遲開始時間

（1）事件v的最早開始時間：規(guī)定源點事件的最早開始時間為0。定義圖中任一事件v的最早開始時間（earlyevent）

ee(v)等于x、y、z到v所有路徑長度的最大值，即：ee(v)=0

當v為源點時ee(v)=MAX{ee(x)+a，ee(y)+b，ee(z)+c} 否則xyzvabcee(v)=?ee(x)ee(y)ee(z)從左向右推進計算這是為什么源點要唯一！7.7AOE網(wǎng)與關鍵路徑63/74

（2）事件v的最遲開始時間：定義在不影響整個工程進度的前提下，事件v必須發(fā)生的時間稱為v的最遲開始時間（lateevent），記作le(v)。le(v)應等于ee(y)與v到匯點的最長路徑長度之差，即：vxyzabcle(v)=?le(x)le(y)le(z)le(v)=ee(v) 當v為匯點時le(v)=MIN{le(x)-a，le(y)-b，le(z)-c} 否則從右向左推進計算這是為什么匯點要唯一！7.7AOE網(wǎng)與關鍵路徑64/74活動的最早開始時間和最遲開始時間

（3）活動a的最早開始時間e(a)：指該活動起點x事件的最早開始時間，即：

e(a)=ee(x)xy活動a時間為cee(x)le(y)

（4）活動a的最遲開始時間l(a)：指該活動終點y事件的最遲開始時間與該活動所需時間之差，即：

l(a)=le(y)-c7.7AOE網(wǎng)與關鍵路徑65/74

（5）關鍵活動：對于每個活動a，求出d(a)=l(a)-e(a)，若d(a)為0，則稱活動a為關鍵活動。7.7AOE網(wǎng)與關鍵路徑66/74對關鍵活動來說，不存在富余時間。顯然，關鍵路徑上的活動都是關鍵活動。找出關鍵活動的意義在于，可以適當?shù)卦黾訉﹃P鍵活動的投資（人力、物力等），相應地減少對非關鍵活動的投資，從而減少關鍵活動的持續(xù)時間，縮短整個工程的工期。7.7AOE網(wǎng)與關鍵路徑67/74按拓撲序列計算各事件的ee(v)如下：ee(A)=0ee(B)=ee(A)+c(a1)=6ee(C)=ee(A)+c(a2)=4ee(D)=ee(A)+c(a3)=5ee(E)=MAX(ee(B)+c(a4)，ee(C)+c(a5)}=MAX{7，5}=7【例7.15】產(chǎn)生一個拓撲序列：ABCDEFGHI。ABCDFGHEIa1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a10=2a11=4a9=47.7AOE網(wǎng)與關鍵路徑68/74ee(F)=ee(E)+c(a7)=16ee(G)=ee(E)+c(a8)=14ee(H)=ee(D)+c(a6)=7ee(I)=MAX{ee(F)+c(a10)，ee(G)+c(a11)，ee(H)+c(a9)}=MAX(18，18，11}=18ABCDFGHEIa1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a10=2a11=4a9=47.7AOE網(wǎng)與關鍵路徑69/74

按拓撲序列