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

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

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

數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(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è)圖G。

（2）DestroyGraph(&T)

初始條件：圖G存在。

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

（3）LocateVertex(G,v)

初始條件：圖G存在，頂點(diǎn)v合法。

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

（4）GetVertex(G,i)

初始條件：圖G存在。

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

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

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

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

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

//用于存儲(chǔ)頂點(diǎn)

doublearc[][];

//鄰接矩陣，存儲(chǔ)邊或弧的信息

intvexnum,arcnum;//頂點(diǎn)數(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圖的存儲(chǔ)結(jié)構(gòu)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力表頭結(jié)點(diǎn)有兩個(gè)域組成：數(shù)據(jù)域和指針域。其中，數(shù)據(jù)域用來(lái)存放頂點(diǎn)信息，指針域用來(lái)指向邊表中的第一個(gè)結(jié)點(diǎn)。通常情況下，表頭結(jié)點(diǎn)采用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)，邊表結(jié)點(diǎn)由三個(gè)域組成：鄰接點(diǎn)域、數(shù)據(jù)域和指針域。6.2.2鄰接表表示法6.2圖的存儲(chǔ)結(jié)構(gòu)學(xué)習(xí)基礎(chǔ)學(xué)習(xí)認(rèn)知能力6.2.2鄰接表表示法圖6.1所示的兩個(gè)圖G1和G2用鄰接表表示如圖6.11所示。圖6.8所示的帶權(quán)圖用鄰接表表示如圖6.12所示。6.2圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接表存儲(chǔ)結(jié)構(gòu)描述如下：enumGKind{DG,DN,UG,UN}//圖的類型classArcNode//邊結(jié)點(diǎn)的類型定義{intadjvex;//弧指向的頂點(diǎn)的位置

ArcNodenextarc;//指示下一個(gè)與該頂點(diǎn)相鄰接的頂點(diǎn)

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

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

this.firstarc=null;

//指向第一個(gè)與該頂點(diǎn)鄰接的頂點(diǎn)

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

GKindkind;AdjGraph()

{vertex=newVNode[MAXSIZE];vexnum=0;arcnum=0;kind=GKind.UG;}6.2圖的存儲(chǔ)結(jié)構(gòu)圖6.1所示的有向圖G1的逆鄰接鏈表如圖6.13所示。求某個(gè)頂點(diǎn)的入度，需要建立一個(gè)有向圖的逆鄰接鏈表，也就是為每個(gè)頂點(diǎn)vi建立一個(gè)以vi為弧頭的鏈表。6.2圖的存儲(chǔ)結(jié)構(gòu)【例6.2】編寫算法，采用鄰接表創(chuàng)建一個(gè)無(wú)向圖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圖的存儲(chǔ)結(jié)構(gòu)6.2.3十字鏈表十字鏈表是有向圖的又一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在十字鏈表中，將表頭結(jié)點(diǎn)稱為頂點(diǎn)結(jié)點(diǎn)，邊結(jié)點(diǎn)稱為弧結(jié)點(diǎn)。其中，頂點(diǎn)結(jié)點(diǎn)包含三個(gè)域：數(shù)據(jù)域和兩個(gè)指針域。兩個(gè)指針域，一個(gè)指向以頂點(diǎn)為弧頭頂點(diǎn)，另一個(gè)指向以頂點(diǎn)為弧尾的頂點(diǎn)，數(shù)據(jù)域存放頂點(diǎn)的信息。6.2圖的存儲(chǔ)結(jié)構(gòu)6.2.4鄰接多重表鄰接多重表（AdjacencyMulti_list）表示是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。頂點(diǎn)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：data域和firstedge域。數(shù)據(jù)域data用于存儲(chǔ)頂點(diǎn)的數(shù)據(jù)信息，firstedga域指示依附于頂點(diǎn)的第一條邊。邊結(jié)點(diǎn)包含六個(gè)域：mark域、ivex域、ilink域、jvex域、jlink域和info域。6.2圖的遍歷6.2.1圖的深度優(yōu)先遍歷1.圖的深度遍歷的定義圖的深度優(yōu)先遍歷是樹的先根遍歷的推廣。圖的深度優(yōu)先遍歷的思想是：從圖中某個(gè)頂點(diǎn)v0出發(fā)，訪問(wèn)頂點(diǎn)v0的第一個(gè)鄰接點(diǎn)，然后以該鄰接點(diǎn)為新的頂點(diǎn)，訪問(wèn)該頂點(diǎn)的鄰接點(diǎn)。重復(fù)執(zhí)行以上操作，直到當(dāng)前頂點(diǎn)沒(méi)有鄰接點(diǎn)為止。圖的深度優(yōu)先遍歷的序列為：A、B、E、F、C、D、G、H、I。6.3圖的遍歷6.3.1圖的深度優(yōu)先搜索遍歷publicvoidDFSTraverse(intvisited[])

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

{

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

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

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

{

if(visited[v]==0)

DFS(v,visited);

//對(duì)未訪問(wèn)的頂點(diǎn)v進(jìn)行深度優(yōu)先遍歷

}

System.out.println();

}

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

System.out.print(vertex[v].data+"");//訪問(wèn)第v個(gè)頂點(diǎn)

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

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

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

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

{if(visited[p.adjvex]==0)//如果該頂點(diǎn)未被訪問(wèn)過(guò)

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

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

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

{

intk=M.LocateVertex(u);//k為頂點(diǎn)u對(duì)應(yīng)的序號(hào)

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;//初始時(shí)集合U只包括頂點(diǎn)u

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

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

{k=MiniNum(M,closeedge);//k為與U中頂點(diǎn)相鄰接的下一個(gè)頂點(diǎn)的序號(hào)

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

closeedge[k].lowcost=0;//第k頂點(diǎn)并入U(xiǎn)集

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

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

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

ArcNodep=G.vertex[i].firstarc;while(p!=null)//處理編號(hào)為i的頂點(diǎn)的每個(gè)鄰接點(diǎn)

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