數(shù)據(jù)結(jié)構(gòu)（Java語言實現(xiàn)） 課件 第6章 圖

第6章圖結(jié)構(gòu)Java實據(jù)現(xiàn)數(shù)目錄CONTENTS6.1

圖的定義及相關(guān)概念6.2圖的存儲結(jié)構(gòu)6.3圖的遍歷6.6最短路徑6.4圖的連通性問題6.5有向無環(huán)圖6.7小結(jié)6.1圖的定義及相關(guān)概念6.1.1圖的定義圖由數(shù)據(jù)元素集合與邊的集合構(gòu)成。數(shù)據(jù)元素常稱為頂點（Vertex），頂點集合（V）不能為空，邊（E）表示頂點之間的關(guān)系，用連線表示。圖（G）的形式化定義為：G=(V,E)，其中，V={x|x∈數(shù)據(jù)元素集合}，E={<x,y>|Path(x,y)/\(x∈V,y∈V)}。Path(x,y)表示從x與y的關(guān)系屬性。如果<x,y>∈E，則<x,y>表示從頂點x到頂點y的一條弧（Arc），x稱為弧尾（Tail）或起始點（Initialnode），y稱為弧頭（Head）或終端點（Terminalnode）。6.1圖的定義及相關(guān)概念6.1.1圖的定義如果<x,y>∈E且有<y,x>∈E，則用無序?qū)?x,y)代替有序?qū)?lt;x,y>和<y,x>，表示x與y之間存在一條邊（Edge），將這樣的圖稱為無向圖。6.1圖的定義及相關(guān)概念6.1.1圖的定義對于無向圖，邊數(shù)e的取值范圍為0~n(n-1)/2。將具有n(n-1)/2條邊的無向圖稱為完全圖。對于有向圖，弧度e的取值范圍是0~n(n-1)。將具有n(n-1)條弧的有向圖稱為有向完全圖。具有e<nlogn條弧或邊的圖，稱為稀疏圖（Sparsegraph）。具有e>nlogn條弧或邊的圖，稱為稠密圖（Densegraph）。6.1圖的定義及相關(guān)概念6.1.2圖的相關(guān)概念1.鄰接點在無向圖G=(V,E)中，如果存在邊(vi,vj)∈E，則稱vi和vj互為鄰接點（Adjacent），即vi和vj相互鄰接。邊(vi,vj)依附于頂點vi和vj，或者稱邊(vi,vj)與頂點vi和vj相互關(guān)聯(lián)。2.頂點的度在無向圖中，頂點v的度是指與v相關(guān)聯(lián)的邊的數(shù)目，記作TD(v)。在有向圖中，以頂點v為弧頭的數(shù)目稱為頂點v的入度（InDegree），記作ID(v)。以頂點v為弧尾的數(shù)目稱為v的出度（OutDegree），記作OD(v)。頂點v的度為以v為頂點的入度和出度之和，即TD(v)=ID(v)+OD(v)。6.1圖的定義及相關(guān)概念6.1.2圖的相關(guān)概念3.路徑在圖中，從頂點vi出發(fā)經(jīng)過一系列的頂點序列到達頂點vj稱為從頂點vi到vj的路徑（Path）。路徑的長度是路徑上弧或邊的數(shù)目。4.子圖假設(shè)存在兩個圖G={V,E}和G’={V’,E’}，如果G’的頂點和關(guān)系都是V的子集，即有V’V，E’E，則G’為G的子圖。6.1圖的定義及相關(guān)概念6.1.2圖的相關(guān)概念5.連通圖和強連通圖在無向圖中，如果從頂點vi到頂點vj存在路徑，則稱頂點vi到vj是連通的。推廣到圖的所有頂點，如果圖中的任何兩個頂點之間都是連通的，則稱圖是連通圖（ConnectedGraph）。無向圖中的極大連通子圖稱為連通分量（ConnectedComponent）。6.1圖的定義及相關(guān)概念6.1.2圖的相關(guān)概念6.生成樹一個連通圖（假設(shè)有n個頂點）的生成樹是一個極小連通子圖，它含有圖中的全部頂點，但只有足以構(gòu)成一棵樹的n-1條邊。6.1圖的定義及相關(guān)概念6.1.2圖的相關(guān)概念7.網(wǎng)在實際應(yīng)用中，圖的邊或弧往往與具有一定意義的數(shù)有關(guān)，即每一條邊都有與它相關(guān)的數(shù)，稱為權(quán)，這些權(quán)可以表示從一個頂點到另一個頂點的距離或花費等信息。這種帶權(quán)的圖稱為帶權(quán)圖或網(wǎng)。一個網(wǎng)如圖6.6所示。6.1圖的定義及相關(guān)概念6.1.3圖的抽象數(shù)據(jù)類型7.網(wǎng)在實際應(yīng)用中，圖的邊或弧往往與具有一定意義的數(shù)有關(guān)，即每一條邊都有與它相關(guān)的數(shù)，稱為權(quán)，這些權(quán)可以表示從一個頂點到另一個頂點的距離或花費等信息。這種帶權(quán)的圖稱為帶權(quán)圖或網(wǎng)。一個網(wǎng)如圖6.6所示。ADTGraph{

數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點集。數(shù)據(jù)關(guān)系R：R={VR}VR={<x,y>|x,y∈V且P(x,y>，<x,y>表示從x到y(tǒng)的弧，謂詞P(x,y>定義了弧<x,y>的意義或信息}6.1圖的定義及相關(guān)概念6.1.3圖的抽象數(shù)據(jù)類型基本操作：

（1）CreateGraph(&G)

初始條件：圖G不存在。

操作結(jié)果：創(chuàng)建一個圖G。

（2）DestroyGraph(&T)

初始條件：圖G存在。

操作結(jié)果：銷毀圖G。

（3）LocateVertex(G,v)

初始條件：圖G存在，頂點v合法。

操作結(jié)果：若圖G存在頂點v，則返回頂點v在圖G中的位置。若圖G中沒有頂點v，則函數(shù)返回值為空。

（4）GetVertex(G,i)

初始條件：圖G存在。

操作結(jié)果：返回圖G中序號i對應(yīng)的值。i是圖G某個頂點的序號，返回圖G中序號i對應(yīng)的值。6.1圖的定義及相關(guān)概念6.1.3圖的抽象數(shù)據(jù)類型（5）FirstAdjVertex(G,v)

初始條件：圖G存在，頂點v的值合法。操作結(jié)果：返回圖G中v的第一個鄰接頂點。若v無鄰接頂點或圖G中無頂點v，則函數(shù)返回-1。（6）NextAdjVertex(G,v,w)

初始條件：圖G存在，w是圖G中頂點v的某個鄰接頂點。操作結(jié)果：返回頂點v的下一個鄰接頂點。若w是v的最后一個鄰接頂點，則函數(shù)返回-1。（11）DFSTraverseGraph(G)

初始條件：圖G存在。操作結(jié)果：從圖中的某個頂點出發(fā)，對圖進行深度遍歷。（12）BFSTraverseGraph(G)

初始條件：圖G存在。操作結(jié)果：從圖中的某個頂點出發(fā)，對圖進行廣度遍歷。}ADTGraph6.2圖的存儲結(jié)構(gòu)6.2.1鄰接矩陣表示法圖的鄰接矩陣表示（AdjacencyMatrix）也稱為數(shù)組表示。它采用兩個數(shù)組來表示圖：一個是用于存儲頂點信息的一維數(shù)組，另一個是用于存儲圖中頂點之間的關(guān)聯(lián)關(guān)系的二維數(shù)組，這個關(guān)聯(lián)關(guān)系數(shù)組稱為鄰接矩陣。6.2圖的存儲結(jié)構(gòu)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力兩個圖弧和邊的集合分別為A={<A,B>,<A,C>,<A,D>,<C,A>,<C,B>,<D,A>}和E={(A,B),(A,D),(B,C),(B,D),(C,D)}。它們的鄰接矩陣表示如圖6.7所示。6.2圖的存儲結(jié)構(gòu)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力enumKind{DG,DN,UG,UN}//圖的類型publicclassMGraph{Stringvex[];

//用于存儲頂點

doublearc[][];

//鄰接矩陣，存儲邊或弧的信息

intvexnum,arcnum;//頂點數(shù)#邊（?。┑臄?shù)目

Kindkind;//圖的類型

finalintMAXSIZE=20;}帶權(quán)圖的鄰接矩陣表示如圖6.8所示。MGraph(){vex=newString[MAXSIZE];arc=newdouble[MAXSIZE][MAXSIZE];arcnum=0;vexnum=0;kind=Kind.UG;}6.2圖的存儲結(jié)構(gòu)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力表頭結(jié)點有兩個域組成：數(shù)據(jù)域和指針域。其中，數(shù)據(jù)域用來存放頂點信息，指針域用來指向邊表中的第一個結(jié)點。通常情況下，表頭結(jié)點采用順序存儲結(jié)構(gòu)實現(xiàn)，邊表結(jié)點由三個域組成：鄰接點域、數(shù)據(jù)域和指針域。6.2.2鄰接表表示法6.2圖的存儲結(jié)構(gòu)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力6.2.2鄰接表表示法圖6.1所示的兩個圖G1和G2用鄰接表表示如圖6.11所示。圖6.8所示的帶權(quán)圖用鄰接表表示如圖6.12所示。6.2圖的存儲結(jié)構(gòu)圖的鄰接表存儲結(jié)構(gòu)描述如下：enumGKind{DG,DN,UG,UN}//圖的類型classArcNode//邊結(jié)點的類型定義{intadjvex;//弧指向的頂點的位置

ArcNodenextarc;//指示下一個與該頂點相鄰接的頂點

Stringinfo;//與弧相關(guān)的信息

ArcNode(intadjvex){this.adjvex=adjvex;this.nextarc=null;}}classVNode//頭結(jié)點的類型定義{Stringdata;ArcNodefirstarc;VNode(Stringdata){this.data=data;//用于存儲頂點

