數(shù)據(jù)結(jié)構(gòu)-C語言描述（第三版）課件：圖

圖7.1圖的定義與基本術(shù)語7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4

圖的應(yīng)用7.5總結(jié)與提高

圖結(jié)構(gòu)與表結(jié)構(gòu)和樹結(jié)構(gòu)的不同表現(xiàn)在結(jié)點(diǎn)之間的關(guān)系上，線性表中結(jié)點(diǎn)之間的關(guān)系是一對一的；樹是按分層關(guān)系組織的結(jié)構(gòu)，樹結(jié)構(gòu)之間是一對多；對于圖結(jié)構(gòu)，圖中頂點(diǎn)之間的關(guān)系可以是多對多，即一頂點(diǎn)和其它頂點(diǎn)間的關(guān)系是任意的，可以有關(guān)也可以無關(guān)。因此，圖G

樹T

L，圖是一種比較復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)。

圖作為一種非線性結(jié)構(gòu)，被廣泛應(yīng)用于多個技術(shù)領(lǐng)域。在本章中，主要是應(yīng)用圖論的理論知識來討論如何在計算機(jī)上表示和處理圖，以及如何利用圖來解決一些實(shí)際問題。7.1圖的定義與基本術(shù)語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為一個集合，該集合中的所有元素具有相同的特性。V中的數(shù)據(jù)元素通常稱為頂點(diǎn)（vertex），VR是兩個頂點(diǎn)之間的關(guān)系的集合。P（x，y）表示x和y之間有特定的關(guān)聯(lián)屬性P。

弧：若<x，y>∈VR，則<x，y>表示從頂點(diǎn)x到頂點(diǎn)y的一條弧（arc），并稱x為弧尾（tail）或起始點(diǎn)，稱y為弧頭（head）或終端點(diǎn)。有向圖：若圖中的邊是有方向的，稱這樣的圖為有向圖。無向圖：若<x，y>∈VR，必有<y，x>∈VR，即VR是對稱關(guān)系，這時以無序?qū)Γ▁，y）來代替兩個有序?qū)?，表示x和y之間的一條邊（edge），此時的圖稱為無向圖。

例如：下圖G1是有向圖，G2是無向圖2134G12145G23

在圖中，我們可以將任一頂點(diǎn)看成是圖的第一個頂點(diǎn)，同理，對于任一頂點(diǎn)而言，它的鄰接點(diǎn)之間也不存在順序關(guān)系。為了操作的方便，我們需要將圖中的頂點(diǎn)按任意序列排列起來。頂點(diǎn)在這個人為的隨意排列中的位置序號稱為頂點(diǎn)在圖中的位置。

圖的基本操作和其它數(shù)據(jù)結(jié)構(gòu)一樣，也有創(chuàng)建、插入、刪除、查找等。圖的抽象類型定義：ADTGraph數(shù)據(jù)對象V：一個集合，該集合中的所有元素具有相同的特性。數(shù)據(jù)關(guān)系R：R={VR}VR={<x，y>∣P（x，y）∧（x，y∈V）}基本操作：（1）CreateGraph（G）操作前提：已知圖G不存在操作結(jié)果：創(chuàng)建圖G。（2）DestoryGraph（G）操作前提：已知圖G存在；操作結(jié)果：銷毀圖G。（3）LocateVertex（G，v）操作前提：已知圖G存在，頂點(diǎn)v值合法；操作結(jié)果：若頂點(diǎn)v在圖G中存在，則返回頂點(diǎn)v在圖G中的位置。若圖G中沒有頂點(diǎn)v，則函數(shù)返回值為“空”。（4）GetVertex（G，i）操作前提：已知圖G存在；操作結(jié)果：返回圖G中的第i個頂點(diǎn)的值。若i大于圖G中頂點(diǎn)數(shù)，則函數(shù)返回值為“空”。（5）FirstAdjVertex（G，v）操作前提：已知圖G存在，頂點(diǎn)v值合法；操作結(jié)果：返回圖G中頂點(diǎn)v的第一個鄰接點(diǎn)。若v無鄰接點(diǎn)或圖G中無頂點(diǎn)v，則函數(shù)值為“空”。（6）NextAdjVertex（G，v，w）操作前提：已知圖G存在，w是圖G中頂點(diǎn)v的某個鄰接點(diǎn)，操作結(jié)果：返回頂點(diǎn)v的下一個鄰接點(diǎn)（緊跟在w后面）。若w是v的最后一個鄰接點(diǎn)，則函數(shù)值為“空”。（7）InsertVertex（G，u）操作前提：已知圖G存在，u值合法；操作結(jié)果：在圖G中增加一個頂點(diǎn)u。（8）DeleteVertex（G，v）操作前提：已知圖G存在，v值合法；操作結(jié)果：刪除圖G的頂點(diǎn)v及與頂點(diǎn)v相關(guān)聯(lián)的弧。（9）InsertArc（G，v，w）操作前提：已知圖G存在，v值，w值合法；操作結(jié)果：在圖G中增加一條從頂點(diǎn)v到頂點(diǎn)w的弧。（10）DeleteArc（G，v，w）操作前提：已知圖G存在，v值，w值合法，存在弧(v,w)；操作結(jié)果：刪除圖G中從頂點(diǎn)v到頂點(diǎn)w的弧。（11）TraverseGraph（G）操作前提：已知圖G存在；操作結(jié)果：按照某種次序，對圖G的每個頂點(diǎn)訪問一次且僅訪問一次。7.1.2基本術(shù)語

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

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

