數(shù)據(jù)結(jié)構(gòu)-第七章圖

第7章圖7.1圖的定義與基本術(shù)語(yǔ)7.2圖的存儲(chǔ)結(jié)構(gòu)7.3圖的遍歷7.4圖的連通性問(wèn)題7.5有向無(wú)環(huán)圖的應(yīng)用7.6最短路徑圖結(jié)構(gòu)與表結(jié)構(gòu)和樹(shù)結(jié)構(gòu)的不同表現(xiàn)在結(jié)點(diǎn)之間的關(guān)系上，線(xiàn)性表中結(jié)點(diǎn)之間的關(guān)系是一對(duì)一的；樹(shù)是按分層關(guān)系組織的結(jié)構(gòu)，樹(shù)結(jié)構(gòu)之間是一對(duì)多；對(duì)于圖結(jié)構(gòu)，圖中頂點(diǎn)之間的關(guān)系可以是多對(duì)多，即一頂點(diǎn)和其它頂點(diǎn)間的關(guān)系是任意的，可以有關(guān)也可以無(wú)關(guān)。因此，圖G

樹(shù)TL，圖是一種比較復(fù)雜的非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。圖作為一種非線(xiàn)性結(jié)構(gòu)，被廣泛應(yīng)用于多個(gè)技術(shù)領(lǐng)域。在本章中，主要是應(yīng)用圖論的理論知識(shí)來(lái)討論如何在計(jì)算機(jī)上表示和處理圖，以及如何利用圖來(lái)解決一些實(shí)際問(wèn)題。7.1圖的定義與基本術(shù)語(yǔ)7.1.1圖的定義圖（Graph）是一種網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，其形式化定義如下：Graph=（V，R）V={x∣x∈DataObject}R={VR}VR={<x，y>∣P（x，y）∧（x，y∈V）}

DataObject為一個(gè)集合，該集合中的所有元素具有相同的特性。V中的數(shù)據(jù)元素通常稱(chēng)為頂點(diǎn)（vertex），VR是兩個(gè)頂點(diǎn)之間的關(guān)系的集合。P（x，y）表示x和y之間有特定的關(guān)聯(lián)屬性P。

?。喝?lt;x，y>∈VR，則<x，y>表示從頂點(diǎn)x到頂點(diǎn)y的一條?。╝rc），并稱(chēng)x為弧尾（tail）或起始點(diǎn)，稱(chēng)y為弧頭（head）或終端點(diǎn)。有向圖：若圖中的邊是有方向的，稱(chēng)這樣的圖為有向圖。無(wú)向圖：若<x，y>∈VR，必有<y，x>∈VR，即VR是對(duì)稱(chēng)關(guān)系，這時(shí)以無(wú)序?qū)Γ▁，y）來(lái)代替兩個(gè)有序?qū)?，表示x和y之間的一條邊（edge），此時(shí)的圖稱(chēng)為無(wú)向圖。

例如：下圖G1是有向圖，G2是無(wú)向圖2134G12145G23在圖中，我們可以將任一頂點(diǎn)看成是圖的第一個(gè)頂點(diǎn)，同理，對(duì)于任一頂點(diǎn)而言，它的鄰接點(diǎn)之間也不存在順序關(guān)系。為了操作的方便，我們需要將圖中的頂點(diǎn)按任意序列排列起來(lái)。頂點(diǎn)在這個(gè)人為的隨意排列中的位置序號(hào)稱(chēng)為頂點(diǎn)在圖中的位置。圖的基本操作和其它數(shù)據(jù)結(jié)構(gòu)一樣，也有創(chuàng)建、插入、刪除、查找等。圖的抽象類(lèi)型定義：ADTGraph數(shù)據(jù)對(duì)象V：一個(gè)集合，該集合中的所有元素具有相同的特性。數(shù)據(jù)關(guān)系R：R={VR}VR={<x，y>∣P（x，y）∧（x，y∈V）}基本操作：（1）GreateGraph(G)：創(chuàng)建圖G。（2）DestoryGraph(G)：銷(xiāo)毀圖G。（3）LocateVertex(G,v)：確定頂點(diǎn)v在圖G中的位置。若圖G中沒(méi)有頂點(diǎn)v，則函數(shù)值為“空”。（4）GetVertex(G,I)：取出圖G中的第i個(gè)頂點(diǎn)的值。若i>圖G中頂點(diǎn)數(shù)，則函數(shù)值為“空”。

（5）FirstAdjVertex(G,v)：求圖G中頂點(diǎn)v的第一個(gè)鄰接點(diǎn)。若v無(wú)鄰接點(diǎn)或圖G中無(wú)頂點(diǎn)v，則函數(shù)值為“空”。

（6）NextAdjVertex(G,v,w)：已知w是圖G中頂點(diǎn)v的某個(gè)鄰接點(diǎn)，求頂點(diǎn)v的下一個(gè)鄰接點(diǎn)（緊跟在w后面）。若w是v的最后一個(gè)鄰接點(diǎn)，則函數(shù)值為“空”。

（7）InsertVertex(G,u)：在圖G中增加一個(gè)頂點(diǎn)u。

（8）DeleteVertex（G，v）：刪除圖G的頂點(diǎn)v及與頂點(diǎn)v相關(guān)聯(lián)的弧。

（9）InsertArc（G，v，w）：在圖G中增加一條從頂點(diǎn)v到頂點(diǎn)w的弧。

（10）DeleteArc（G，v，w）：刪除圖G中從頂點(diǎn)v到頂點(diǎn)w的弧。

（11）TraverseGraph（G）：按照某種次序，對(duì)圖G的每個(gè)結(jié)點(diǎn)訪(fǎng)問(wèn)一次且最多一次。

7.1.2基本術(shù)語(yǔ)設(shè)用n表示圖中頂點(diǎn)的個(gè)數(shù)，用e表示圖中邊或弧的數(shù)目，并且不考慮圖中每個(gè)頂點(diǎn)到其自身的邊或弧。無(wú)向完全圖：有n（n-1）/2條邊（圖中每個(gè)頂點(diǎn)和其余n-1個(gè)頂點(diǎn)都有邊相連）的無(wú)向圖為無(wú)向完全圖。有向完全圖：有n（n-1）條邊（圖中每個(gè)頂點(diǎn)和其余n-1個(gè)頂點(diǎn)都有弧相連）的有向圖為有向完全圖。稀疏圖：對(duì)于有很少條邊的圖（e<nlogn）稱(chēng)為稀疏圖，反之稱(chēng)為稠密圖。

子圖：設(shè)有兩個(gè)圖G=（V，{E}）和圖G/=（V/，{E/}）,若V/V且E/

E，則稱(chēng)圖G/為G的子圖。

圖G1和圖G2的子圖見(jiàn)p155的圖7.2所示。對(duì)于無(wú)向圖

G=（V，{E}），如果邊（v，v/）∈E，則稱(chēng)頂點(diǎn)v，v/互為鄰接點(diǎn)，即v，v/相鄰接。邊（v，v/）依附于頂點(diǎn)v和v/，或者說(shuō)邊（v，v/）與頂點(diǎn)v和v/相關(guān)聯(lián)。對(duì)于有向圖G=（V，{A}）而言，若弧<v，v/>∈A，則稱(chēng)頂點(diǎn)v鄰接到頂點(diǎn)v/，頂點(diǎn)v/鄰接自頂點(diǎn)v，或者說(shuō)弧<v，v/>與頂點(diǎn)v，v/相關(guān)聯(lián)。