this.firstarc=null;

//指向第一個與該頂點鄰接的頂點

}}classAdjGraph//圖的類型定義{finalintMAXSIZE=20;VNodevertex[];intvexnum,arcnum;//圖的頂點數(shù)目、弧的數(shù)目

GKindkind;AdjGraph()

{vertex=newVNode[MAXSIZE];vexnum=0;arcnum=0;kind=GKind.UG;}6.2圖的存儲結(jié)構(gòu)圖6.1所示的有向圖G1的逆鄰接鏈表如圖6.13所示。求某個頂點的入度，需要建立一個有向圖的逆鄰接鏈表，也就是為每個頂點vi建立一個以vi為弧頭的鏈表。6.2圖的存儲結(jié)構(gòu)【例6.2】編寫算法，采用鄰接表創(chuàng)建一個無向圖G。for(k=0;k<arcnum;k++)//建立邊鏈表

{Stringv[]=sc.nextLine().split("");inti=LocateVertex(v[0]);intj=LocateVertex(v[1]);//j為入邊i為出邊創(chuàng)建鄰接表

ArcNodep=newArcNode(j);p.nextarc=vertex[i].firstarc;vertex[i].firstarc=p;//i為入邊j為出邊創(chuàng)建鄰接表

p=newArcNode(i);p.nextarc=vertex[j].firstarc;vertex[j].firstarc=p;}6.2圖的存儲結(jié)構(gòu)6.2.3十字鏈表十字鏈表是有向圖的又一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。在十字鏈表中，將表頭結(jié)點稱為頂點結(jié)點，邊結(jié)點稱為弧結(jié)點。其中，頂點結(jié)點包含三個域：數(shù)據(jù)域和兩個指針域。兩個指針域，一個指向以頂點為弧頭頂點，另一個指向以頂點為弧尾的頂點，數(shù)據(jù)域存放頂點的信息。6.2圖的存儲結(jié)構(gòu)6.2.4鄰接多重表鄰接多重表（AdjacencyMulti_list）表示是無向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。頂點結(jié)點由兩個域構(gòu)成：data域和firstedge域。數(shù)據(jù)域data用于存儲頂點的數(shù)據(jù)信息，firstedga域指示依附于頂點的第一條邊。邊結(jié)點包含六個域：mark域、ivex域、ilink域、jvex域、jlink域和info域。6.2圖的遍歷6.2.1圖的深度優(yōu)先遍歷1.圖的深度遍歷的定義圖的深度優(yōu)先遍歷是樹的先根遍歷的推廣。圖的深度優(yōu)先遍歷的思想是：從圖中某個頂點v0出發(fā)，訪問頂點v0的第一個鄰接點，然后以該鄰接點為新的頂點，訪問該頂點的鄰接點。重復(fù)執(zhí)行以上操作，直到當(dāng)前頂點沒有鄰接點為止。圖的深度優(yōu)先遍歷的序列為：A、B、E、F、C、D、G、H、I。6.3圖的遍歷6.3.1圖的深度優(yōu)先搜索遍歷publicvoidDFSTraverse(intvisited[])