V且E/

E，則稱圖G/為G的子圖。

圖G1和圖G2的子圖如圖7.2所示。AACACDCDAB（a）G1的子圖ABCEDEABCEDBA（b）G2的子圖

對于無向圖

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

鄰接點(diǎn)：度、入度和出度

對于無向圖而言，頂點(diǎn)v的度是指和v相關(guān)聯(lián)的邊的數(shù)目，記作TD（v）。

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

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

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

:

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

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

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

連通圖

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

連通分量：無向圖中的極大連通子圖稱為該無向圖的連通分量。

強(qiáng)連通圖：在有向圖G=（V，{A}）中，若對于每對頂點(diǎn)vi、vj∈V且vi≠vj，從vi到vj和vj到vi都有路徑，則稱該有向圖為強(qiáng)連通圖。強(qiáng)連通分量：有向圖的極大強(qiáng)連通子圖稱作有向圖的強(qiáng)連通分量。圖G1和圖G3的連通分量見p157的圖7.4所示(a)無向圖G3ABLCJFMDEIGHK(b)無向圖G3的三個連通分量BLCJFMIGHKDEABAC1D圖7.4圖G1和G3的連通分量示例(c)有向圖G1的兩個連通分量7.2圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)方法有：①鄰接矩陣表示法；②鄰接表；③鄰接多重表；④十字鏈表

鄰接矩陣表示法

圖的鄰接矩陣表示法（AdjacencyMatrix）也稱作數(shù)組表示法。它采用兩個數(shù)組來表示圖：一個是用于存儲頂點(diǎn)信息的一維數(shù)組，另一個是用于存儲圖中頂點(diǎn)之間關(guān)聯(lián)關(guān)系的二維數(shù)組，這個關(guān)聯(lián)關(guān)系數(shù)組被稱為鄰接矩陣。

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