鄰接點(diǎn)：度、入度和出度對(duì)于無(wú)向圖而言，頂點(diǎn)v的度是指和v相關(guān)聯(lián)的邊的數(shù)目，記作TD（v）。

對(duì)于有向圖而言，頂點(diǎn)v的度有出度和入度兩部分：以頂點(diǎn)v為弧頭的弧的數(shù)目稱(chēng)為該頂點(diǎn)的入度，記作ID（v），以頂點(diǎn)v為弧尾的弧的數(shù)目稱(chēng)為該頂點(diǎn)的出度，記作OD（v）則頂點(diǎn)v的度為：

TD（v）=ID（v）+OD（v）。

一般地，若圖G中有n個(gè)頂點(diǎn)，e條邊或弧，則圖中頂點(diǎn)的度與邊的關(guān)系如下：e=TD(Vi)2ni=1權(quán)與網(wǎng)

:

在實(shí)際應(yīng)用中，有時(shí)圖的邊或弧上往往與具有一定意義的數(shù)有關(guān)，即每一條邊都有與它相關(guān)的數(shù)，稱(chēng)為權(quán)，這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)等信息。我們將這種帶權(quán)的圖叫做賦權(quán)圖或網(wǎng)。圖例見(jiàn)p156的圖7.3所示。路徑與回路無(wú)向圖G=（V，{E}）中從頂點(diǎn)v到v/的路徑是一個(gè)頂點(diǎn)序列vi0，vi1，vi2，…，vin，其中（vij-1，vij）∈E，1≤j≤n。如果圖G是有向圖，則路徑也是有向的，頂點(diǎn)序列應(yīng)滿(mǎn)足<vij-1，vij>∈A，1≤j≤n。

路徑長(zhǎng)度：指路徑上經(jīng)過(guò)的弧或邊的數(shù)目。

回路或環(huán)：在一個(gè)路徑中，若其第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)是相同的，即v=v/，則稱(chēng)該路徑為一個(gè)回路或環(huán)。簡(jiǎn)單路徑：若表示路徑的頂點(diǎn)序列中的頂點(diǎn)各不相同，則稱(chēng)這樣的路徑為簡(jiǎn)單路徑。簡(jiǎn)單回路：除了第一個(gè)和最后一個(gè)頂點(diǎn)外，其余各頂點(diǎn)均不重復(fù)出現(xiàn)的回路為簡(jiǎn)單回路。

連通圖

連通圖：在無(wú)向圖G=（V，{E}）中，若從vi到vj有路徑相通，則稱(chēng)頂點(diǎn)vi與vj是連通的。如果對(duì)于圖中的任意兩個(gè)頂點(diǎn)vi、vj∈V，vi，vj都是連通的，則稱(chēng)該無(wú)向圖G為連通圖。

連通分量：無(wú)向圖中的極大連通子圖稱(chēng)為該無(wú)向圖的連通分量。

強(qiáng)連通圖：在有向圖G=（V，{A}）中，若對(duì)于每對(duì)頂點(diǎn)vi、vj∈V且vi≠vj，從vi到vj和vj到vi都有路徑，則稱(chēng)該有向圖為強(qiáng)連通圖。強(qiáng)連通分量：有向圖的極大強(qiáng)連通子圖稱(chēng)作有向圖的強(qiáng)連通分量。圖G1和圖G3的連通分量見(jiàn)p157的圖7.4所示生成樹(shù)一個(gè)連通圖的生成樹(shù)是指一個(gè)極小連通子圖，它含有圖中的全部頂點(diǎn)，但只有足已構(gòu)成一棵樹(shù)的n-1條邊。如圖p157的圖7.5所示。7.2圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)方法有：①鄰接矩陣表示法；②鄰接表；③鄰接多重表；④十字鏈表

鄰接矩陣表示法

圖的鄰接矩陣表示法（AdjacencyMatrix）也稱(chēng)作數(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ù)組被稱(chēng)為鄰接矩陣。

若G是一具有n個(gè)頂點(diǎn)的無(wú)權(quán)圖，G的鄰接矩陣是具有如下性質(zhì)的n×n矩陣A：

A[i,j]=若<vi,vj>或（vi,vj)VR0反之G1和G2的鄰接矩陣見(jiàn)p158的圖7.6所示若圖G是一個(gè)有n個(gè)頂點(diǎn)的網(wǎng)，則它的鄰接矩陣是具有如下性質(zhì)的n×n矩陣A：A[i,j]=Wij

若<vi,vj>或（vi,vj)VR∞反之有向網(wǎng)及其鄰接矩陣見(jiàn)p158的圖7.7所示。鄰接矩陣表示法的C語(yǔ)言類(lèi)型描述為：#defineMAX_VERTEX_NUM10/*最多頂點(diǎn)個(gè)數(shù)*/#defineINFINITY32768/*最多頂點(diǎn)個(gè)數(shù)*/typedef

enum{DG,DN,UDG,UDN}GraphKind;/*圖的種類(lèi)：DG表示有向圖,DN表示有向網(wǎng),UDG表示無(wú)向圖,UDN表示無(wú)向網(wǎng)*/typedefcharVertexData;/*假設(shè)頂點(diǎn)數(shù)據(jù)為字符型*/typedef

struct

ArcNode{

AdjType

adj;/*對(duì)于無(wú)權(quán)圖，用1或0表示是否相鄰；對(duì)帶權(quán)圖，則為權(quán)值類(lèi)型*/

OtherInfoinfo;}ArcNode;typedef

struct{

VertexData

vexs[MAX_VERTEX_NUM];/*頂點(diǎn)向量*/

ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*鄰接矩陣*/

int

vexnum,arcnum;/*圖的頂點(diǎn)數(shù)和弧數(shù)*/

GraphKindkind;/*圖的種類(lèi)標(biāo)志*/}AdjMatrix;/*（AdjacencyMatrixGraph）*/

鄰接矩陣法的特點(diǎn)：1.存儲(chǔ)空間：對(duì)于無(wú)向圖而言，它的鄰接矩陣是對(duì)稱(chēng)矩陣，所以可采用壓縮存儲(chǔ)法（下三角），其存儲(chǔ)空間只需n(n-1)/2。但對(duì)于有向圖而言，因?yàn)樗幕∈怯蟹较虻?，它的鄰接矩陣不一定是?duì)稱(chēng)矩陣，所以需要n2個(gè)存儲(chǔ)空間。2.便于運(yùn)算：采用鄰接矩陣表示法，便于判定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連，即根據(jù)A[i，j]=0或1來(lái)判斷。另外還便于求得各個(gè)頂點(diǎn)的度。

對(duì)于無(wú)向圖而言，其鄰接矩陣第i行元素之和就是圖中第i個(gè)頂點(diǎn)的度：TD(vi)=A[i,j]j=1n對(duì)于有向圖而言，其鄰接矩陣第i行元素之和就是圖中第i個(gè)頂點(diǎn)的出度，第i列元素之和就是圖中第i個(gè)頂點(diǎn)的入度。

OD(vi)=A[i,j]j=1nID(vi)=A[j,i]j=1n頂點(diǎn)i的出度：頂點(diǎn)i的入度：采用鄰接矩陣存儲(chǔ)法表示圖，很便于實(shí)現(xiàn)圖的一些基本操作，如FirstAdjVertex（G，v）：（1）首先，由LocateVertex（G，v）找到v在圖中的位置，即v在一維數(shù)組vexs中的序號(hào)i。

（2）二維數(shù)組arcs中第i行上第一個(gè)adj域非零的分量所在的列號(hào)j，便是v的第一個(gè)鄰接點(diǎn)在圖G中的位置。