//從第1個頂點起，深度優(yōu)先遍歷圖

{

for(intv=0;v<vexnum;v++)

visited[v]=0;//訪問標(biāo)志數(shù)組初始化為未被訪問

for(intv=0;v<vexnum;v++)

{

if(visited[v]==0)

DFS(v,visited);

//對未訪問的頂點v進行深度優(yōu)先遍歷

}

System.out.println();

}

publicvoidDFS(intv,intvisited[])//從頂點v出發(fā)遞歸深度優(yōu)先遍歷圖{visited[v]=1;//訪問標(biāo)志設(shè)置為已訪問

System.out.print(vertex[v].data+"");//訪問第v個頂點

intw=FirstAdjVertex(vertex[v].data);while(w>=0){if(visited[w]==0)DFS(w,visited);//遞歸調(diào)用DFS對v的尚未訪問的序號為w的鄰接頂點

w=NextAdjVertex(vertex[v].data,vertex[w].data);}}6.3圖的遍歷6.3.2圖的廣度優(yōu)先遍歷1.圖的廣度優(yōu)先遍歷的定義從圖的某個頂點v出發(fā)，首先訪問頂點v，然后按照次序訪問頂點v的未被訪問的每一個鄰接點，接著訪問這些鄰接點的鄰接點，并保證先被訪問的鄰接點的鄰接點先訪問，后被訪問的鄰接點的鄰接點后訪問的原則，依次訪問鄰接點的鄰接點。例如，圖G6的廣度優(yōu)先遍歷的過程如圖6.19所示。其中，箭頭表示廣度遍歷的方向，圖中的數(shù)字表示遍歷的次序。6.3圖的遍歷圖的廣度優(yōu)先搜索遍歷