A[i,j]=若<vi,vj>或（vi,vj)VR0反之G1和G2的鄰接矩陣A1=0 1 1 00 0 0 00 0 0 11 0 0 0A2=0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0若圖G是一個有n個頂點(diǎn)的網(wǎng)，則它的鄰接矩陣是具有如下性質(zhì)的n×n矩陣A：A[i,j]=Wij若<vi,vj>或（vi,vj)VR∞反之有向網(wǎng)及其鄰接矩陣6978254551V1V6V5V4V2V3v1 v2 v3 v4 v5 v6∞ 5 ∞ 7 ∞ ∞∞ ∞ 4 ∞ ∞ ∞8 ∞ ∞ ∞ ∞ 9∞ ∞ 5 ∞ ∞ 6∞ ∞ ∞ 5 ∞ ∞2 ∞ ∞ ∞ 1 ∞v1v2v3v4v5v6(a)有向網(wǎng)N(b)有向網(wǎng)N的鄰接矩陣鄰接矩陣表示法的C語言類型描述為：#defineMAX_VERTEX_NUM10/*最多頂點(diǎn)個數(shù)*/#defineINFINITY32768/*最多頂點(diǎn)個數(shù)*/typedefenum{DG,DN,UDG,UDN}GraphKind;/*圖的種類：DG表示有向圖,DN表示有向網(wǎng),UDG表示無向圖,UDN表示無向網(wǎng)*/typedefcharVertexData;/*假設(shè)頂點(diǎn)數(shù)據(jù)為字符型*/typedefstructArcNode{AdjTypeadj;/*對于無權(quán)圖，用1或0表示是否相鄰；對帶權(quán)圖，則為權(quán)值類型*/OtherInfoinfo;}ArcNode;typedefstruct{VertexDatavexs[MAX_VERTEX_NUM];/*頂點(diǎn)向量*/ArcNodearcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*鄰接矩陣*/intvexnum,arcnum;/*圖的頂點(diǎn)數(shù)和弧數(shù)*/GraphKindkind;/*圖的種類標(biāo)志*/}AdjMatrix;/*（AdjacencyMatrixGraph）*/

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

對于無向圖而言，其鄰接矩陣第i行元素之和就是圖中第i個頂點(diǎn)的度：TD(vi)=A[i,j]j=1n

對于有向圖而言，其鄰接矩陣第i行元素之和就是圖中第i個頂點(diǎn)的出度，第i列元素之和就是圖中第i個頂點(diǎn)的入度。

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

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

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

注意：稀疏圖不適于用鄰接矩陣來存儲，因?yàn)檫@樣會造成存儲空間的浪費(fèi)。用鄰接矩陣法創(chuàng)建有向網(wǎng)的算法如下：intLocateVertex(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);}intCreateDN(AdjMatrix*G)/*創(chuàng)建一個有向網(wǎng)*/{inti,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);/*輸入一條弧的兩個頂點(diǎn)及權(quán)值*/ i=LocateVex_M(G,v1); j=LocateVex_M(G,v2); G->arcs[i][j].adj=weight;/*建立弧*/ }return(Ok);}分析：該算法的時間復(fù)雜度為O（n2+e×n），其中O（n2）時間耗費(fèi)在對二維數(shù)組arcs的每個分量的arj域初始化賦值上。O（e×n）的時間耗費(fèi)在有向網(wǎng)中邊權(quán)的賦值上。

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

它的基本思想是只存有關(guān)聯(lián)的信息，對于圖中存在的邊信息則存儲，而對于不相鄰接的頂點(diǎn)則不保留信息。在鄰接表中，對圖中的每個頂點(diǎn)建立一個帶頭結(jié)點(diǎn)的邊鏈表，每個邊鏈表的頭結(jié)點(diǎn)又構(gòu)成一個表頭結(jié)點(diǎn)表。這樣，一個n個頂點(diǎn)的圖的鄰接表表示由表頭結(jié)點(diǎn)表與邊表兩部分構(gòu)成。（1）表頭結(jié)點(diǎn)表：由所有表頭結(jié)點(diǎn)以順序結(jié)構(gòu)（向量）的形式存儲，以便可以隨機(jī)訪問任一頂點(diǎn)的單鏈表。表頭結(jié)點(diǎn)有兩部分構(gòu)成，其中數(shù)據(jù)域（vexdata）用于存儲頂點(diǎn)的名或其它有關(guān)信息；鏈域（firstarc）用于指向鏈表中第一個頂點(diǎn)（即與頂點(diǎn)vi鄰接的第一個鄰接點(diǎn)）。表頭結(jié)點(diǎn)結(jié)構(gòu)為：vexdatafirstarc（2）邊表：由表示圖中頂點(diǎn)間鄰接關(guān)系的n個邊鏈表組成。它由三部分組成，其中鄰接點(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)為：圖例圖G1、G2的鄰接表表示法1234AB∧CD3∧24∧1∧（a）G1的鄰接表表示法1∧

2∧

2∧

341∧

2∧