（3）取出一維數(shù)組vexs[j]中的數(shù)據(jù)信息，即與頂點(diǎn)v鄰接的第一個(gè)鄰接點(diǎn)的信息。

注意：稀疏圖不適于用鄰接矩陣來(lái)存儲(chǔ)，因?yàn)檫@樣會(huì)造成存儲(chǔ)空間的浪費(fèi)。用鄰接矩陣法創(chuàng)建有向網(wǎng)的算法如下：int

LocateVertex(AdjMatrix*G,VertexDatav)/*求頂點(diǎn)位置函數(shù)*/{intj=Error,k;

for(k=0;k<G->vexnum;k++)

if(G->vexs[k]==v) {j=k;break;}

return(j);}int

CreateDN(AdjMatrix*G)/*創(chuàng)建一個(gè)有向網(wǎng)*/{int

i,j,k,weight;VertexDatav1,v2;

scanf("%d,%d",&G->arcnum,&G->vexnum);/*輸入圖的頂點(diǎn)數(shù)和弧數(shù)*/

for(i=0;i<G->vexnum;i++)

for(j=0;j<G->vexnum;j++) G->arcs[i][j].adj=INFINITY;

for(i=0;i<G->vexnum;i++)

scanf("%c",&G->vexs[i]);/*輸入圖的頂點(diǎn)*/

for(k=0;k<G->arcnum;k++) {scanf("%c,%c,%d",&v1,&v2,&weight);/*輸入一條弧的兩個(gè)頂點(diǎn)及權(quán)值*/ i=LocateVex_M(G,v1); j=LocateVex_M(G,v2); G->arcs[i][j].adj=weight;/*建立弧*/ }

return(Ok);}分析：該算法的時(shí)間復(fù)雜度為O（n2+e×n），其中O（n2）時(shí)間耗費(fèi)在對(duì)二維數(shù)組arcs的每個(gè)分量的arj域初始化賦值上。O（e×n）的時(shí)間耗費(fèi)在有向網(wǎng)中邊權(quán)的賦值上。

鄰接表表示法鄰接表（AdjacencyList）表示法實(shí)際上是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

它的基本思想是只存有關(guān)聯(lián)的信息，對(duì)于圖中存在的邊信息則存儲(chǔ)，而對(duì)于不相鄰接的頂點(diǎn)則不保留信息。在鄰接表中，對(duì)圖中的每個(gè)頂點(diǎn)建立一個(gè)帶頭結(jié)點(diǎn)的邊鏈表，每個(gè)邊鏈表的頭結(jié)點(diǎn)又構(gòu)成一個(gè)表頭結(jié)點(diǎn)表。這樣，一個(gè)n個(gè)頂點(diǎn)的圖的鄰接表表示由表頭結(jié)點(diǎn)表與邊表兩部分構(gòu)成。（1）表頭結(jié)點(diǎn)表：由所有表頭結(jié)點(diǎn)以順序結(jié)構(gòu)（向量）的形式存儲(chǔ)，以便可以隨機(jī)訪(fǎng)問(wèn)任一頂點(diǎn)的單鏈表。表頭結(jié)點(diǎn)有兩部分構(gòu)成，其中數(shù)據(jù)域（vexdata）用于存儲(chǔ)頂點(diǎn)的名或其它有關(guān)信息；鏈域（firstarc）用于指向鏈表中第一個(gè)頂點(diǎn)（即與頂點(diǎn)vi鄰接的第一個(gè)鄰接點(diǎn)）。表頭結(jié)點(diǎn)結(jié)構(gòu)為：vexdatafirstarc（2）邊表：由表示圖中頂點(diǎn)間鄰接關(guān)系的n個(gè)邊鏈表組成。它由三部分組成，其中鄰接點(diǎn)域（adjvex）用于存放與頂點(diǎn)vi相鄰接的頂點(diǎn)在圖中的位置；鏈域（nextarc）用于指向與頂點(diǎn)vi相關(guān)聯(lián)的下一條邊或弧的結(jié)點(diǎn)；數(shù)據(jù)域（info）用于存放與邊或弧相關(guān)的信息（如賦權(quán)圖中每條邊或弧的權(quán)值等）。

adjvexinfonextarc弧結(jié)點(diǎn)結(jié)構(gòu)為：圖例p161的圖7.9所示是圖G1、G2的鄰接表表示法鄰接表存儲(chǔ)結(jié)構(gòu)的形式化說(shuō)明如下：#defineMAX_VERTEX_NUM10/*最多頂點(diǎn)個(gè)數(shù)*/typedef

enum{DG,DN,UDG,UDN}GraphKind;/*圖的種類(lèi)*/typedef

struct

ArcNode{int

adjvex;/*該弧指向頂點(diǎn)的位置*/

struct

ArcNode*nextarc;/*指向下一條弧的指針*/

OtherInfoinfo;/*與該弧相關(guān)的信息*/}ArcNode;

typedef

struct

VertexNode{

VertexDatadata;/*頂點(diǎn)數(shù)據(jù)*/

ArcNode*firstarc;/*指向該頂點(diǎn)第一條弧的指針*/}VertexNode;

typedef

struct{

VertexNode

vertex[MAX_VERTEX_NUM];

int

vexnum,arcnum;/*圖的頂點(diǎn)數(shù)和弧數(shù)*/

GraphKindkind;/*圖的種類(lèi)標(biāo)志*/}AdjList;/*基于鄰接表的圖(AdjacencyListGraph)*/

●存儲(chǔ)空間：對(duì)于有n個(gè)頂點(diǎn)，e條邊的無(wú)向圖而言，若采取鄰接表作為存儲(chǔ)結(jié)構(gòu)，則需要n個(gè)表頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。

●無(wú)向圖的度：在無(wú)向圖的鄰接表中，頂點(diǎn)vi的度恰好就是第i個(gè)邊鏈表上結(jié)點(diǎn)的個(gè)數(shù)。

●有向圖的度：在有向圖中，第i個(gè)邊鏈表上頂點(diǎn)的個(gè)數(shù)是頂點(diǎn)vi的出度。要想求得該頂點(diǎn)的入度，則必須遍歷整個(gè)鄰接表。在所有單鏈表中查找鄰接點(diǎn)域的值為i的結(jié)點(diǎn)并計(jì)數(shù)求和。由此可見(jiàn)，對(duì)于用鄰接表方式存儲(chǔ)的有向圖，求頂點(diǎn)的入度并不方便，因此需要有一種解決的方法－逆鄰接表法。對(duì)圖中的每一頂點(diǎn)vi建立一個(gè)遞鄰接表，即對(duì)每個(gè)頂點(diǎn)vi建立一個(gè)所有以頂點(diǎn)vi為弧頭的弧的表，這樣求頂點(diǎn)vi的入度即是計(jì)算逆鄰接表中第i個(gè)頂點(diǎn)的邊鏈表中結(jié)點(diǎn)個(gè)數(shù)。

圖G1的逆鄰接表表示法見(jiàn)p162的圖7.10十字鏈表十字鏈表(OrthogonalList)是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。我們也可以把它看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)形成的一種鏈表。有向圖中的每一條弧對(duì)應(yīng)十字鏈表中的一個(gè)弧結(jié)點(diǎn)，同時(shí)有向圖中的每個(gè)頂點(diǎn)在十字鏈表中對(duì)應(yīng)有一個(gè)結(jié)點(diǎn)，叫做頂點(diǎn)結(jié)點(diǎn)。

這兩類(lèi)結(jié)點(diǎn)的結(jié)構(gòu)見(jiàn)p162的圖7.11所示。圖G1的十字鏈表表示見(jiàn)p163的圖7.12所示。12