while(front<rear)//如果隊列不空

{front=(front+1)%MaxSize;v=queue[front];//隊頭元素出隊賦值給vArcNodep=vertex[v].firstarc;while(p!=null)//遍歷序號為v的所有鄰接點

{if(visited[p.adjvex]==0)//如果該頂點未被訪問過

{visited[p.adjvex]=1;System.out.print(vertex[p.adjvex].data+"");rear=(rear+1)%MaxSize;queue[rear]=p.adjvex;}p=p.nextarc;//p指向下一個鄰接點

}6.4圖的連通性問題6.4.1無向圖的連通分量與生成樹圖G3進行深度優(yōu)先搜索遍歷，得到的序列為：A、B、C、D、I、E和F、G、H。6.4圖的連通性問題從某一個頂點出發(fā)，對圖進行廣度優(yōu)先遍歷，得到的生成樹稱為廣度優(yōu)先生成樹。圖6.21所示就是對應(yīng)圖G6的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。對于非連通圖而言，從某一個頂點出發(fā)，對圖進行深度優(yōu)先遍歷或者廣度優(yōu)先遍歷，按照訪問路徑會得到一系列的生成樹，這些生成樹在一起構(gòu)成生成森林。6.4圖的連通性問題最小生成樹就是指在一個連通網(wǎng)的所有生成樹中，其中所有邊的代價之和的那棵生成樹。6.4.2最小生成樹假設(shè)一個連通網(wǎng)N=(V,E)，V是頂點的集合，E是邊的集合，V有一個非空子集U。如果(u,v)是一條具有最小權(quán)值的邊，其中，u∈U、v∈V-U，那么一定存在一個最小生成樹包含邊(u,v)。6.4圖的連通性問題普里姆算法描述如下：假設(shè)N={V,E}是連通網(wǎng)，TE是N的最小生成樹邊的集合。執(zhí)行以下操作：（1）初始時，令U={u0}(u0∈V)、TE=。（2）對于所有的邊u∈U，v∈V-U的邊(u,v)∈E，將一條代價最小的邊(u0,v0)放到集合TE中，同時將頂點v0放進集合U中。（3）重復(fù)執(zhí)行步驟（2），直到U=V為止。這時，邊集合TE一定有n-1條邊，T={V,TE}就是連通網(wǎng)N的最小生成樹。1.普里姆算法6.4圖的連通性問題例如，圖6.23所示就是利用普里姆算法構(gòu)造最小生成樹的過程。6.4圖的連通性問題需要設(shè)置一個數(shù)組closeedge[MaxSize]，用來保存U到V-U最小代價的邊。對于每個頂點v∈V-U，在數(shù)組中存在一個分量closeedge[v]，它包括兩個域adjvex和lowcost，其中，adjvex域用來表示該邊中屬于U中的頂點，lowcost域存儲該邊對應(yīng)的權(quán)值。closeedge[v].lowcost=Min({cost(u,v)|u∈U})6.4圖的連通性問題publicvoidPrim(MGraphM,Stringu,CloseEdgecloseedge[])

//利用Prim算法求從第u個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹

{

intk=M.LocateVertex(u);//k為頂點u對應(yīng)的序號

intm=0;

for(intj=0;j<M.vexnum;j++)//數(shù)組初始化

{

CloseEdgeclose_edge=newCloseEdge(u,M.arc[k][j]);

closeedge[m++]=close_edge;}

closeedge[k].lowcost=0;//初始時集合U只包括頂點u

System.out.println("最小代價生成樹的各條邊為:");

for(inti=1;i<M.vexnum;i++)//選擇剩下的M.vexnum-1個頂點

{k=MiniNum(M,closeedge);//k為與U中頂點相鄰接的下一個頂點的序號

System.out.print("("+closeedge[k].adjvex+"-"+M.vex[k]+")");//輸出邊

closeedge[k].lowcost=0;//第k頂點并入U集

for(intj=0;j<M.vexnum;j++){

if(M.arc[k][j]<closeedge[j].lowcost)//將最小邊存入到列表

{

closeedge[j].adjvex=M.vex[k];

closeedge[j].lowcost=M.arc[k][j];}

}

}

}6.4圖的連通性問題2.克魯斯卡爾算法克魯斯卡爾算法的基本思想是：假設(shè)N={V,E}是連通網(wǎng)，TE是N的最小生成樹邊的集合。執(zhí)行以下操作：（1）初始時，最小生成樹中只有n個頂點，這n個頂點分別屬于不同的集合，而邊的集合TE=。（2）從連通網(wǎng)N中選擇一個代價最小的邊，如果邊所依附的兩個頂點在不同的集合中，將該邊加入到最小生成樹TE中，并將該邊依附的兩個頂點合并到同一個集合中。（3）重復(fù)執(zhí)行步驟（2），直到所有的頂點都屬于同一個頂點集合為止。6.4圖的連通性問題例如，圖6.26所示就是利用卡魯斯卡爾算法構(gòu)造最小生成樹的過程。6.5有向無環(huán)圖1.AOV網(wǎng)在每一個工程過程中，可以將工程分為若干個子工程，這些子工程稱為活動。如果用圖中的頂點表示活動，以有向圖的弧表示活動之間的優(yōu)先關(guān)系，這樣的有向圖稱為AOV網(wǎng)，即頂點表示活動的網(wǎng)。6.5.1AOV網(wǎng)與拓?fù)渑判?.5有向無環(huán)圖對AOV網(wǎng)進行拓?fù)渑判虻姆椒ㄈ缦拢海?）在AOV網(wǎng)中任意選擇一個沒有前驅(qū)的頂點即頂點入度為零，將該頂點輸出。（2）從AOV網(wǎng)中刪除該頂點，以及從該頂點出發(fā)的弧。（3）重復(fù)執(zhí)行步驟（1）和（2），直到AOV網(wǎng)中所有頂點都已經(jīng)被輸出，或者AOV網(wǎng)中不存在無前驅(qū)的頂點為止。按照以上步驟，圖6.26所示的AOV網(wǎng)的拓?fù)湫蛄袨椋?C1,C2,C3,C4,C5,C6,C7,C8,C9,C10)或(C6,C7,C8,C9,C1,C2,C3,C4,C5,C10)拓?fù)渑判?.5有向無環(huán)圖圖6.28所示是AOV網(wǎng)的拓?fù)湫蛄械臉?gòu)造過程，其拓?fù)湫蛄袨椋篤1、V2、V3、V5、V4、V6。6.5有向無環(huán)圖采用鄰接表存儲結(jié)構(gòu)的AOV網(wǎng)的拓?fù)渑判虻乃惴▽崿F(xiàn)：遍歷鄰接表，將各個頂點的入度保存在數(shù)組indegree中。將入度為零的頂點入棧，依次將棧頂元素出棧并輸出該頂點，對該頂點的鄰接頂點的入度減1，如果鄰接頂點的入度為零，則入棧，否則，將下一個鄰接頂點的入度減1并進行相同的處理。然后繼續(xù)將棧中元素出棧，重復(fù)執(zhí)行以上操作，直到?？諡橹埂Ｍ?fù)渑判騱hile(!S.StackEmpty())//如果棧S不為空