45533ABECD12345（b）G2的鄰接表表示法鄰接表存儲結(jié)構(gòu)的形式化說明如下：#defineMAX_VERTEX_NUM10/*最多頂點(diǎn)個數(shù)*/typedefenum{DG,DN,UDG,UDN}GraphKind;/*圖的種類*/typedefstructArcNode{intadjvex;/*該弧指向頂點(diǎn)的位置*/structArcNode*nextarc;/*指向下一條弧的指針*/OtherInfoinfo;/*與該弧相關(guān)的信息*/}ArcNode;

typedefstructVertexNode{VertexDatadata;/*頂點(diǎn)數(shù)據(jù)*/ArcNode*firstarc;/*指向該頂點(diǎn)第一條弧的指針*/}VertexNode;

typedefstruct{VertexNodevertex[MAX_VERTEX_NUM];intvexnum,arcnum;/*圖的頂點(diǎn)數(shù)和弧數(shù)*/GraphKindkind;/*圖的種類標(biāo)志*/}AdjList;/*基于鄰接表的圖(AdjacencyListGraph)*/

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

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

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

圖G1的逆鄰接表表示法見p162的圖7.10十字鏈表

十字鏈表(OrthogonalList)是有向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。我們也可以把它看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來形成的一種鏈表。

有向圖中的每一條弧對應(yīng)十字鏈表中的一個弧結(jié)點(diǎn)，同時有向圖中的每個頂點(diǎn)在十字鏈表中對應(yīng)有一個結(jié)點(diǎn)，叫做頂點(diǎn)結(jié)點(diǎn)。

這兩類結(jié)點(diǎn)的結(jié)構(gòu)見圖所示。tailvexheadvexhlinktlinktailvex表示弧尾頂點(diǎn)在圖中的位置headvex表示弧頭頂點(diǎn)在圖中的位置hlink指向與此弧的弧頭相同的下一條弧tlink指向與此弧的弧尾相同的下一條?。╝）十字鏈表弧結(jié)點(diǎn)結(jié)構(gòu)示意datafirstinfirstoutdata域用于存儲與頂點(diǎn)有關(guān)的信息如頂點(diǎn)的名字等firstin域（鏈域）用于指向以該頂點(diǎn)作為弧頭的第一個弧頂點(diǎn)firstout域（鏈域）用于指向以該頂點(diǎn)作為弧尾的第一個弧頂點(diǎn)（b）十字鏈表頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)示意圖7.10圖的十字鏈表弧結(jié)點(diǎn)、頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)圖圖G1的十字鏈表表示12

∧

13∧

∧4

1

∧

∧

A

C

BD

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

voidCrtOrthList（OrthListg）/*從終端輸入n個頂點(diǎn)的信息和e條弧的信息，以建立一個有向圖的十字鏈表*/{scanf(“%d,%d”,&n,&e);/*鍵盤輸入圖的頂點(diǎn)個數(shù)和弧的個數(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為頭的弧，因此對于有向圖，若采用十字鏈表作為存儲結(jié)構(gòu)，則很容易求出頂點(diǎn)vi的度。

鄰接多重表

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

鄰接多重表是指將圖中關(guān)于一條邊的信息用一個結(jié)點(diǎn)來表示。鄰接多重表中的邊結(jié)點(diǎn)結(jié)構(gòu)和頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)markivexilinkjvexjlink標(biāo)志域：可用以標(biāo)記該條邊是否被搜索過ivex和jvex：為該邊依附的兩個頂點(diǎn)在圖中的位置ilink（鏈域）：用于指向下一條依附于頂點(diǎn)ivex的邊jlink（鏈域）：用于指向下一條依附于頂點(diǎn)jvex的邊（a）鄰接多重表中邊結(jié)點(diǎn)的結(jié)構(gòu)datafirstedgedata域用于存儲與頂點(diǎn)有關(guān)的信息，如頂點(diǎn)的名字firstdege域（鏈域）用于指向第一條依附于該頂點(diǎn)的邊（b）鄰接多重表中頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)圖7.12鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu)鄰接多重表的結(jié)構(gòu)類型說明如下：typedefstructEdgeNode{intmark,ivex,jvex;structEdgeNode*ilink,*jlink;}EdgeNode;typedefstruct{VertexDatadata;EdgeNode*firstedge;}VertexNode;typedefstruct{VertexNodevertex[MAX_VERTEX_NUM];intvexnum,arcnum;/*圖的頂點(diǎn)數(shù)和弧數(shù)*/GraphKindkind;/*圖的種類*/}AdjMultiList;/*基于圖的鄰接多重表表示法(AdjacencyMulti_list)*/圖G2的鄰接多重表見圖所示。ABDC121∧4∧323∧5∧3452∧E圖7.13無向圖的鄰接多重表表示7.4圖的遍歷圖的遍歷：從圖中的某個頂點(diǎn)出發(fā)，按某種方法對圖中的所有頂點(diǎn)訪問且僅訪問一次。

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

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

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

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

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

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

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