∧

13∧

∧4

1∧

∧1

3

2

∧4

34∧∧1234建立一個(gè)有向圖的十字鏈表的算法如下：

voidCrtOrthList（OrthListg）/*從終端輸入n個(gè)頂點(diǎn)的信息和e條弧的信息，以建立一個(gè)有向圖的十字鏈表*/{scanf(“%d,%d”,&n,&e);/*鍵盤(pán)輸入圖的頂點(diǎn)個(gè)數(shù)和弧的個(gè)數(shù)*/for(i=0;i<n;i++){scanf(“%c”,g.vertex[i].data）；

g.vertex[i].firstin=NULL；g.vertex[i].firsout=NULL；

}for(k=0;k<e;k++){scanf(“%c,%c”,&vt,&vh);i=LocateVertex（g，vt）；j=LocateVertex（g，vh）；

p=alloc(sizeof(ArcNode));p->tailvex=i；p->headvex=j；

p->tlink=g.vertex[i].firstout；g.vertex[i].firstout=p；

p->hlink=

g.vertex[j].firstin；g.vertex[j].firstin=p；

}}/*CrtOrthList*/

十字鏈表的優(yōu)點(diǎn)：在十字鏈表中既能夠很容易地找到以vi為尾的弧，也能夠容易地找到以vi為頭的弧，因此對(duì)于有向圖，若采用十字鏈表作為存儲(chǔ)結(jié)構(gòu)，則很容易求出頂點(diǎn)vi的度。

鄰接多重表鄰接多重表(AdjacencyMulti_list)是無(wú)向圖的另外一種存儲(chǔ)結(jié)構(gòu)。使用鄰接多重表這種存儲(chǔ)結(jié)構(gòu)是因?yàn)樗軌蛱峁└鼮榉奖愕倪吿幚硇畔ⅰ?/p>

鄰接多重表是指將圖中關(guān)于一條邊的信息用一個(gè)結(jié)點(diǎn)來(lái)表示。鄰接多重表中的邊結(jié)點(diǎn)結(jié)構(gòu)和頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)見(jiàn)p164的圖7.13所示。鄰接多重表的結(jié)構(gòu)類(lèi)型說(shuō)明如下：typedef

struct

EdgeNode{int

mark,ivex,jvex;struct

EdgeNode*ilink,*jlink;}EdgeNode;typedef

struct{

VertexDatadata;

EdgeNode*firstedge;}VertexNode;typedef

struct{

VertexNode

vertex[MAX_VERTEX_NUM];

int

vexnum,arcnum;/*圖的頂點(diǎn)數(shù)和弧數(shù)*/

GraphKindkind;/*圖的種類(lèi)*/}AdjMultiList;/*基于圖的鄰接多重表表示法(AdjacencyMulti_list)*/圖G2的鄰接多重表見(jiàn)p165的圖7.14所示。7.4圖的遍歷圖的遍歷：從圖中的某個(gè)頂點(diǎn)出發(fā)，按某種方法對(duì)圖中的所有頂點(diǎn)訪(fǎng)問(wèn)且僅訪(fǎng)問(wèn)一次。

為了保證圖中的各頂點(diǎn)在遍歷過(guò)程中訪(fǎng)問(wèn)且僅訪(fǎng)問(wèn)一次，需要為每個(gè)頂點(diǎn)設(shè)一個(gè)訪(fǎng)問(wèn)標(biāo)志，用以標(biāo)示圖中每個(gè)頂點(diǎn)是否被訪(fǎng)問(wèn)過(guò)，訪(fǎng)問(wèn)標(biāo)志用數(shù)組visited[n]來(lái)表示。

圖的遍歷方法有兩種：深度優(yōu)先搜索和廣度優(yōu)先搜索深度優(yōu)先搜索：深度優(yōu)先搜索（Depth_FirstSearch）是指按照深度方向搜索，它類(lèi)似于樹(shù)的先根遍歷。深度優(yōu)先算法的基本思想是：（1）從圖中某個(gè)頂點(diǎn)v0出發(fā)，首先訪(fǎng)問(wèn)v0。

（2）找出剛訪(fǎng)問(wèn)過(guò)的頂點(diǎn)vi的第一個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)，然后訪(fǎng)問(wèn)該頂點(diǎn)。重復(fù)此步驟，直到當(dāng)前的頂點(diǎn)沒(méi)有未被訪(fǎng)問(wèn)的鄰接點(diǎn)為止。（3）返回前一個(gè)訪(fǎng)問(wèn)過(guò)的頂點(diǎn)，找出該頂點(diǎn)的下一個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)，訪(fǎng)問(wèn)該頂點(diǎn)。轉(zhuǎn)2。

采用遞歸的形式說(shuō)明，則深度優(yōu)先搜索連通子圖的的基本思想可表示為：

（1）訪(fǎng)問(wèn)出發(fā)點(diǎn)v0。

（2）依次以v0的未被訪(fǎng)問(wèn)的鄰接點(diǎn)為出發(fā)點(diǎn)，深度優(yōu)先搜索圖，直至圖中所有與v0有路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)。若此時(shí)圖中還有頂點(diǎn)未被訪(fǎng)問(wèn)，則另選圖中一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述深度優(yōu)先搜索過(guò)程，直至圖中所有頂點(diǎn)均被訪(fǎng)問(wèn)過(guò)為止。

深度優(yōu)先搜索的過(guò)程示例見(jiàn)p167的7.15圖所示。其中實(shí)箭頭代表訪(fǎng)問(wèn)方向，虛箭頭代表回溯方向，箭頭旁邊的數(shù)字代表搜索順序，A為起始頂點(diǎn)。8ADGBEHCFI1236710114155149131216訪(fǎng)問(wèn)序列為：A、B、C、F、E、G、D、H、I。圖的深度優(yōu)先搜索的算法描述如下：#defineTrue1#defineFalse0#defineError–1/*出錯(cuò)*/#defineOk1int

visited[MAX_VERTEX_NUM];/*訪(fǎng)問(wèn)標(biāo)志數(shù)組*/

voidTraverseGraph(Graphg)/*對(duì)圖g進(jìn)行深度優(yōu)先搜索，Graph表示圖的一種存儲(chǔ)結(jié)構(gòu)，如數(shù)組表示法或鄰接表等*/{for(vi=0;vi<g.vexnum;vi++)visited[vi]=False;/*訪(fǎng)問(wèn)標(biāo)志數(shù)組初始*/for(vi=0;vi<g.vexnum;vi++) /*調(diào)用深度遍歷連通子圖的操作*//*若圖g是連通圖，則此循環(huán)只執(zhí)行一次*/ if(！visited[vi])DepthFirstSearch(g，vi)；}/*TraverseGraph*/

深度遍歷v0所在地連通子圖算法如下：voidDepthFirstSearch（Graphg,intv0）/*深度遍歷v0所在的連通子圖*/{visit（v0）；visited[v0]=True；/*訪(fǎng)問(wèn)頂點(diǎn)v0，并置訪(fǎng)問(wèn)標(biāo)志數(shù)組相應(yīng)分量值*/w=FirstAdjVertex(g,v0);while(w!=-1)/*鄰接點(diǎn)存在*/{if(!visited[w])DepthFirstSearch(g,w);/*遞歸調(diào)用DepthFirstSearch*/w=NextAdjVertex(g,v0,w);/*找下一個(gè)鄰接點(diǎn)*/}}/*DepthFirstSearch*/