{inti=S.PopStack();//從棧S將已拓?fù)渑判虻捻旤ci彈出

System.out.print(G.vertex[i].data+"");count+=1;//對入棧T的頂點計數(shù)

ArcNodep=G.vertex[i].firstarc;while(p!=null)//處理編號為i的頂點的每個鄰接點

{intk=p.adjvex;//頂點序號為kindegree[k]-=1;if(indegree[k]==0)//如果k的入度減1后變?yōu)?，則將k入棧SS.PushStack(k);p=p.nextarc;}}6.5有向無環(huán)圖.AOE網(wǎng)AOE網(wǎng)是一個帶權(quán)的有向無環(huán)圖。其中，用頂點表示事件，弧表示活動，權(quán)值表示兩個活動持續(xù)的時間。AOE網(wǎng)是以邊表示活動的網(wǎng)（ActivityOnEdgeNetwork）。圖6.29所示是一個具有10個活動、8個事件的AOE網(wǎng)。v1、v2、…、v8表示8個事件，<v1,v2>、<v1,v3>、…、<v7,v8>表示10個活動，a1、a2、…、a10表示活動的執(zhí)行時間。進入頂點的有向弧表示的活動已經(jīng)完成，從頂點出發(fā)的有向弧表示的活動可以開始。頂點v1表示整個工程的開始，v8表示整個工程的結(jié)束。頂點v5表示活動a4、a5、a6已經(jīng)完成，活動a7和a8可以開始。其中，完成活動a5和活動a6分別需要5天和6天。6.5.2AOE網(wǎng)與關(guān)鍵路徑6.5有向無環(huán)圖2.關(guān)鍵路徑關(guān)鍵路徑是指在AOE網(wǎng)中從源點到匯點路徑最長的路徑。這里的路徑長度是指路徑上各個活動持續(xù)時間之和。在AOE網(wǎng)中，有些活動是可以并行執(zhí)行的。關(guān)鍵路徑其實就是完成工程的最短時間所經(jīng)過的路徑，關(guān)鍵路徑上的活動稱為關(guān)鍵活動。（1）事件vi的最早發(fā)生時間：從源點到頂點vi的最長路徑長度，稱為事件vi的最早發(fā)生時間，記作ve(i)。求解ve(i)可以從源點ve(0)=0開始，按照拓?fù)渑判蛞?guī)則根據(jù)遞推得到：ve(i)=Max{ve(k)+dut(<k,i>)|<k,i>∈T,1≤i≤n-1}6.5有向無環(huán)圖（2）事件vi的最晚發(fā)生時間：在保證整個工程完成的前提下，活動必須最遲的開始時間，記作vl(i)。在求解事件vi的最早發(fā)生時間ve(i)的前提vl(n-1)=ve(n-1)下，從匯點開始，向源點推進得到vl(i)：vl(i)=Min{vl(k)-dut(<i,k>)|<i,k>∈S,0≤i≤n-2}（3）活動ai的最早開始時間e(i)：如果弧<vk,vj>表示活動ai，當(dāng)事件vk發(fā)生之后，活動ai才開始。因此，事件vk的最早發(fā)生時間也就是活動ai的最早開始時間，即e(i)=ve(k)。（4）活動ai的最晚開始時間l(i)：在不推遲整個工程完成時間的基礎(chǔ)上，活動ai最遲必須開始的時間。如果弧<vk,vj>表示活動ai，持續(xù)時間為dut(<k,j>)，則活動ai的最晚開始時間l(i)=vl(j)-dut(<k,j>)。6.5有向無環(huán)圖求AOE網(wǎng)的關(guān)鍵路徑的算法如下：（1）對AOE網(wǎng)中的頂點進行拓?fù)渑判?，如果得到的拓?fù)湫蛄许旤c個數(shù)小于網(wǎng)中頂點數(shù)，則說明網(wǎng)中有環(huán)存在，不能求關(guān)鍵路徑，終止算法；否則，從源點v0開始，求出各個頂點的最早發(fā)生時間ve(i)。（2）從匯點vn出發(fā)vl(n-1)=ve(n-1)，按照逆拓?fù)湫蛄星笃渌旤c的最晚發(fā)生時間vl(i)。（3）由各頂點的最早發(fā)生時間ve(i)和最晚發(fā)生時間vl(i)，求出每個活動ai的最早開始時間e(i)和最晚開始時間l(i)。（4）找出所有滿足條件e(i)=l(i)的活動ai，ai即是關(guān)鍵活動。6.5有向無環(huán)圖利用求AOE網(wǎng)的關(guān)鍵路徑的算法，圖6.29所示的網(wǎng)中頂點對應(yīng)事件最早發(fā)生時間ve、最晚發(fā)生時間vl以及及弧對應(yīng)活動最早發(fā)生時間e、最晚發(fā)生時間如圖6.30所示。網(wǎng)的關(guān)鍵路徑是(v1,v2,v5,v6,v8)，關(guān)鍵活動是a1、a4、a7和a9。6.6最短路徑6.6.1從某個頂點到其余各頂點的最短路徑1.從某個頂點到其他頂點的最短路徑算法思想假設(shè)從有向圖的頂點v0出發(fā)到其余各個頂點的最短路徑。帶權(quán)有向圖G7及從v0出發(fā)到其他各個頂點的最短路徑如圖6.31所示。6.6最短路徑從頂點v0到頂點v2有兩條路徑：(v0,v1,v2)和(v0,v2)。其中，前者的路徑長度為70，后者的路徑長度為60。因此，(v0,v2)是從頂點v0到頂點v2的最短路徑。從頂點v0到頂點v3有三條路徑：(v0,v1,v2,v3)、(v0,v2,v3)和(v0,v1,v3)。其中，第一條路徑長度為120，第二條路徑長度為110，第三條路徑長度為130。因此，(v0,v2,v3)是從頂點v0到頂點v3的最短路徑。6.6最短路徑設(shè)有一個帶權(quán)有向圖D=(V,E)，定義一個數(shù)組dist，數(shù)組中的每個元素dist[i]表示頂點v0到頂點vi的最短路徑長度，則長度為dist[j]=Min{dist[i]|vi∈V}的路徑，表示從頂點v0出發(fā)到頂點vj的最短路徑。也就是說，在所有的頂點v0到頂點vj的路徑中，dist[j]是最短的一條路徑。而數(shù)組dist的初始狀態(tài)是：如果從頂點v0到頂點vi存在弧，則dist[i]是弧<v0,vj>的權(quán)值，否則dist[j]的值為∞。6.6最短路徑迪杰斯特拉算法求解最短路徑步驟如下（用鄰接矩陣存儲）：（1）初始時，S只包括源點v0，即S={v0}，V-S包括除v0以外的圖中的其他頂點。v0到其他頂點的路徑初始化為dist[i]=G.arc[0][i].adj。（2）選擇距離頂點vi最短的頂點vj，使得dist[j]=Min{dist[i]|vi∈V-S}dist[j]表示從v0到vj最短路徑長度，vj表示對應(yīng)的終點。（3）修改從v0到到頂點vi的最短路徑長度，其中vi∈V-S。如果有dist[k]+G.arc[k][i]<dist[i]，則修改dist[i]，使得dist[i]=dist[k]+G.arc[k][i].adj。（4）重復(fù)執(zhí)行步驟（2）和（3），直到所有從v0到其他頂點的最短路徑長度求出。。6.6最短路徑對圖6.31所示的圖G7求解從頂點v0到其他頂點的最短路徑，求解過程如圖6.32所示。6.6最短路徑6.6.2每一對頂點之間的最短路徑弗洛伊