voidTraverseGraph(Graphg)/*對圖g進(jìn)行深度優(yōu)先搜索，Graph表示圖的一種存儲結(jié)構(gòu)，如數(shù)組表示法或鄰接表等*/{for(vi=0;vi<g.vexnum;vi++)visited[vi]=False;/*訪問標(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；/*訪問頂點(diǎn)v0，并置訪問標(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);/*找下一個鄰接點(diǎn)*/}}/*DepthFirstSearch*/

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

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

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

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

3）用非遞歸過程實(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的第一個鄰接點(diǎn)*/while(w!=-1){ if(!visited(w))Push(S,w);w=NextAdj(g,v,w);/*求v相對于w的下一個鄰接點(diǎn)*/}}}

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

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

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

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

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

廣度優(yōu)先搜索過程示例見p169的圖7.16所示。其中箭頭代表搜索方向，箭頭旁邊的數(shù)字代表搜索順序，A為起始頂點(diǎn)。ADGBEHCFI14657823訪問序列為：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的第一個鄰接點(diǎn)*/while(w!=-1){ if(!visited(w)){visit(w);visited[w]=True;EnterQueue(&Q,w);}

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

7.4圖的應(yīng)用7.4.1圖的連通性問題無向圖的連通分量

在對圖遍歷時，對于連通圖，無論是廣度優(yōu)先搜索還是深度優(yōu)先搜索，僅需要調(diào)用一次搜索過程，即從任一個頂點(diǎn)出發(fā)，便可以遍歷圖中的各個頂點(diǎn)。對于非連通圖，則需要多次調(diào)用搜索過程，而每次調(diào)用得到的頂點(diǎn)訪問序列恰為各連通分量中的頂點(diǎn)集。調(diào)用搜索過程的次數(shù)就是該圖連通分量的個數(shù)。

例如：一個非連通圖，按照它的鄰接表進(jìn)行深度優(yōu)先搜索遍歷，三次調(diào)用深度優(yōu)先搜索（DepthFirstSearch）過程得到的訪問頂點(diǎn)序列為：1，2，4，3，95，6，78，10因此有三個連通分量。如圖所示5ABECFDHGIJ236932419417510248FEGADBCIJH(a)無向圖G5(b)G5的鄰接表ADBCIFEGJH(c)無向圖G5的三個連通分量圖7.16圖及其連通分量最小生成樹在一個連通網(wǎng)的所有生成樹中，各邊的代價之和最小的那棵生成樹稱為該連通網(wǎng)的最小代價生成樹（MinimumCostSpanningTree），簡稱為最小生成樹。

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

用反證法來證明這個最小生成樹（MST）的性質(zhì)：

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

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

（2）在所有u∈U,v∈V-U的邊中選一條代價最小的邊（u0，v0）并入集合TE，同時將v0并入U；

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

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

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

closedge[v].lowcoast=Min({cost(u,v)|u∈U})普里姆算法可描述為：struct{VertexDataadjvex;intlowcost;}closedge[MAX_VERTEX_NUM];/*求最小生成樹時的輔助數(shù)組*/MiniSpanTree_Prim(AdjMatrixgn,VertexData

u)/*從頂點(diǎn)u出發(fā)，按普里姆算法構(gòu)造連通網(wǎng)gn的最小生成樹，并輸出生成樹的每條邊*/{k=LocateVertex(gn,u);closedge[k].lowcost=0;/*初始化，U={u}*/for(i=0;i<gn.vexnum;i++)if(i!=k)/*對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);/*輸出生成樹的當(dāng)前最小邊（u0,v0）*/closedge[k0].lowcost=0;/*將頂點(diǎn)v0納入U集合*/for(i=0;i<vexnum;i++)/*在頂點(diǎn)v0并入U之后，更新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)是一個連通網(wǎng)，由普里姆算法構(gòu)造最小生成樹的過程見圖7.18(b)~(f)所示。算法中各參量的變化見p173的表7－1。圖7.18普里姆算法構(gòu)造最小生成樹的過程iClosedge[i]012345UV-Uek0(u0,v0)adjvexlowcost0V16V11V15V1∞V1∞{V1}{V2,V3,V4,V5,V6}12(V1,V3)adjvexlowcost0V350V15V36V34{V1,V3}{V2,V4,V5,V6}25(V3,V6)adjvexlowcost0V350V62V360{V1,V3,V6}{V2,V4,V5}33(V6,V4)adjvexlowcost0V3500V360{V1,V3,V6,V4}{V2,V5}41(V3,V2)adjvexlowcost0000V230{V1,V3,V6,V4,V2}{V5}54(V2,V5)adjvexlowcost000000{V1,V3,V6,V4,V2,V5}{}表7-1普里姆算法各參量的變化2.克魯斯卡爾算法假設(shè)N=(V,{E})是連通網(wǎng)，將N中的邊按權(quán)值從小到大的順序排列；（1）將n個頂點(diǎn)看成n個集合；

（2）按權(quán)值由小到大的順序選擇邊，所選邊應(yīng)滿足兩個頂點(diǎn)不在同一個頂點(diǎn)集合內(nèi)，將該邊放到生成樹邊的集合中。同時將該邊的兩個頂點(diǎn)所在的頂點(diǎn)集合合并；（3）重復(fù)（2），直到所有的頂點(diǎn)都在同一個頂點(diǎn)集合內(nèi)。

克魯斯卡爾算法是逐步增加生成樹的邊，故稱為“加邊法”克魯斯卡爾算法的執(zhí)行過程。7.4.2有向無環(huán)圖的應(yīng)用拓?fù)渑判颍═opologicalSort）

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

如表7-2課程關(guān)系，用頂點(diǎn)表示課程，弧表示先決條件，則表7－2可用一個有向無環(huán)圖表示。見圖課程編號課程名稱先修課程C1高等數(shù)學(xué)無C2程序設(shè)計基礎(chǔ)無C3離散數(shù)學(xué)C1,C2C4數(shù)據(jù)結(jié)構(gòu)C2,C3C5算法語言C2C6編譯技術(shù)C4,C5C7操作系統(tǒng)C4,C9C8普通物理C1C9計算機(jī)原理C8C1C2C3C4C5C6C7C8C9圖7.21表示課程之間優(yōu)先關(guān)系的有向無環(huán)圖拓?fù)湫蛄校涸谟邢驁DG=（V，{E}）中，

V中頂點(diǎn)的線性序列（vi1,,vi1,,vi3,…，vin）稱為拓?fù)湫蛄?。此序列必須滿足：對序列中任意兩個頂點(diǎn)vi、vj，在G中有一條從vi到vj的路徑，則在序列中vi必排在vj之前。

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

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

若vi為vj的先行活動，vj為vk的先行活動，則vi必為vk的先行活動，即先行關(guān)系具有可傳遞性。

AOV-網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏摹?/p>

它的另一個拓?fù)湫蛄袨椋篊1,C2,C3,C8,C4,C5,C9,C7,C6。

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

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

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

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

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

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

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

拓?fù)渑判虻膶?shí)現(xiàn)算法intTopoSort(AdjListG){StackS;intindegree[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號頂點(diǎn)并計數(shù)*/p=G.vertexes[i].firstarc; while(p!=NULL) {k=p->adjvex;indegree[k]--;/*i號頂點(diǎn)的每個鄰接點(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,intindegree[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*/}圖7.22所示的AOV-網(wǎng)用拓?fù)渑判蛩惴ㄇ蟪龅耐負(fù)湫蛄袨椋簐6，v1，v3，v2，v4，v5。

算法的時間復(fù)雜度分析：

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

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

AOE-網(wǎng)用在工程計劃和管理中，人們最關(guān)心的是：

哪些活動是影響工程進(jìn)度的關(guān)鍵活動？

至少需要多長時間能完成整個工程？源點(diǎn)：存在唯一的、入度為零的頂點(diǎn)，叫源點(diǎn)。匯點(diǎn)：存在唯一的、出度為零的頂點(diǎn)，叫匯點(diǎn)。關(guān)鍵路徑：從源點(diǎn)到匯點(diǎn)的最長路徑的長度即為完成整個工程任務(wù)所需的時間，該路徑叫做關(guān)鍵路徑。關(guān)鍵活動：關(guān)鍵路徑上的活動叫做關(guān)鍵活動。

在AOE-網(wǎng)中的基本概念：如圖7.24所示的AOE-網(wǎng)。V0為源點(diǎn)，表示整個工程可以開始，v8為匯點(diǎn)，表示整個工程結(jié)束。410235678a1=6a2=4a3=5a5=1a6=2a9=4a4=1a10=2a11=4a8=7a7=9圖7.24AOE-網(wǎng)幾個重要的定義：

事件vi的最早發(fā)生時間ve(i)：從源點(diǎn)到頂點(diǎn)vi的最長路徑的長度，叫做事件vi的最早發(fā)生時間。求ve(i)時可從源點(diǎn)開始，按拓?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>對應(yīng)的活動的持續(xù)時間。

事件vi的最晚發(fā)生時間vl(i)：在保證匯點(diǎn)按其最早發(fā)生時間發(fā)生這一前提下，事件vi的最晚發(fā)生時間。在求出ve(i)的基礎(chǔ)上，可從匯點(diǎn)開始，按逆拓?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>對應(yīng)的活動的持續(xù)時間。

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

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

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

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

修改后的拓?fù)渑判蛩惴╥ntve[MAX_VERTEX_NUM];/*每個頂點(diǎn)的最早發(fā)生時間*/intTopoOrder(AdjListG,Stack*T)/*G為有向網(wǎng)，T為返回拓?fù)湫蛄械臈?，S為存放入度為0的頂點(diǎn)的棧*/{intcount,i,j,k;ArcNode*p;intindegree[MAX_VERTEX_NUM];/*各頂點(diǎn)入度數(shù)組*/StackS;InitStack(T);InitStack(&S);/*初始化棧T,S*/FindID(G,indegree);/*求各個頂點(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ā)生時間*/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)算法intCriticalPath(AdjListG){ArcNode*p;inti,j,k,dut,ei,li;chartag;intvl[MAX_VERTEX_NUM];/*每個頂點(diǎn)的最遲發(fā)生時間*/StackT;if(!TopoOrder(G,&T))return(Error);for(i=0;i<G.vexnum;i++) vl[i]=ve[i];/*初始化頂點(diǎn)事件的最遲發(fā)生時間*/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)鍵活動*/ {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)鍵活動*/ p=p->nextarc; }/*while*/ }/*for*/return(Ok);}/*CriticalPath*/該算法的時間復(fù)雜度為O(n+e)。用該算法求圖7.24中AOE-網(wǎng)的關(guān)鍵路徑，結(jié)果如圖7.25。014867a1a7a8a11a10a4圖7.25關(guān)鍵路徑7.4.3最短路徑問題求某一頂點(diǎn)到其它各頂點(diǎn)的最短路徑設(shè)有帶權(quán)的有向圖D=(V,{E})，D中的邊權(quán)為

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