上述算法中對(duì)于FirstAdjVertex（g，v0）以及NextAdjVertex（g，v0，w）并沒(méi)有具體實(shí)現(xiàn)。因?yàn)閷?duì)于圖的不同存儲(chǔ)方法，兩個(gè)操作的實(shí)現(xiàn)方法不同，時(shí)間耗費(fèi)也不同。

下面的算法是在鄰接矩陣與鄰接表方式下實(shí)現(xiàn)上面算法的功能。1）用鄰接矩陣方式實(shí)現(xiàn)深度優(yōu)先搜索voidDepthFirstSearch(AdjMatrixg,intv0)/*圖g為鄰接矩陣類(lèi)型AdjMatrix*/

{visit(v0);visited[v0]=True;for(vj=0;vj<n;vj++)if(!visited[vj]&&g.arcs[v0][vj].adj==1)

DepthFirstSearch(g,vj);}/*DepthFirstSearch*/

2）用鄰接表方式實(shí)現(xiàn)深度優(yōu)先搜索voidDepthFirstSearch(AdjListg,intv0)/*圖g為鄰接表類(lèi)型AdjList*/{visit(v0)；visited[v0]=True；p=g.vertex[v0].firstarc；while(p!=NULL){if(!visited[p->adjvex])

DepthFirstSearch（g，p->adjvex）；

p=p->nextarc；

}}/*DepthFirstSearch*/

分析算法：以鄰接表作為存儲(chǔ)結(jié)構(gòu)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)的時(shí)間復(fù)雜度為O(e)，

其中e是無(wú)向圖中的邊數(shù)或有向圖中弧數(shù),則深度優(yōu)先搜索圖的時(shí)間復(fù)雜度為O(n+e)。

3）用非遞歸過(guò)程實(shí)現(xiàn)深度優(yōu)先搜索voidDepthFirstSearch(Graphg,intv0)/*從v0出發(fā)深度優(yōu)先搜索圖g*/{

InitStack(S);/*初始化空棧*/Push(S,v0)；while(!Empty(S)){v=Pop(S);if(!visited(v))/*棧中可能有重復(fù)結(jié)點(diǎn)*/{visit(v);visited[v]=True;}w=FirstAdj(g,v);/*求v的第一個(gè)鄰接點(diǎn)*/while(w!=-1){ if(!visited(w))Push(S,w);w=NextAdj(g,v,w);/*求v相對(duì)于w的下一個(gè)鄰接點(diǎn)*/}}}

7.3.2廣度優(yōu)先搜索廣度優(yōu)先搜索（Breadth_FirstSearch）是指按照廣度方向搜索，它類(lèi)似于樹(shù)的按層次遍歷。廣度優(yōu)先搜索的基本思想是：（1）從圖中某個(gè)頂點(diǎn)v0出發(fā)，首先訪(fǎng)問(wèn)v0。

（2）依次訪(fǎng)問(wèn)v0的各個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)。

（3）分別從這些鄰接點(diǎn)（端結(jié)點(diǎn)）出發(fā)，依次訪(fǎng)問(wèn)它們的各個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)（新的端結(jié)點(diǎn)）。

訪(fǎng)問(wèn)時(shí)應(yīng)保證：如果Vi和Vk為當(dāng)前端結(jié)點(diǎn)，且Vi在Vk之前被訪(fǎng)問(wèn)，則Vi的所有未被訪(fǎng)問(wèn)的鄰接點(diǎn)應(yīng)在Vk的所有未被訪(fǎng)問(wèn)的鄰接點(diǎn)之前訪(fǎng)問(wèn)。重復(fù)（3），直到所有端結(jié)點(diǎn)均沒(méi)有未被訪(fǎng)問(wèn)的鄰接點(diǎn)為止。

若此時(shí)還有頂點(diǎn)未被訪(fǎng)問(wèn)，則選一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作為起始點(diǎn)，重復(fù)上述過(guò)程，直至所有頂點(diǎn)均被訪(fǎng)問(wèn)過(guò)為止。

廣度優(yōu)先搜索過(guò)程示例見(jiàn)p169的圖7.16所示。其中箭頭代表搜索方向，箭頭旁邊的數(shù)字代表搜索順序，A為起始頂點(diǎn)。ADGBEHCFI14657823訪(fǎng)問(wèn)序列為：A、B、E、D、C、G、F、H、I。廣度優(yōu)先搜索連通子圖的算法如下：voidBreadthFirstSearch(Graphg,intv0)/*廣度優(yōu)先搜索圖g中v0所在的連通子圖*/{visit(v0);visited[v0]=True;InitQueue(&Q);/*初始化空隊(duì)*/

EnterQueue(&Q,v0)；/*v0進(jìn)隊(duì)*/while(!Empty(Q)){DeleteQueue(&Q,&v);/*隊(duì)頭元素出隊(duì)*/w=FirstAdj(g,v);/*求v的第一個(gè)鄰接點(diǎn)*/while(w!=-1){ if(!visited(w)){visit(w);visited[w]=True;

EnterQueue(&Q,w);}

w=NextAdj(g,v,w);/*求v相對(duì)于w的下一個(gè)鄰接點(diǎn)*/}}}

7.4圖的連通性問(wèn)題無(wú)向圖的連通分量在對(duì)圖遍歷時(shí)，對(duì)于連通圖，無(wú)論是廣度優(yōu)先搜索還是深度優(yōu)先搜索，僅需要調(diào)用一次搜索過(guò)程，即從任一個(gè)頂點(diǎn)出發(fā)，便可以遍歷圖中的各個(gè)頂點(diǎn)。對(duì)于非連通圖，則需要多次調(diào)用搜索過(guò)程，而每次調(diào)用得到的頂點(diǎn)訪(fǎng)問(wèn)序列恰為各連通分量中的頂點(diǎn)集。調(diào)用搜索過(guò)程的次數(shù)就是該圖連通分量的個(gè)數(shù)。例如：p171的圖7.17(a)是一個(gè)非連通圖，按照它的鄰接表進(jìn)行深度優(yōu)先搜索遍歷，三次調(diào)用深度優(yōu)先搜索（DepthFirstSearch）過(guò)程得到的訪(fǎng)問(wèn)頂點(diǎn)序列為：1，2，4，3，95，6，78，10因此有三個(gè)連通分量。如p171的圖7.17(c).最小生成樹(shù)在一個(gè)連通網(wǎng)的所有生成樹(shù)中，各邊的代價(jià)之和最小的那棵生成樹(shù)稱(chēng)為該連通網(wǎng)的最小代價(jià)生成樹(shù)（MinimumCostSpanningTree），簡(jiǎn)稱(chēng)為最小生成樹(shù)。

最小生成樹(shù)的重要性質(zhì)如下：設(shè)N=(V,{E})是一連通網(wǎng)，U是頂點(diǎn)集V的一個(gè)非空子集。若（u,v）是一條具有最小權(quán)值的邊，其中u∈U，v∈V-U，則存在一棵包含邊（u,v）的最小生成樹(shù)。

用反證法來(lái)證明這個(gè)最小生成樹(shù)（MST）的性質(zhì)：假設(shè)不存在這樣一棵包含邊（u,v）的最小生成樹(shù)。任取一棵最小生成樹(shù)T，將（u,v）加入T中。根據(jù)樹(shù)的性質(zhì)，此時(shí)T中必形成一個(gè)包含（u,v）的回路，且回路中必有一條邊（u’,v’）的權(quán)值大于或等于（u,v）的權(quán)值。刪除（u,v），則得到一棵代價(jià)小于等于T的生成樹(shù)T’，且T’為一棵包含邊（u,v）的最小生成樹(shù)。這與假設(shè)矛盾。