如圖7.26所示的帶權(quán)有向圖，其源點(diǎn)v0到其它各頂點(diǎn)的最短路徑如表7－3所示。0V4V2V3V545153531520源點(diǎn)終點(diǎn)最短路徑路徑長度V0V2V0，V210V3V0，V2，V325V1V0，V2，V3，V145V4V0，V445V5無最短路徑圖7.26一個帶權(quán)有向圖表7.3v0到其他頂點(diǎn)的最短路徑用迪杰斯特拉（Dijkstra）求最短路徑算法對于圖G=(V,E)，將圖中的頂點(diǎn)分成兩組：第一組S：已求出的最短路徑的終點(diǎn)集合（開始為{v0}）。第二組V－S：尚未求出最短路徑的頂點(diǎn)集合（開始為V－{v0}的全部結(jié)點(diǎn)）。算法將按最短路徑長度的遞增順序逐個將第二組的頂點(diǎn)加入到第一組中，直到所有頂點(diǎn)都被加入到第一組頂點(diǎn)集S為止。[定理]：下一條最短路徑或者是?。╲0，vx），或者是中間經(jīng)過S中的某些頂點(diǎn)，而后到達(dá)vx的路徑。[證明]：可用反證法：假設(shè)下一條最短路徑上有一個頂點(diǎn)vy不在S中，即此路徑為（v0，…，vy，…，vx）。顯然，（v0，…，vy）的長度小于（v0，…，vy，…，vx）的長度，故下一條最短路徑應(yīng)為（v0，…，vy），這與假設(shè)的下一條最短路徑（v0，…，vy，…，vx）相矛盾！因此，下一條最短路徑上不可能有不在S中的頂點(diǎn)vy，即假設(shè)不成立。算法中使用了輔助數(shù)組dist[]，dist[i]表示目前已經(jīng)找到的、從開始點(diǎn)v0到終點(diǎn)vi的當(dāng)前最短路徑的長度。它的初值為：如果從v0到vi有弧，則dist[i]為弧的權(quán)值；否則dist[i]為∞。根據(jù)上述定理，長度最短的一條最短路徑必為(v0,vk)，vk滿足如下條件：dist[k]=Min{dist[i]|vi∈V-S}求得頂點(diǎn)vk的最短路徑后，將vk加入到第一組頂點(diǎn)集S中。每加入一個新的頂點(diǎn)vk到頂點(diǎn)集S，則對第二組剩余的各個頂點(diǎn)而言，多了一個“中轉(zhuǎn)”結(jié)點(diǎn)，從而多了一個“中轉(zhuǎn)”路徑，所以要對第二組剩余的各個頂點(diǎn)的最短路徑長度dist[i]進(jìn)行修正。原來v0到vi的最短路徑長度為dist[i]，加進(jìn)vk之后，以vk作為中間頂點(diǎn)的“中轉(zhuǎn)”路徑長度為：dist[k]+wki，（wki為弧<vk,vi>上的權(quán)值），若“中轉(zhuǎn)”路徑長度小于dist[i]，則將頂點(diǎn)vi的最短路徑長度修正為“中轉(zhuǎn)”路徑長度。修正后，再選擇數(shù)組dist[]中值最小的頂點(diǎn)加入到第一組頂點(diǎn)集S中，如此進(jìn)行下去，直到圖中所有頂點(diǎn)都加入到第一組頂點(diǎn)集S中為止。另外，為了記錄從v0出發(fā)到其余各點(diǎn)的最短路徑（頂點(diǎn)序列），引進(jìn)輔助數(shù)組path[]，path[i]表示目前已經(jīng)找到的、從開始點(diǎn)v0到終點(diǎn)vi的當(dāng)前最短路徑頂點(diǎn)序列。它的初值為：如果從v0到vi有弧，則path[i]為（v0,vi）；否則path[i]為空。求圖的最短路徑的迪杰斯特拉算法typedefSeqListVertexSet;ShortestPath_DJS(AdjMatrixg,intv0,WeightTypedist[MAX_VERTEX_NUM],VertexSetpath[MAX_VERTEX_NUM])/*path[i]中存放頂點(diǎn)i的當(dāng)前最短路徑。dist[i]中存放頂點(diǎn)i的當(dā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]);/*將v0看成第一個已找到最短路徑的終點(diǎn)*/for(t=1;t<=g.vexnum-1;t++)/*求v0到其余n-1個頂點(diǎn)的最短路徑(n=g.vexnum)*/{min=MAX;for(i=0;i<g.vexnum;i++)if(!Member(g.vex[i],s)&&dist[i]<min){k=i;min=dist[i];}AddTail(&s,g.vexs[k]);for(i=0;i<g.vexnum;i++)/*修正dist[i],i∈V-S*/if(!Member(g.vex[i],s)&&(dist[k]+g.arcs[k][i]<dist[i])){dist[i]=dist[k]+g