一個(gè)連通網(wǎng)的最小生成樹(shù)算法：普里姆算法假設(shè)N=(V,{E})是連通網(wǎng)，TE為最小生成樹(shù)中邊的集合。（1）初始U={u0}(u0∈V),TE=φ；

（2）在所有u∈U,v∈V-U的邊中選一條代價(jià)最小的邊（u0，v0）并入集合TE，同時(shí)將v0并入U(xiǎn)；

（3）重復(fù)（2），直到U=V為止。

此時(shí)，TE中必含有n-1條邊，則T=（V，{TE}）為N的最小生成樹(shù)。

普里姆算法是逐步增加U中的頂點(diǎn)，可稱(chēng)為“加點(diǎn)法”注意：選擇最小邊時(shí)，可能有多條同樣權(quán)值的邊可供選擇，此時(shí)任選其一。為了實(shí)現(xiàn)這個(gè)算法需設(shè)一個(gè)輔助數(shù)組closedge[]，以記錄從U道V-U具有最小代價(jià)的邊。對(duì)每個(gè)頂點(diǎn)v∈V-U，在輔助數(shù)組中存在一個(gè)分量closedge[v]，它包括兩個(gè)域vex和lowcost，其中l(wèi)owcost存儲(chǔ)該邊上的權(quán)，顯然有

closedge[v].lowcoast=Min({cost(u,v)|u∈U})普里姆算法可描述為：struct{VertexData

adjvex;

int

lowcost;}closedge[MAX_VERTEX_NUM];/*求最小生成樹(shù)時(shí)的輔助數(shù)組*/MiniSpanTree_Prim(AdjMatrix

gn,VertexData

u)/*從頂點(diǎn)u出發(fā)，按普里姆算法構(gòu)造連通網(wǎng)gn

的最小生成樹(shù)，并輸出生成樹(shù)的每條邊*/{k=LocateVertex(gn,u);closedge[k].lowcost=0;/*初始化，U={u}*/for(i=0;i<gn.vexnum;i++)if(i!=k)/*對(duì)V-U中的頂點(diǎn)i，初始化closedge[i]*/{closedge[i].adjvex=u;closedge[i].lowcost=gn.arcs[k][i].adj;}for(e=1;e<=gn.vexnum-1;e++)/*找n-1條邊(n=gn.vexnum)*/{k0=Minium(closedge);/*closedge[k0]中存有當(dāng)前最小邊（u0,v0）的信息*/u0=closedge[k0].adjvex;/*u0∈U*/v0=gn.vexs[k0]/*v0∈V-U*/printf(u0,v0);/*輸出生成樹(shù)的當(dāng)前最小邊（u0,v0）*/closedge[k0].lowcost=0;/*將頂點(diǎn)v0納入U(xiǎn)集合*/for(i=0;i<vexnum;i++)/*在頂點(diǎn)v0并入U(xiǎn)之后，更新closedge[i]*/if(gn.arcs[k0][i].adj<closedge[i].lowcost){closedge[i].lowcost=gn.arcs[k0][i].adj;

closedge[i].adjvex=v0;}}}

P173的圖7.18(a)是一個(gè)連通網(wǎng)，由普里姆算法構(gòu)造最小生成樹(shù)的過(guò)程見(jiàn)圖7.18(b)~(f)所示。算法中各參量的變化見(jiàn)p173的表7－1。2.克魯斯卡爾算法假設(shè)N=(V,{E})是連通網(wǎng)，將N中的邊按權(quán)值從小到大的順序排列；（1）將n個(gè)頂點(diǎn)看成n個(gè)集合；

（2）按權(quán)值由小到大的順序選擇邊，所選邊應(yīng)滿(mǎn)足兩個(gè)頂點(diǎn)不在同一個(gè)頂點(diǎn)集合內(nèi)，將該邊放到生成樹(shù)邊的集合中。同時(shí)將該邊的兩個(gè)頂點(diǎn)所在的頂點(diǎn)集合合并；（3）重復(fù)（2），直到所有的頂點(diǎn)都在同一個(gè)頂點(diǎn)集合內(nèi)?？唆斔箍査惴ㄊ侵鸩皆黾由蓸?shù)的邊，故稱(chēng)為“加邊法”以p174的連通圖7.19(a)為例，說(shuō)明克魯斯卡爾算法的執(zhí)行過(guò)程。7.5有向無(wú)環(huán)圖的應(yīng)用拓?fù)渑判颍═opologicalSort）

AOV-網(wǎng)：用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向無(wú)環(huán)圖，稱(chēng)為頂點(diǎn)表示活動(dòng)的網(wǎng)（ActivityOnVertexNetwork），簡(jiǎn)稱(chēng)為AOV-網(wǎng)。

如p175的表7-2課程關(guān)系，用頂點(diǎn)表示課程，弧表示先決條件，則表7－2可用一個(gè)有向無(wú)環(huán)圖表示。見(jiàn)圖p175的圖7.21。拓?fù)湫蛄校涸谟邢驁DG=（V，{E}）中，

V中頂點(diǎn)的線(xiàn)性序列（vi1,,vi1,,vi3,…，vin）稱(chēng)為拓?fù)湫蛄小４诵蛄斜仨殱M(mǎn)足：對(duì)序列中任意兩個(gè)頂點(diǎn)vi、vj，在G中有一條從vi到vj的路徑，則在序列中vi必排在vj之前。

如p175的圖7.21的一個(gè)拓?fù)湫蛄袨椋篊1,C2,C3,C4,C5,C8,C9,C7,C6。

AOV-網(wǎng)的特性如下：

若vi為vj的先行活動(dòng)，vj為vk的先行活動(dòng)，則vi必為vk的先行活動(dòng)，即先行關(guān)系具有可傳遞性。AOV-網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏摹Ｈ鏿175的圖7.21的另一個(gè)拓?fù)湫蛄袨椋篊1,C2,C3,C8,C4,C5,C9,C7,C6。

求拓?fù)渑判虻幕舅枷耄海?）從有向圖中選一個(gè)無(wú)前驅(qū)的頂點(diǎn)輸出；（2）將此頂點(diǎn)和以它為起點(diǎn)的弧刪除；（3）重復(fù)（1）、（2），直到不存在無(wú)前驅(qū)的頂點(diǎn)；（4）若此時(shí)輸出的頂點(diǎn)數(shù)小于有向圖中的頂點(diǎn)數(shù)，則說(shuō)明有向圖中存在回路，否則輸出的頂點(diǎn)的順序即為一個(gè)拓?fù)湫蛄小?/p>

例如p176的圖7.22所示的AOV－網(wǎng)，其拓?fù)湫蛄袨椋簐1,v6,v4,v3,v2,v5或v1,v3,v2,v6,v4,v5對(duì)于有向圖的不同存儲(chǔ)形式，有不同實(shí)現(xiàn)的拓?fù)渑判蛩惴ā?）基于鄰接矩陣表示的存儲(chǔ)結(jié)構(gòu)A為有向圖G的鄰接矩陣，則有（1）找G中無(wú)前驅(qū)的頂點(diǎn)—在A中找到值全為0的列；（2）刪除以i為起點(diǎn)的所有弧—將矩陣中i對(duì)應(yīng)的行全部置為0。

算法步驟為：（1）取1作為第一新序號(hào)；（2）找一個(gè)未新編號(hào)的、值全為0的列j，若找到則轉(zhuǎn)（3）；否則，若所有的列全部都編過(guò)號(hào)，拓?fù)渑判蚪Y(jié)束；若有列未曾被編號(hào)，則該圖中有回路；（3）輸出列號(hào)對(duì)應(yīng)的頂點(diǎn)j，把新序號(hào)賦給所找到的列；（4）將矩陣中j對(duì)應(yīng)的行全部置為0;（5）新序號(hào)加1，轉(zhuǎn)（2）；

2）基于鄰接表的存儲(chǔ)結(jié)構(gòu)

入度為零的頂點(diǎn)即沒(méi)有前趨的頂點(diǎn)，因此我們可以附設(shè)一個(gè)存放各頂點(diǎn)入度的數(shù)組indegree[]，于是有

（1）找G中無(wú)前驅(qū)的頂點(diǎn)——查找indegree[i]為零的頂點(diǎn)vi；（2）刪除以i為起點(diǎn)的所有弧——對(duì)鏈在頂點(diǎn)i后面的所有鄰接頂點(diǎn)k，將對(duì)應(yīng)的indegree[k]減1。

為了避免重復(fù)檢測(cè)入度為零的頂點(diǎn)，可以再設(shè)置一個(gè)輔助棧，若某一頂點(diǎn)的入度減為0，則將它入棧。每當(dāng)輸出某一頂點(diǎn)時(shí)，便將它從棧中刪除。

拓?fù)渑判虻膶?shí)現(xiàn)算法int

TopoSort(AdjListG){StackS;int

indegree[MAX_VERTEX_NUM];inti,count,k;

ArcNode*p;

FindID(G,indegree);/*求各頂點(diǎn)入度*/

InitStack(&S);/*初始化輔助棧*/

for(i=0;i<G.vexnum;i++)

if(indegree[i]==0)Push(&S,i);/*將入度為0的頂點(diǎn)入棧*/count=0;

while(!StackEmpty(S)){Pop(&S,&i);

printf("%c",G.vertex[i].data); count++;/*輸出i號(hào)頂點(diǎn)并計(jì)數(shù)*/p=G.vertexes[i].firstarc;

while(p!=NULL) {k=p->adjvex;

indegree[k]--;/*i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1*/

if(indegree[k]==0)Push(&S,k);/*若入度減為0，則入棧*/ p=p->nextarc; } }/*while*/if(count<G.vexnum)return(Error);/*該有向圖含有回路*/elsereturn(Ok);}求各頂點(diǎn)入度的函數(shù)voidFindID(AdjListG,int

indegree[MAX_VERTEX_NUM])/*求各頂點(diǎn)的入度*/{inti;ArcNode*p;

for(i=0;i<G.vexnum;i++)

indegree[i]=0;

for(i=0;i<G.vexnum;i++){p=G.vertexes[i].firstarc;

while(p!=NULL) {indegree[p->adjvex]++; p=p->nextarc; }}/*for*/}P176的圖7.22所示的AOV-網(wǎng)的鄰接表如圖p178的圖7.23所示，用拓?fù)渑判蛩惴ㄇ蟪龅耐負(fù)湫蛄袨椋簐6，v1，v3，v2，v4，v5。

算法的時(shí)間復(fù)雜度分析：若有向無(wú)環(huán)圖有n個(gè)頂點(diǎn)和e條弧，則在拓?fù)渑判虻乃惴ㄖ?，for循環(huán)需要執(zhí)行n次，時(shí)間復(fù)雜度為O(n)；對(duì)于while循環(huán)，由于每一頂點(diǎn)必定進(jìn)一次棧，出一次棧，其時(shí)間復(fù)雜度為O(e)；故該算法的時(shí)間復(fù)雜度為O(n+e)。

關(guān)鍵路徑AOE-網(wǎng)：在有向圖中，用頂點(diǎn)表示事件，用弧表示活動(dòng)，弧的權(quán)值表示活動(dòng)所需要的時(shí)間。我們把用這種方法構(gòu)造的有向無(wú)環(huán)圖叫做邊表示活動(dòng)的網(wǎng)（ActivityOnEdgeNetwork）,簡(jiǎn)稱(chēng)AOE-網(wǎng)。

AOE-網(wǎng)用在工程計(jì)劃和管理中，人們最關(guān)心的是：哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵活動(dòng)？至少需要多長(zhǎng)時(shí)間能完成整個(gè)工程？源點(diǎn)：存在唯一的、入度為零的頂點(diǎn)，叫源點(diǎn)。匯點(diǎn)：存在唯一的、出度為零的頂點(diǎn)，叫匯點(diǎn)。關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度即為完成整個(gè)工程任務(wù)所需的時(shí)間，該路徑叫做關(guān)鍵路徑。關(guān)鍵活動(dòng)：關(guān)鍵路徑上的活動(dòng)叫做關(guān)鍵活動(dòng)。

在AOE-網(wǎng)中的基本概念：例如p179的圖7.24所示的AOE-網(wǎng)。V0為源點(diǎn)，表示整個(gè)工程可以開(kāi)始，v8為匯點(diǎn)，表示整個(gè)工程結(jié)束。幾個(gè)重要的定義：事件vi的最早發(fā)生時(shí)間ve(i)：從源點(diǎn)到頂點(diǎn)vi的最長(zhǎng)路徑的長(zhǎng)度，叫做事件vi的最早發(fā)生時(shí)間。求ve(i)時(shí)可從源點(diǎn)開(kāi)始，按拓?fù)漤樞蛳騾R點(diǎn)遞推：ve(0)=0；

ve(i)=Max{ve(k)＋dut(<k,i>)}<k,i>∈T,1≤i≤n-1;其中，T為所有以i為頭的弧<k,i>的集合，dut（<k,i>）表示與弧<k,i>對(duì)應(yīng)的活動(dòng)的持續(xù)時(shí)間。事件vi的最晚發(fā)生時(shí)間vl(i)：在保證匯點(diǎn)按其最早發(fā)生時(shí)間發(fā)生這一前提下，事件vi的最晚發(fā)生時(shí)間。在求出ve(i)的基礎(chǔ)上，可從匯點(diǎn)開(kāi)始，按逆拓?fù)漤樞蛳蛟袋c(diǎn)遞推，求出vl(i)：vl(n-1)=ve(n-1)；

vl(i)=Min{vl(k)＋dut(<i,k>)}<i,k>∈S,0≤i≤n-2;其中，S為所有以i為尾的弧<i,k>的集合，dut（<i,k>）表示與弧<i,k>對(duì)應(yīng)的活動(dòng)的持續(xù)時(shí)間。

活動(dòng)ai的最早開(kāi)始時(shí)間e(i)：如果活動(dòng)ai對(duì)應(yīng)的弧為<j,k>，則e(i)等于從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑的長(zhǎng)度，即：e(i)=ve(j)

活動(dòng)ai的最晚開(kāi)始時(shí)間l(i)：如果活動(dòng)ai對(duì)應(yīng)的弧為<j,k>，其持續(xù)時(shí)間為dut（<j,k>）則有：l(i)=vl(k)-dut（<j,k>）

活動(dòng)ai的松弛時(shí)間（時(shí)間余量）：ai的最晚開(kāi)始時(shí)間與ai的最早開(kāi)始時(shí)間之差：l(i)-e(i)。顯然，松弛時(shí)間（時(shí)間余量）為0的活動(dòng)為關(guān)鍵活動(dòng)。

求關(guān)鍵路徑的基本步驟：（1）對(duì)圖中頂點(diǎn)進(jìn)行拓?fù)渑判?，在排序過(guò)程中按拓?fù)湫蛄星蟪雒總€(gè)事件的最早發(fā)生時(shí)間ve(i)；（2）按逆拓?fù)湫蛄星竺總€(gè)事件的最晚發(fā)生時(shí)間vl(i)；（3）求出每個(gè)活動(dòng)ai的最早開(kāi)始時(shí)間e(i)和最晚發(fā)生時(shí)間l(i)；4)找出e(i)=l(i)的活動(dòng)ai，即為關(guān)鍵活動(dòng)。

修改后的拓?fù)渑判蛩惴╥nt

ve[MAX_VERTEX_NUM];/*每個(gè)頂點(diǎn)的最早發(fā)生時(shí)間*/int

TopoOrder(AdjList

G,Stack*T)/*G為有向網(wǎng)，T為返回拓?fù)湫蛄械臈?，S為存放入度為0的頂點(diǎn)的棧*/{int

count,i,j,k;ArcNode*p;int

indegree[MAX_VERTEX_NUM];/*各頂點(diǎn)入度數(shù)組*/StackS;

InitStack(T);InitStack(&S);/*初始化棧T,S*/

FindID(G,indegree);/*求各個(gè)頂點(diǎn)的入度*/

for(i=0;i<G.vexnum;i++)

if(indegree[i]==0) Push(&S,i);count=0;

for(i=0;i<G.vexnum;i++)

ve[i]=0;/*初始化最早發(fā)生時(shí)間*/while(!StackEmpty(S)){Pop(&S,&j);Push(T,j);count++;p=G.vertex[j].firstarc;while(p!=NULL) { k=p->adjvex;if(--indegree[k]==0)Push(&S,k);/*若頂點(diǎn)的入度減為0，則入棧*/

if(ve[j]+p->weight>ve[k])ve[k]=ve[j]+p->weight; p=p->nextarc; }/*while*/}/*while*/

if(count<G.vexnum)return(Error);elsereturn(Ok);}求關(guān)鍵路徑的實(shí)現(xiàn)算法int

CriticalPath(AdjListG){ArcNode*p;int

i,j,k,dut,ei,li;chartag;int

vl[MAX_VERTEX_NUM];/*每個(gè)頂點(diǎn)的最遲發(fā)生時(shí)間*/StackT;

if(!TopoOrder(G,&T))return(Error);

for(i=0;i<G.vexnum;i++)

vl[i]=ve[i];/*初始化頂點(diǎn)事件的最遲發(fā)生時(shí)間*/

while(!StackEmpty(T))/*按逆拓?fù)漤樞蚯蟾黜旤c(diǎn)的vl值*/ {Pop(&T,&j); p=G.vertex[j].firstarc; while(p!=NULL) {k=p->adjvex;dut=p->weight;

if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;p=p->nextarc; }/*while*/ }/*while*/

for(j=0;j<G.vexnum;j++)/*求ei,li和關(guān)鍵活動(dòng)*/ {p=G.vertex[j].firstarc;

while(p!=NULL) {k=p->Adjvex;dut=p->weight;

ei=ve[j];li=vl[k]-dut;tag=(ei==li)?'*':'';

printf("%c,%c,%d,%d,%d,%c\n",G.vertex[j].data,G.vertex[k].data,dut,ei,li,tag);/*輸出關(guān)鍵活動(dòng)*/ p=p->nextarc; }/*while*/ }/*for*/return(Ok);}/*CriticalPath*/該算法的時(shí)間復(fù)雜度為O(n+e)。用該算法求p179的圖7.24中AOE-網(wǎng)的關(guān)鍵路徑，結(jié)果如p181的圖7.25。7.6最短路徑求某一頂點(diǎn)到其它各頂點(diǎn)的最短路徑設(shè)有帶權(quán)的有向圖D=(V,{E})，D中的邊權(quán)為

W(e)。已知源點(diǎn)為v0，求v0到其它各頂點(diǎn)的最短路徑。

如p184的圖7.26所示的帶權(quán)有向圖，其源點(diǎn)v0到其它各頂點(diǎn)的最短路徑如p184的表7－3所示。用迪杰斯特拉（Dijkstra）求最短路徑算法基本思想是：按路徑長(zhǎng)度遞增的順序，逐個(gè)產(chǎn)生各最短路徑。

首先引進(jìn)輔助向量dist[]，它的每一個(gè)分量dist[i]表示已經(jīng)找到的且從開(kāi)始點(diǎn)v0到每一個(gè)終點(diǎn)vi的當(dāng)前最短路徑的長(zhǎng)度。它的初態(tài)為：如果從v0到vi有弧，則dist[i]為弧的權(quán)值；否則dist[i]為∞。其中，長(zhǎng)度為dist[j]=Min{dist[i]|vi∈V}

的路徑是從v0出發(fā)的長(zhǎng)度最短的一條最短路徑，此路徑為（v0，vj）。

當(dāng)我們按長(zhǎng)度遞增的順序來(lái)產(chǎn)生各個(gè)最短路徑時(shí)，設(shè)S為已經(jīng)求得的最短路徑的終點(diǎn)集合。我們可以證明：下一條最短路徑或者是?。╲0，vx），或者是中間經(jīng)過(guò)S中的某些頂點(diǎn)，而后到達(dá)vx的路徑。一般情況下，下一條長(zhǎng)度最短的最短路徑的長(zhǎng)度必是dist[j]=Min{dist[i]|vi∈V－S}其中，dist[i]或者是?。╲0，vi）上的權(quán)值，或者是dist[k]（vk∈S）和?。╲k，vi）上的權(quán)值之和。

我們將圖中的頂點(diǎn)分為兩組：S—已求出的最短路徑的終點(diǎn)集合(開(kāi)始為{v0})。V-S—尚未求出最短路徑的頂點(diǎn)集合(開(kāi)始為V－{v0}的全部結(jié)點(diǎn))。按最短路徑長(zhǎng)度的遞增順序逐個(gè)將第二組的頂點(diǎn)加入到第一組中。

迪杰斯特拉算法的主要步驟：（1）g為用鄰接矩陣表示的帶權(quán)圖。

S←—{v0}，dist[i]=g.arcs[v0][vi]；將v0到其余頂點(diǎn)的路徑長(zhǎng)度初始化為權(quán)值；

（2）選擇vk，使得dist[vk]=min(dist[i]|vi∈V－S)

vk為目前求得的下一條從v0出發(fā)的最短路徑的終點(diǎn)。（3）修改從v0出發(fā)到集合V－S上任一頂點(diǎn)vi的最短路徑的長(zhǎng)度。如果

dist[k]+g.arcs[k][i]<dist[i]則將dist[i]修改為：

dist[k]+g.arcs[k][i]（4)重復(fù)(2)、(3)n-1次，即可按最短路徑長(zhǎng)度的遞增順序，逐個(gè)求出v0到圖中其它每個(gè)頂點(diǎn)的最短路徑。求圖的最短路徑的迪杰斯特拉算法typedef

SeqList

VertexSet;ShortestPath_DJS(AdjMatrixg,intv0,WeightType

dist[MAX_VERTEX_NUM],VertexSet

path[MAX_VERTEX_NUM])/*path[i]中存放頂點(diǎn)i的當(dāng)前最短路徑。dist[i]中存放頂點(diǎn)i的當(dāng)前最短路徑長(zhǎng)度*/{VertexSets;/*s為已找到最短路徑的終點(diǎn)集合*/for(i=0;i<g.vexnum;i++)/*初始化dist[i]和path

[i]*/{InitList(&path[i]);dist[i]=g.arcs[v0][i];if(dist[i]<MAX){AddTail(&path[i],g.vexs[v0]);/*AddTail為表尾添加操作*/AddTail(&path[i],g.vexs[i]);}}

InitList(&s);AddTail(&s,g.vexs[v0]);