《數(shù)據(jù)結(jié)構(gòu)-C語(yǔ)言描述》課件第10章

第10章圖10.1圖的基本概念10.2圖的存儲(chǔ)結(jié)構(gòu)10.3圖的遍歷10.4拓?fù)渑判蚝完P(guān)鍵路徑10.5最小代價(jià)生成樹(shù)10.6*最短路徑習(xí)題1010.1圖的基本概念10.1.1圖的定義與術(shù)語(yǔ)圖(graph)是數(shù)據(jù)結(jié)構(gòu)G=(V，E)，其中V(G)是G中結(jié)點(diǎn)的有限非空集合，結(jié)點(diǎn)的偶對(duì)稱(chēng)為邊(edge)，E(G)是G中邊的有限集合。圖中的結(jié)點(diǎn)常稱(chēng)為頂點(diǎn)(vertices)。若圖中代表一條邊的偶對(duì)是有序的，則稱(chēng)其為有向圖(directedgraph)。用〈v1,v2〉代表有向圖中的一條有向邊，v1稱(chēng)為邊的始點(diǎn)(尾tail)，v2稱(chēng)為邊的終點(diǎn)(頭head)。〈v1,v2〉和〈v2,v1〉這兩個(gè)偶對(duì)代表不同的邊。有向邊也稱(chēng)為弧(arc)。圖10－2圖的示例

(a)無(wú)向圖G1；(b)有向圖G2

若圖中代表一條邊的偶對(duì)是無(wú)序的，則稱(chēng)其為無(wú)向圖(undirectedgraph)。用(v1,v2)代表無(wú)向圖中的邊，這時(shí)(v1,v2)和(v2,v1)是同一條邊。事實(shí)上，對(duì)任何一個(gè)有向圖，若〈u,v〉

E，必有〈v,u〉

E，即E是對(duì)稱(chēng)的，則可以用一個(gè)無(wú)序?qū)?u,v)代替這兩個(gè)有序?qū)?，表示u和v之間的一條邊，便成為無(wú)向圖。圖10－2中的G1是無(wú)向圖，G2是有向圖。圖中：

V(G1)=V(G2)={v0,v1,v2,v3,v4}E(G1)={(v0,v1),(v0,v2),(v0,v4),(v1,v2),(v2,v3),(v2,v4),(v3,v4)}E(G2)={<v0,v1>,<v1,v2>,<v2,v0>,<v2,v4>,<v3,v0>,<v3,v2>,<v3,v4>}

如果邊(vi,vi)或<vi,vi>是允許的，這樣的邊稱(chēng)為自回路(selfloop)，如圖10－3(a)所示。兩頂點(diǎn)間允許有多條相同邊的圖，稱(chēng)為多重圖(multigraph)，如圖10－3(b)所示。在我們以后的討論中，不允許存在自回路和多重圖。圖10－3自回路和多重圖示例(a)自回路；(b)多重圖圖10－4完全圖示例

如果一個(gè)圖有最多的邊數(shù)，稱(chēng)為完全圖(completegraph)。無(wú)向完全圖有n(n－1)/2條邊；有向完全圖有n(n－1)條邊。圖10－4是一個(gè)無(wú)向完全圖。若(v1,v2)是無(wú)向圖的一條邊，則稱(chēng)頂點(diǎn)v1和v2相鄰接(adjacent)；若〈v1,v2〉是有向圖的一條邊，則稱(chēng)頂點(diǎn)v1鄰接到(adjacentto)頂點(diǎn)v2,頂點(diǎn)v2鄰接自(adjacentfrom)v1，并稱(chēng)邊(v1,v2)或〈v1,v2〉與頂點(diǎn)v1

和v2相關(guān)聯(lián)(incident)。圖10－2(a)的圖G1中，v1

和v2相鄰接。圖10－2(b)的圖G2中，v1鄰接到v2，v2鄰接自v1，與頂點(diǎn)v2相關(guān)聯(lián)的弧有〈v1,v2〉、〈v2,v0〉、〈v2,v4〉和〈v3,v2〉。

圖G的一個(gè)子圖(subgraph)是一個(gè)圖G'=(V',E')，使得V'(G')

V(G),E'(G')

E(G)。圖10－5(a)和(b)各給出了圖10－2所示的圖G1和G2的一個(gè)子圖。在無(wú)向圖G中，一條從vp到vq的路徑(path)是一個(gè)頂點(diǎn)的序列：vp,v1,v2,…,vn,vq，使得(vp,v1),(v1,v2),…,(vn,vq)是圖G的邊。若圖G是有向圖，則該路徑使得〈vp,v1〉，〈v1,v2〉，…，〈vn,vq〉是圖G的邊。路徑上邊的數(shù)目稱(chēng)為路徑長(zhǎng)度(pathlength)。圖10－5圖10－2所示的圖的子圖

(a)圖G1的子圖；(b)圖G2的子圖；(c)圖G1的生成樹(shù)

如果一條路徑上的所有結(jié)點(diǎn)，除起始頂點(diǎn)和終止頂點(diǎn)可以相同外，其余頂點(diǎn)各不相同，則稱(chēng)其為簡(jiǎn)單路徑(simplepath)。一個(gè)回路(cycle)是一條簡(jiǎn)單路徑，其起始頂點(diǎn)和終止頂點(diǎn)相同。我們用結(jié)點(diǎn)序列來(lái)表示路徑。圖10－2的圖G1中，v0,v1,v2,v4是一條簡(jiǎn)單路徑,其長(zhǎng)度為3。v0,v1,v2,v4,v0是一條回路，v0,v1,v2,v0,v4是一條路徑，但不是簡(jiǎn)單路徑。

一個(gè)無(wú)向圖中，若兩個(gè)頂點(diǎn)v0和v1間存在一條從v0到v1的路徑，則稱(chēng)v0和v1是連通的。若圖中任意一對(duì)頂點(diǎn)都是連通的，則稱(chēng)此圖是連通圖(connectedgraph)。一個(gè)有向圖中，若任意一對(duì)頂點(diǎn)v0和v1間存在一條從v0到v1的路徑和一條從v1到v0的路徑，則稱(chēng)此圖是強(qiáng)連通圖(stronglyconnectedgraph)。圖10－2的圖G1是連通圖，圖G2不是強(qiáng)連通圖。無(wú)向圖的一個(gè)極大連通子圖稱(chēng)為該圖的一個(gè)連通分量(connectedcomponent)。有向圖的一個(gè)極大強(qiáng)連通子圖稱(chēng)為該圖的一個(gè)強(qiáng)連通分量(stronglyconnectedcomponent)。見(jiàn)圖10－6的例子。圖10－6圖的強(qiáng)連通分量(a)圖G3；(b)圖G3的兩個(gè)強(qiáng)連通分量

圖中一個(gè)頂點(diǎn)的度(degree)是與該頂點(diǎn)相關(guān)聯(lián)的邊的數(shù)目。有向圖的頂點(diǎn)v的入度(in-degree)是以v為頭的邊的數(shù)目，頂點(diǎn)v的出度(out-degree)是以v為尾的邊的數(shù)目。圖10－6(a)中，頂點(diǎn)0的度為4，入度為3，出度為1。

一個(gè)無(wú)向連通圖的生成樹(shù)(spanningtree)是一個(gè)極小連通子圖，它包括圖中全部頂點(diǎn)，但只有足以構(gòu)成一棵樹(shù)的n－1條邊(見(jiàn)圖10－5(c))。有向圖的生成森林是這樣的一個(gè)子圖，它由若干棵互不相交的有根有向樹(shù)組成，這些樹(shù)包含了圖中全部頂點(diǎn)。有根有向樹(shù)是一個(gè)有向圖，它恰有一個(gè)頂點(diǎn)入度為0，其余頂點(diǎn)的入度為1，并且如果略去此圖中邊的方向，處理成無(wú)向圖后，圖是連通的。不包含回路的有向圖稱(chēng)為有向無(wú)環(huán)圖(directedacyclicgraphDAG)。一棵自由樹(shù)(freetree)是不包含回路的連通圖。

最后我們來(lái)看工程上經(jīng)常使用的網(wǎng)的概念。在圖的每條邊上加上一個(gè)數(shù)字作權(quán)(weight)，也稱(chēng)為代價(jià)(cost)，帶權(quán)的圖稱(chēng)為網(wǎng)(weightedgraphornetwork)。圖10－4所示的完全圖也是一個(gè)網(wǎng)。10.1.2圖ADT

現(xiàn)在我們用抽象數(shù)據(jù)類(lèi)型(見(jiàn)ADT10－1)定義帶權(quán)有向圖。如果將一個(gè)無(wú)向圖的每條邊(u，v)都看成是兩條有向邊<u,v>和<v,u>，則該無(wú)向圖變成有向圖。ADT10－1Graph{數(shù)據(jù)：頂點(diǎn)的非空集合V和邊的集合E，每條邊由V中頂點(diǎn)的偶對(duì)<u,v>表示。運(yùn)算：

voidCreateGraph(Graph*g,intn,Tnoedge)

后置條件:已構(gòu)造一個(gè)只有n個(gè)結(jié)點(diǎn)，不包含任何邊的有向圖。

BOOLAdd(Graph*g,intu,intv,Tw)

后置條件:向圖中添加權(quán)值為w(若邊上沒(méi)有權(quán)，則w＝0)的邊<u，v>，若插入成功，則函數(shù)返回TRUE，否則返回FALSE。BOOLDelete(Graph*g,intu,intv)

后置條件：從圖中刪除邊<u，v>，若刪除成功，則函數(shù)返回TRUE，否則返回FALSE。

BOOLExist(Graphg,intu,intv)

后置條件：如果圖中存在邊<u，v>，則函數(shù)返回TRUE，否則返回FALSE。

intVerticesGraphg)

后置條件：函數(shù)返回圖中頂點(diǎn)數(shù)目。}

上面列出的只是圖的最基本的運(yùn)算。在以后的各小節(jié)中，我們將通過(guò)添加新運(yùn)算，陸續(xù)擴(kuò)充ADT10－1的圖抽象數(shù)據(jù)類(lèi)型。主要包括以下圖運(yùn)算：

(1)深度優(yōu)先搜索圖：voidDFS(Graphg)；

(2)寬度優(yōu)先搜索圖：voidBFS(Graphg)；

(3)拓?fù)渑判颍簐oidTopoSort(Graphg)；

(4)關(guān)鍵路徑：voidCriticalPath(Graphg)；

(5)普里姆算法求最小代價(jià)生成樹(shù)：voidPrim(Graphg，intk)；(6)克魯斯卡爾算法求最小代價(jià)生成樹(shù)：voidKruskal(Graphg，intedges)；

(7)迪杰斯特拉算法求單源最短路徑：voidDijkstra(Graphg，intk,Td[],intp[])；

(8)弗洛伊德算法求所有頂點(diǎn)之間的最短路徑：voidFloyd(Graphg，T**&d,int**&path)。10.2圖的存儲(chǔ)結(jié)構(gòu)10.2.1矩陣表示法

1.鄰接矩陣鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。一個(gè)有n個(gè)頂點(diǎn)的圖G=(V,E)的鄰接矩陣(adjacencymatrix)是一個(gè)n?

?n的矩陣A，A中每一個(gè)元素是0或1。鄰接矩陣表示一個(gè)圖中頂點(diǎn)間的相鄰接的關(guān)系。如果G是無(wú)向圖，那么A中的元素定義如下：如果G是有向圖，那么A中的元素定義如下：如果G是帶權(quán)的有向圖(網(wǎng))，那么A中的元素定義如下：其中，w(u,v)是邊<u,v>的權(quán)值。

圖10－7給出了圖的鄰接矩陣表示的例子。圖10－7(d)是(a)的無(wú)向圖G1的鄰接矩陣，它是對(duì)稱(chēng)矩陣，這是因?yàn)橐粭l無(wú)向邊被認(rèn)為是兩條有向邊。圖10－7(f)是(c)的網(wǎng)G3的鄰接矩陣，主對(duì)角線為0，若<u,v>是圖中的邊，則A(u,v)為邊<u,v>上的權(quán)值，否則A(u,v)為。圖10－7鄰接矩陣示例(a)無(wú)向圖G1；(b)有向圖G2；(c)網(wǎng)G3；(d)G1的鄰接矩陣；(e)G2的鄰接矩陣；(f)G3的鄰接矩陣

2.關(guān)聯(lián)矩陣前面提到，圖在工程技術(shù)中應(yīng)用十分廣泛。例如，在電路CAD中的關(guān)聯(lián)矩陣(incidencematrix)便是圖的另一種表示方法。對(duì)圖10－1的電路，根據(jù)克希霍夫定律，列出結(jié)點(diǎn)的電流方程為寫(xiě)成矩陣形式為：

上式左邊的矩陣是圖的關(guān)聯(lián)矩陣A，右邊向量稱(chēng)為支路電流向量Ib，這樣克?；舴螂娏鞫煽蓪?xiě)成矩陣表示式A·Ib=0。

事實(shí)上，對(duì)于一個(gè)圖，除了可用鄰接矩陣表示外，還對(duì)應(yīng)著一個(gè)圖的關(guān)聯(lián)矩陣。關(guān)聯(lián)矩陣是表示圖中邊與頂點(diǎn)相關(guān)聯(lián)的矩陣。有向圖G=(V，E)的關(guān)聯(lián)矩陣是如下定義的n

m階矩陣：

從上面的討論中我們看到，一個(gè)圖可以用矩陣表示，那么在計(jì)算機(jī)中就可以按照矩陣的存儲(chǔ)方式來(lái)存儲(chǔ)圖，其中最常見(jiàn)的是用二維數(shù)組存儲(chǔ)。圖的結(jié)構(gòu)復(fù)雜，使用廣泛，所以存儲(chǔ)表示方法也是多種多樣的。對(duì)于不同的應(yīng)用，往往有不同的存儲(chǔ)方法。

3.鄰接矩陣的C語(yǔ)言定義下面我們給出用鄰接矩陣作為存儲(chǔ)表示的圖的C語(yǔ)言類(lèi)型定義。圖被定義成結(jié)構(gòu)類(lèi)型Graph。Vertices為圖中的頂點(diǎn)數(shù)。A是指向存儲(chǔ)鄰接矩陣的二維數(shù)組的指針，即它是一個(gè)指向類(lèi)型為T(mén)的元素的指針的指針。鄰接矩陣有兩種：圖和網(wǎng)的鄰接矩陣。圖的鄰接矩陣的元素為0或1，而網(wǎng)的鄰接矩陣中包含0、和邊上的權(quán)值，權(quán)值的類(lèi)型T可為整型、實(shí)型等，見(jiàn)圖10－7(f)。兩種鄰接矩陣中，主對(duì)角線元素總是0。令A(yù)[i][j]＝w，若邊<u,v>E，則w＝1(圖)或w＝邊上的權(quán)(網(wǎng))。若邊<u,v>E，則w＝0(圖)或w＝

(網(wǎng))。所以，在類(lèi)型Graph中，NoEdge的值對(duì)圖和網(wǎng)是不同的。若有向圖不帶權(quán)，則NoEdge＝0，否則NoEdge＝。typedefstructgraph{ TNoEdge; intVertices; T**A;}Graph;

4．建立鄰接矩陣函數(shù)CreateGraph構(gòu)造一個(gè)有n個(gè)頂點(diǎn)，但不包含邊的有向圖，一個(gè)無(wú)向圖的一條邊可以看成兩條有向邊。由于圖的頂點(diǎn)數(shù)事先并不知道，所以我們使用動(dòng)態(tài)存儲(chǔ)分配的二維數(shù)組。程序10－1的構(gòu)造函數(shù)CreateGraph完成對(duì)二維數(shù)組A的動(dòng)態(tài)存儲(chǔ)分配。其中，變量NoEdge用于表示A[i][j]處沒(méi)有邊時(shí)的值。對(duì)于不帶權(quán)的圖，NoEdge為0；對(duì)于網(wǎng)，A[i][i]=0.【程序10－1】建立鄰接矩陣。

voidCreateGraph(Graph*g,intn,Tnoedge){ inti,j; g->NoEdge=noedge; g->Vertices=n; g->A=(T**)malloc(n*sizeof(T*)); for(i=0;i<n;i++){ g->A[i]=(T*)malloc(n*sizeof(T)); for(j=0;j<n;j++) g->A[i][j]=noedge; g->A[i][i]=0; }}

5．邊的插入、刪除和搜索程序10－2實(shí)現(xiàn)圖的邊的插入、刪除和搜索運(yùn)算。

(1)Add函數(shù)：當(dāng)u<0或v<0或u>n－1或v>n－1或u==v時(shí)，表示輸入?yún)?shù)u和v無(wú)效，而g->A[u][v]!=g->NoEdge，則表示邊<u，v>已經(jīng)存在，不能再重復(fù)輸入。如果不屬于上述情況，則在鄰接矩陣中添加邊<u,v>，具體做法是：令g->A[u][v]=w;，其中，對(duì)帶權(quán)的圖，w的值是邊<u,v>的權(quán)值，對(duì)一般的有向圖，有w=1。(2)Delete函數(shù):當(dāng)輸入?yún)?shù)u和v無(wú)效，或當(dāng)g->A[u][v]==g->NoEdge時(shí)，不能執(zhí)行刪除運(yùn)算，否則從鄰接矩陣中刪除邊<u,v>，即令g->A[u][v]=g->NoEdge。

(3)Exist函數(shù)：當(dāng)輸入?yún)?shù)u和v無(wú)效，或當(dāng)g->A[u][v]==g->NoEdge時(shí)，表示不存在邊<u,v>，函數(shù)返回FALSE，否則函數(shù)返回TRUE?！境绦?0－2】邊的插入、刪除和搜索。

BOOLAdd(Graph*g,intu,intv,Tw){ intn=g->Vertices; if(u<0||v<0||u>n-1||v>n-1||u==v||g->A[u][v]!=g->NoEdge){ printf("BadInput\n");returnFALSE; } g->A[u][v]=w;returnTRUE;}BOOLDelete(Graph*g,intu,intv){ intn=g->Vertices; if(u<0||v<0||u>n-1||v>n-1||u==v||g->A[u][v]==g->NoEdge){ printf("BadInput\n");returnFALSE; } g->A[u][v]=g->NoEdge;returnTRUE;}BOOLExist(Graphg,intu,intv){ intn; n=g.Vertices; if(u<0||v<0||u>n-1||v>n-1||u==v||g.A[u][v]==g.NoEdge) returnFALSE; returnTRUE;}10.2.2鄰接表表示法

1．鄰接表鄰接表是圖的另一種有效的存儲(chǔ)表示方法。鄰接表為圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表。頂點(diǎn)u的單鏈表中的每個(gè)結(jié)點(diǎn)指示u的一個(gè)鄰接點(diǎn)v，它代表一條邊<u,v>，所以稱(chēng)為邊結(jié)點(diǎn)。這樣，頂點(diǎn)u的單鏈表記錄了與u相鄰接(或鄰接自u(píng))的所有頂點(diǎn)。實(shí)際上，每個(gè)單鏈表相當(dāng)于鄰接矩陣的一行，它指示了該行中的非零的元素。邊結(jié)點(diǎn)通常有圖10－8(a)所示的格式。其中，AdjVex域指示頂點(diǎn)u的一個(gè)鄰接點(diǎn)，NextArc指向u的下一個(gè)邊結(jié)點(diǎn)。如果是網(wǎng)，則增加一個(gè)W域存儲(chǔ)邊上的權(quán)值，見(jiàn)圖10－8(b)。每個(gè)單鏈表可設(shè)立一個(gè)存放頂點(diǎn)u的有關(guān)信息的表頭結(jié)點(diǎn)，也稱(chēng)頂點(diǎn)結(jié)點(diǎn)，其結(jié)構(gòu)見(jiàn)圖10－8(c)。其中，Element域存放頂點(diǎn)的名稱(chēng)及其他信息，F(xiàn)irstArc指向u的第一個(gè)邊結(jié)點(diǎn)。我們可以將頂點(diǎn)結(jié)點(diǎn)按順序存儲(chǔ)方式組織起來(lái)，例如，圖10－8(d)是圖10－7(b)中圖G2的鄰接表表示。

在圖結(jié)構(gòu)中，我們習(xí)慣用編號(hào)來(lái)標(biāo)識(shí)頂點(diǎn)。為了簡(jiǎn)單起見(jiàn)，我們常省去保存頂點(diǎn)信息的Element域，圖10－8(e)是圖10－7(a)的無(wú)向圖G1的鄰接表表示。在無(wú)向圖的鄰接表中，一條邊對(duì)應(yīng)兩個(gè)邊結(jié)點(diǎn)。圖10－8(f)是圖10－7(c)的圖G1和G3的鄰接表表示。圖10－8鄰接表示例

(a)邊結(jié)點(diǎn)；(b)帶權(quán)的邊結(jié)點(diǎn)；(c)頂點(diǎn)結(jié)點(diǎn)；(d)圖G2的鄰接表表示；

(e)圖G1的鄰接表表示；(f)網(wǎng)G3的鄰接表表示

2.鄰接表的C語(yǔ)言定義下面我們給出用鄰接表作為存儲(chǔ)表示的圖的C語(yǔ)言類(lèi)型定義。邊結(jié)點(diǎn)的結(jié)構(gòu)類(lèi)型為ENode，每個(gè)結(jié)點(diǎn)有三個(gè)域AdjVex、W和NextArc。圖被定義成結(jié)構(gòu)類(lèi)型Graph。Vertices為圖中的頂點(diǎn)數(shù)。鄰接表的表頭組成如圖10－8(e)和(f)所示的一維指針數(shù)組，A是指向該數(shù)組的指針。typedefstructenode{ intAdjVex; TW; structenode*NextArc;}ENode;typedefstructgraph{ intVertices; ENode**A;}Graph;

3.建立鄰接表函數(shù)CreateGraph構(gòu)造一個(gè)有n個(gè)頂點(diǎn)，但不包含邊的有向圖。由于圖的頂點(diǎn)數(shù)事先并不知道，所以我們使用動(dòng)態(tài)存儲(chǔ)分配的一維指針數(shù)組。程序10－3的構(gòu)造函數(shù)完成對(duì)一維指針數(shù)組A的動(dòng)態(tài)存儲(chǔ)分配，并對(duì)其每個(gè)元素賦初值NULL?！境绦?0－3】建立鄰接表。voidCreateGraph(Graph*g,intn){inti;g->Vertices=n;g->A=(ENode**)malloc(n*sizeof(ENode*));for(i=0;i<n;i++)g->A[i]=NULL;}

4.邊的搜索、插入和刪除程序10－4實(shí)現(xiàn)對(duì)圖的邊的搜索、插入和刪除操作。這基本上是單鏈表上的操作。

(1)Exist函數(shù)：頂點(diǎn)u的單鏈表中的每個(gè)邊結(jié)點(diǎn)指示u的一個(gè)鄰接點(diǎn)v。表頭指針A[u]指向第一個(gè)邊結(jié)點(diǎn)。Exist函數(shù)從A[u]出發(fā)，在u的單鏈表中搜索AdjVex域?yàn)関的邊結(jié)點(diǎn)，若存在，則返回TRUE，否則返回FALSE。(2)Add函數(shù)：Add函數(shù)首先創(chuàng)建一個(gè)代表一條權(quán)為w的邊〈u,v〉的新邊結(jié)點(diǎn)，并將其插入鄰接表中由指針A[u]所指示的單鏈表的最前面。函數(shù)ENode*NewENode(intvex,Tweight,ENode*nextarc)構(gòu)造一個(gè)新的邊結(jié)點(diǎn)，該結(jié)點(diǎn)的NextArc域可以賦NULL值，如果需要也可以賦以后繼邊結(jié)點(diǎn)的地址。

(3)Delete函數(shù)：Delete函數(shù)先在鄰接表的由指針A[u]所指示的單鏈表中，搜索AdjVex域的值為v的邊結(jié)點(diǎn)，若存在這樣的結(jié)點(diǎn)，則刪除之。刪除操作與在單鏈表中刪除一個(gè)結(jié)點(diǎn)的操作相同?！境绦?0－4】搜索、插入和刪除函數(shù)。ENode*NewENode(intvex,Tweight,ENode*nextarc){ ENode*p; p=(ENode*)malloc(sizeof(ENode)); p->AdjVex=vex;p->W=weight; p->NextArc=nextarc; returnp;}BOOLExist(Graphg,intu,intv){ intn; ENode*p; n=g.Vertices; if(u<0||u>n-1)returnFALSE; for(p=g.A[u];p&&p->AdjVex!=v;)p=p->NextArc; if(!p)returnFALSE; returnTRUE;}BOOLAdd(Graph*g,intu,intv,Tw){ intn;ENode*p; n=g->Vertices; if(u<0||v<0||u>n-1||v>n-1||u==v||Exist(*g,u,v)){ printf("BadInput\n");returnFALSE; } p=NewENode(v,w,g->A[u]);g->A[u]=p; returnTRUE;}BOOLDelete(Graph*g,intu,intv){ intn=g->Vertices; ENode*p,*q; if(u>-1&&u<n){ p=g->A[u];q=NULL; while(p&&p->AdjVex!=v){ q=p;p=p->NextArc; } if(p){ if(q)q->NextArc=p->NextArc; elseg->A[u]=p->NextArc; free(p);returnTRUE; }}printf("BadInput\n");returnFALSE;}10.2.3*正交鏈表和多重表表示法當(dāng)用鄰接表表示無(wú)向圖(見(jiàn)圖10－8(e))時(shí)，每條邊以(u,v)和(v,u)的形式在鄰接表中出現(xiàn)兩次。在某些圖問(wèn)題的求解中，需要給被處理的邊加上標(biāo)記，以免重復(fù)處理。若采用鄰接表表示，需同時(shí)對(duì)鄰接表中代表同一條邊的兩個(gè)邊結(jié)點(diǎn)加標(biāo)記，而這兩處邊結(jié)點(diǎn)又不在同一個(gè)頂點(diǎn)單鏈表中，這給搜索帶來(lái)很大的不便。用鄰接多重表表示無(wú)向圖可簡(jiǎn)化上述問(wèn)題的處理。圖10-9有向圖的正交鏈表和無(wú)向圖的多重表表示2．無(wú)向圖的多重表表示法

鄰接多重表中，圖的每條邊用一個(gè)如圖10－9(a)所示的邊結(jié)點(diǎn)表示，它由五個(gè)域組成，其中：Mark是標(biāo)記域，標(biāo)記該邊是否被處理或搜索過(guò)；Vertex1和Vertex2是頂點(diǎn)域，指示該邊相關(guān)聯(lián)的兩個(gè)頂點(diǎn)；Path1是指針域，指示下一條與頂點(diǎn)Vertex1相關(guān)聯(lián)的邊；Path2是指針域，指示下一條與頂點(diǎn)Vertex2相關(guān)聯(lián)的邊。這樣便可從多重表的表頭開(kāi)始，搜索與某個(gè)頂點(diǎn)v相關(guān)聯(lián)的所有的邊，同時(shí)可查找v的所有的鄰接點(diǎn)。例如，圖10－9(d)所示的鄰接多重表中，與頂點(diǎn)1相關(guān)聯(lián)的邊可從頂點(diǎn)結(jié)點(diǎn)1出發(fā)，經(jīng)邊結(jié)點(diǎn)(0,1)的Path2，到達(dá)邊結(jié)點(diǎn)(1,2)，再經(jīng)該結(jié)點(diǎn)的Path1到達(dá)邊結(jié)點(diǎn)(1,3)，直至該結(jié)點(diǎn)的Path1為空指針為止?？偣灿腥龡l邊(0,1)、(1,2)和(1,3)。10.3圖的遍歷10.3.1深度優(yōu)先遍歷基于圖的結(jié)構(gòu)，以特定的順序依次訪問(wèn)圖中各頂點(diǎn)是很有用的圖運(yùn)算。給定一個(gè)圖和其中任意一個(gè)結(jié)點(diǎn)v，從v出發(fā)系統(tǒng)地訪問(wèn)圖G的所有的結(jié)點(diǎn)，且使每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次，這樣的過(guò)程叫做圖的遍歷(graphtraversal)。遍歷圖的算法常是實(shí)現(xiàn)圖的其他操作的基礎(chǔ)。和樹(shù)的遍歷相似，對(duì)于圖也有兩種遍歷的方法：深度優(yōu)先搜索(depthfirstsearch)和寬度優(yōu)先搜索(breadthfirstsearch)。圖的深度優(yōu)先搜索可以看成是樹(shù)的先序遍歷的推廣，而圖的寬度優(yōu)先搜索則類(lèi)似于樹(shù)的按層次遍歷。

但與樹(shù)遍歷算法不同的是，圖遍歷必須處理兩個(gè)棘手的情況。首先，從起點(diǎn)出發(fā)的搜索可能到達(dá)不了圖的所有其他頂點(diǎn)，對(duì)于一個(gè)非連通無(wú)向圖就會(huì)發(fā)生這種情況，這種現(xiàn)象對(duì)非強(qiáng)連通有向圖也可能出現(xiàn)。其次，圖可能存在回路，搜索算法應(yīng)當(dāng)不因此而陷入死循環(huán)。為了避免發(fā)生上述兩種情況，圖的搜索算法通常為圖的每個(gè)頂點(diǎn)保留一個(gè)標(biāo)志位(markbit)。算法開(kāi)始時(shí)，所有頂點(diǎn)的標(biāo)志位清零。在遍歷過(guò)程中，當(dāng)某個(gè)頂點(diǎn)被訪問(wèn)時(shí)，其標(biāo)志位被標(biāo)記。在搜索中遇到被標(biāo)記過(guò)的頂點(diǎn)則不再訪問(wèn)它。搜索結(jié)束后，如果還有未標(biāo)記過(guò)的頂點(diǎn)，遍歷算法可以選一個(gè)未標(biāo)記的頂點(diǎn)，從它出發(fā)開(kāi)始繼續(xù)搜索。

1．深度優(yōu)先搜索假定初始時(shí)，圖G的所有頂點(diǎn)都未被訪問(wèn)過(guò)，那么從圖中某個(gè)頂點(diǎn)v出發(fā)的深度優(yōu)先搜索圖的遞歸過(guò)程DFS可以描述為：

(1)訪問(wèn)頂點(diǎn)v，并對(duì)v打上已訪問(wèn)標(biāo)記；

(2)依次從v的未訪問(wèn)的鄰接點(diǎn)出發(fā)，深度優(yōu)先搜索圖G。

對(duì)圖10－10(a)的有向圖G，從頂點(diǎn)A出發(fā)調(diào)用DFS過(guò)程，頂點(diǎn)被訪問(wèn)的次序是：A，B，D，C。這里假定鄰接于B的頂點(diǎn)C和D的次序是先D后C，即從A出發(fā)，訪問(wèn)A，標(biāo)記A，然后選擇A的鄰接點(diǎn)B，深度優(yōu)先搜索訪問(wèn)B。B有兩個(gè)鄰接于它的頂點(diǎn)，假定先D后C，所以先深度優(yōu)先搜索訪問(wèn)D。D有兩個(gè)鄰接點(diǎn)，由于D的鄰接點(diǎn)A已標(biāo)記，所以深度優(yōu)先搜索訪問(wèn)C。這時(shí)，鄰接于C的頂點(diǎn)A已經(jīng)被標(biāo)記，所以返回D，這時(shí)D的所有鄰接點(diǎn)均已打上標(biāo)記，故返回B，再返回A。DFS結(jié)束。

上述過(guò)程僅遍歷了圖的一部分，類(lèi)似于森林的先序遍歷中遍歷了一棵樹(shù)。在無(wú)向圖的情況下，遍歷了一個(gè)連通分量，對(duì)有向圖，則遍歷了所有從A出發(fā)可到達(dá)的頂點(diǎn)，即A的可達(dá)集。如果是連通的無(wú)向圖或強(qiáng)連通的有向圖，上述DFS算法必定可以系統(tǒng)地訪問(wèn)圖中的全部頂點(diǎn)，不然，為了遍歷整個(gè)圖，還必須另選未標(biāo)記的頂點(diǎn)，再次調(diào)用DFS過(guò)程，這樣重復(fù)多次，直到全部頂點(diǎn)都已被標(biāo)記為止。上例中，可另選F，訪問(wèn)F，再選G，訪問(wèn)G，最后選E，訪問(wèn)E。圖中所有頂點(diǎn)，以及在遍歷時(shí)經(jīng)過(guò)的邊(即從已訪問(wèn)的頂點(diǎn)到達(dá)未訪問(wèn)頂點(diǎn)的邊)構(gòu)成的子圖，稱(chēng)為圖的深度優(yōu)先搜索生成樹(shù)(dfsspanningtree)(或生成森林)。

2.深度優(yōu)先搜索的遞歸算法程序10－5給出了實(shí)現(xiàn)深度優(yōu)先搜索的DFS遞歸函數(shù)，以及深度優(yōu)先遍歷的Traversal_DFS函數(shù)。后者調(diào)用前者完成對(duì)圖的深度優(yōu)先遍歷。若算法采用圖10－10(b)的鄰接表表示，則在該鄰接表上執(zhí)行DFS算法得到的深度優(yōu)先遍歷的生成森林見(jiàn)圖10－10(c)。【程序10－5】DFS遞歸算法。voidDFS(Graphg,intv,BOOL*visited){ENode*w;visited[v]=TRUE;printf("%d",v);for(w=g.A[v];w;w=w->NextArc)if(!visited[w->AdjVex])DFS(g,w->AdjVex,visited);}voidTraversal_DFS(Graphg){ BOOLvisited[MaxSize];inti,n=g.Vertices; for(i=0;i<n;i++)visited[i]=FALSE; for(i=0;i<n;i++) if(!visited[i])DFS(g,i,visited);}圖10－10圖的深度優(yōu)先搜索

(a)有向圖G；(b)圖G的鄰接表(∧代表NULL)；(c)圖G的深度優(yōu)先搜索的生成森林

深度優(yōu)先搜索圖的算法，每嵌套調(diào)用一次，實(shí)際上是查看頂點(diǎn)v的所有的鄰接點(diǎn)，或者說(shuō)查看頂點(diǎn)v的所有出邊，對(duì)其中未標(biāo)記的鄰接點(diǎn)嵌套調(diào)用DFS函數(shù)。因此DFS算法對(duì)有向圖的每條邊都恰好查看一次。對(duì)無(wú)向圖，一條無(wú)向邊被視作兩條有向邊，被查看兩次。此外，DFS算法中每個(gè)頂點(diǎn)僅被訪問(wèn)一次。設(shè)圖的頂點(diǎn)數(shù)為n，邊數(shù)為e，則遍歷圖算法的時(shí)間為O(n+e)。如果用鄰接矩陣表示圖，則所需時(shí)間為O(n2)。10.3.2寬度優(yōu)先遍歷

1.寬度優(yōu)先搜索假定初始時(shí)，圖G的所有頂點(diǎn)都未被訪問(wèn)過(guò)，那么從圖中某個(gè)頂點(diǎn)v出發(fā)的寬度優(yōu)先搜索圖的過(guò)程BFS可以描述為：訪問(wèn)頂點(diǎn)v，并對(duì)v打上已訪問(wèn)標(biāo)記，然后依次訪問(wèn)v的各個(gè)未訪問(wèn)過(guò)的鄰接點(diǎn)，接著再依次訪問(wèn)分別與這些鄰接點(diǎn)相鄰接且未訪問(wèn)過(guò)的頂點(diǎn)。對(duì)圖10－11(a)的無(wú)向圖G，從頂點(diǎn)0出發(fā)的寬度優(yōu)先搜索過(guò)程是：首先訪問(wèn)頂點(diǎn)0，然后訪問(wèn)與它相鄰接的頂點(diǎn)1，11，10，接著再依次訪問(wèn)這三個(gè)頂點(diǎn)的鄰接點(diǎn)中未訪問(wèn)的頂點(diǎn)2，5，6，9，…，得到的遍歷頂點(diǎn)的序列是：0，1，11，10，2，5，6，9，3，4，7，8。圖10－11圖的寬度優(yōu)先搜索(a)無(wú)向圖G；(b)圖G的寬度優(yōu)先搜索生成樹(shù)

寬度優(yōu)先搜索是按層次往外擴(kuò)展的遍歷方法。它需要一個(gè)隊(duì)列來(lái)記錄已經(jīng)被訪問(wèn)過(guò)但其鄰接點(diǎn)尚未考查的頂點(diǎn)。同樣上面描述的過(guò)程僅遍歷了圖的一部分。若此時(shí)圖中尚有未訪問(wèn)過(guò)的頂點(diǎn)，則必須另選一個(gè)未標(biāo)記的頂點(diǎn)作起點(diǎn)，重復(fù)上述過(guò)程，直到全部頂點(diǎn)都已被標(biāo)記為止。圖中所有頂點(diǎn)以及在遍歷時(shí)經(jīng)過(guò)的邊(即從已訪問(wèn)的頂點(diǎn)到達(dá)未訪問(wèn)頂點(diǎn)的邊)構(gòu)成的子圖稱(chēng)為圖的寬度優(yōu)先搜索生成森林(或生成樹(shù))。

2.寬度優(yōu)先搜索算法程序10－6給出了實(shí)現(xiàn)寬度優(yōu)先搜索的BFS函數(shù)以及寬度優(yōu)先遍歷的Traversal_BFS函數(shù)。后者調(diào)用前者完成對(duì)圖的寬度優(yōu)先遍歷。該算法需要?jiǎng)?chuàng)建一個(gè)隊(duì)列，作為輔助數(shù)據(jù)結(jié)構(gòu)。在遍歷中，對(duì)某個(gè)頂點(diǎn)v(它自身已訪問(wèn))，算法依次訪問(wèn)它的所有未訪問(wèn)過(guò)的鄰接點(diǎn)時(shí)，需將這些鄰接點(diǎn)保存在隊(duì)列中。當(dāng)頂點(diǎn)v的所有鄰接點(diǎn)全部訪問(wèn)完畢后，從隊(duì)列中取出一個(gè)頂點(diǎn)，接著訪問(wèn)這個(gè)頂點(diǎn)的鄰接點(diǎn)，并依次進(jìn)隊(duì)列。需使用語(yǔ)句#include"queue.h"將隊(duì)列數(shù)據(jù)結(jié)構(gòu)包含在內(nèi)。對(duì)圖10－11(a)的無(wú)向圖G執(zhí)行BFS，得到的寬度優(yōu)先遍歷的生成樹(shù)見(jiàn)圖10－11(b)?！境绦?0－6】BFS算法。#include"queue.h"voidBFS(Graphg,Tv,BOOL*visited){ENode*w;Tu;Queueq;CreateQueue(&q,MaxNumVertices);visited[v]=TRUE;printf("%d",v);Append(&q,v);while(!IsEmpty(q)){QueueFront(q,&u);Serve(&q);for(w=g.A[u];w;w=w->NextArc)if(!visited[w->AdjVex]){ printf("%d",w->AdjVex); visited[w->AdjVex]=TRUE; Append(&q,w->AdjVex);}}}voidTraversal_BFS(Graphg){ BOOLvisited[MaxSize];inti,n=g.Vertices; for(i=0;i<n;i++)visited[i]=FALSE; for(i=0;i<n;i++) if(!visited[i])BFS(g,i,visited);}

分析寬度優(yōu)先搜索圖的算法，可知每個(gè)頂點(diǎn)都進(jìn)隊(duì)列一次，而對(duì)于每個(gè)從隊(duì)列取走的頂點(diǎn)v都查看其所有的鄰接點(diǎn)，或者說(shuō)查看頂點(diǎn)v的所有出邊，因此BFS算法對(duì)無(wú)向圖的每條邊都恰好查看兩次。此外，BFS算法中每個(gè)頂點(diǎn)僅被訪問(wèn)一次。設(shè)圖的頂點(diǎn)數(shù)為n，邊數(shù)為e，則寬度優(yōu)先遍歷圖算法的時(shí)間為O(n+e)。如果用鄰接矩陣表示圖，則所需時(shí)間為O(n2)。10.4拓?fù)渑判蚝完P(guān)鍵路徑10.4.1拓?fù)渑判?/p>

1.用頂點(diǎn)代表活動(dòng)的網(wǎng)絡(luò)(AOV網(wǎng)絡(luò))

拓?fù)渑判?topologicalsort)是求解網(wǎng)絡(luò)問(wèn)題所需的主要算法。管理技術(shù)如計(jì)劃評(píng)審技術(shù)PERT(PerformanceEvaluationAndReviewTechnique)和關(guān)鍵路徑法CPM(CriticalPathMethod)都應(yīng)用這一算法。通常，軟件開(kāi)發(fā)、施工過(guò)程、生產(chǎn)流程、程序流程等都可作為一個(gè)工程。一個(gè)工程可分成若干子工程，子工程常稱(chēng)為活動(dòng)(activity)。因此要完成整個(gè)工程，必須完成所有的活動(dòng)?；顒?dòng)的執(zhí)行常常伴隨著某些先決條件，一些活動(dòng)必須先于另一些活動(dòng)被完成。例如一個(gè)計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生必須學(xué)習(xí)一系列課程，其中有些課程是基礎(chǔ)課，而另一些課程則必須在學(xué)完它們規(guī)定的先修課程之后才能開(kāi)始。如數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)必須有離散數(shù)學(xué)和高級(jí)程序設(shè)計(jì)語(yǔ)言的準(zhǔn)備知識(shí)。這些先決條件規(guī)定了課程之間的領(lǐng)先關(guān)系?，F(xiàn)假定計(jì)算機(jī)專(zhuān)業(yè)的必修課及其先修課程的關(guān)系如圖10－12(a)所示。圖10－12課程學(xué)習(xí)的AOV網(wǎng)

(a)課程及其先修關(guān)系；(b)表示先修關(guān)系的有向圖圖10－12課程學(xué)習(xí)的AOV網(wǎng)

(a)課程及其先修關(guān)系；(b)表示先修關(guān)系的有向圖(c)圖(a)的鄰接表(c)

定義1

一個(gè)有向圖G，若各頂點(diǎn)表示活動(dòng)，各條邊表示活動(dòng)之間的領(lǐng)先關(guān)系，則稱(chēng)該有向圖為頂點(diǎn)活動(dòng)網(wǎng)絡(luò)(activityonvertexnetwork)或AOV網(wǎng)絡(luò)。圖10－12(b)的有向圖即為一個(gè)AOV網(wǎng)絡(luò)。

AOV網(wǎng)絡(luò)代表的領(lǐng)先關(guān)系應(yīng)當(dāng)是一種擬序關(guān)系，它具有傳遞性(transitive)和反自反性(irreflexive)。如果這種關(guān)系不是反自反的，就意味著要求一個(gè)活動(dòng)必須在它自己開(kāi)始之前就完成。這顯然是荒謬的，這類(lèi)工程是不可實(shí)施的。如果給定了一個(gè)AOV網(wǎng)絡(luò)，我們所關(guān)心的事情之一，是要確定由此網(wǎng)絡(luò)的各邊所規(guī)定的領(lǐng)先關(guān)系是否是反自反的，也就是說(shuō)，該AOV網(wǎng)絡(luò)中是否包含任何有向回路。一般地，它應(yīng)當(dāng)是一個(gè)有向無(wú)環(huán)圖(DAG)。

2.拓?fù)湫蛄泻屯負(fù)渑判蚨x2

一個(gè)拓?fù)湫蛄?topologicalorder)是AOV網(wǎng)絡(luò)中頂點(diǎn)的線性序列，使得對(duì)圖中任意兩個(gè)頂點(diǎn)i和j，i是j的前驅(qū)結(jié)點(diǎn)，則在線性序列中i先于j。我們可以用拓?fù)渑判虻姆椒▉?lái)測(cè)試AOV網(wǎng)絡(luò)的可行性，同時(shí)還可以得到各活動(dòng)的一個(gè)拓?fù)湫蛄?。例如?duì)圖10－12所列的各門(mén)課程排出一個(gè)線性次序，按照該次序修讀課程，能夠保證學(xué)習(xí)任何一門(mén)課程時(shí)，它的先修課程已經(jīng)學(xué)過(guò)。一個(gè)有向圖的拓?fù)湫蛄胁皇俏┮坏摹Ｏ旅媸菆D10－12示例的兩個(gè)可能的拓?fù)湫蛄?。C0,C1,C2,C3,C4,C5,C7,C8,C6C0,C7,C8,C1,C4,C2,C3,C6,C5

3.拓?fù)渑判蛩惴ㄍ負(fù)渑判蛩惴擅枋鋈缦拢?/p>

(1)在圖中選擇一個(gè)入度為零的頂點(diǎn)，并輸出之；

(2)從圖中刪除該頂點(diǎn)及其所有出邊(以該頂點(diǎn)為尾的有向邊)；

(3)重復(fù)(1)和(2)，直到所有頂點(diǎn)都已列出，或者直到剩下的圖中再也沒(méi)有入度為零的頂點(diǎn)為止。后者表示圖中包含有向回路。

注意，從圖中刪除一個(gè)頂點(diǎn)及其所有出邊，會(huì)產(chǎn)生新的入度為零的頂點(diǎn)，必須用一個(gè)堆?；蜿?duì)列來(lái)保存這些待處理的無(wú)前驅(qū)的頂點(diǎn)。這些入度為零的頂點(diǎn)的輸出次序就拓?fù)渑判蚨允菬o(wú)關(guān)緊要的。

拓?fù)渑判蚩梢栽诓煌拇鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)，與遍歷運(yùn)算相似，鄰接表方法在這里更有效。拓?fù)渑判蛩惴ò▋蓚€(gè)基本操作：(1)決定一個(gè)頂點(diǎn)是否入度為零；(2)刪除一個(gè)頂點(diǎn)的所有出邊。如果我們對(duì)每個(gè)頂點(diǎn)的直接前驅(qū)予以計(jì)數(shù)，使用一個(gè)數(shù)組InDgree保存每個(gè)頂點(diǎn)的入度，即InDgree[i]為頂點(diǎn)i的入度，則基本操作(1)很容易實(shí)現(xiàn)。而基本操作(2)在使用鄰接表表示時(shí)，一般會(huì)比鄰接矩陣更有效。在鄰接矩陣的情況下，必須處理與該頂點(diǎn)有關(guān)的整行元素(n個(gè))，而鄰接表只需處理在鄰接矩陣中非零的那些頂點(diǎn)。

4.拓?fù)渑判蛩惴ǖ腃語(yǔ)言程序程序10－7給出了拓?fù)渑判虻腃語(yǔ)言程序。程序采用鄰接表表示圖，并為每個(gè)頂點(diǎn)i設(shè)立了一個(gè)計(jì)數(shù)器InDegree[i]，保存頂點(diǎn)i的入度?？梢酝ㄟ^(guò)修改程序10－1和程序10－2的圖的構(gòu)造函數(shù)CreateGraph和插入函數(shù)Add，在建立鄰接表的同時(shí)計(jì)算頂點(diǎn)的入度，并將其保存在InDegree數(shù)組中(見(jiàn)程序10－8)。設(shè)MaxVertices是圖的最多可能的頂點(diǎn)數(shù)，數(shù)組order[MaxVertices]保存求得的一個(gè)拓?fù)湫蛄??！境绦?0－7】拓?fù)渑判駽語(yǔ)言程序。voidTopoSort(Graphg，int*order){inti,j,k,count=-1,top=-1,n=g.Vertices;ENode*p;for(i=0;i<n;i++) /*圖中入度為零的頂點(diǎn)進(jìn)棧*/if(!InDegree[i]){InDegree[i]=top;top=i;}for(i=0;i<n;i++){ /*產(chǎn)生和輸出拓?fù)湫蛄?/if(top==-1){printf("Networkhasacycle.Toposortterminated.");return;}else{j=top;top=InDegree[top]; /*入度為零的頂點(diǎn)j出棧*/order[++count]=j; /*輸出頂點(diǎn)j到拓?fù)湫蛄?/for(p=g.A[j];p;p=p->NextArc){k=p->AdjVex;InDegree[k]--; /*將j的鄰接點(diǎn)k的入度減1*/if(!InDegree[k]){ InDegree[k]=top;top=k;/*新的入度為零的頂點(diǎn)k進(jìn)棧*/ }/*EndIf*/ }/*EndFor*/ }/*EndElse*/}/*EndFor*/}/*EndTopoSort*/【程序10－8】修改的構(gòu)造函數(shù)和插入函數(shù)。intInDegree[MaxVertices];voidCreateGraph(Graph*g,intn){ inti;g->Vertices=n; g->A=(ENode**)malloc(n*sizeof(ENode*)); for(i=0;i<n;i++){ g->A[i]=NULL; InDegree[i]=0; }}BOOLAdd(Graph*g,intu,intv,Tw){ intn;ENode*p;n=g->Vertices; if(u<0||v<0||u>n-1||v>n-1||u==v||Exist(*g,u,v)){ printf("BadInput\n");returnFALSE; } p=NewENode(v,w,g->A[u]);g->A[u]=p; InDegree[v]++;returnTRUE;}

程序10－7中沒(méi)有專(zhuān)門(mén)創(chuàng)建一個(gè)堆棧來(lái)保存入度為零的頂點(diǎn)，而是直接利用InDegree數(shù)組空間，形成鏈?zhǔn)蕉褩?，保存入度為零的頂點(diǎn)。當(dāng)一個(gè)頂點(diǎn)k一旦成為入度為零的頂點(diǎn)，便將頂點(diǎn)k插入鏈接堆棧中，即頂點(diǎn)k成為新的棧頂元素。設(shè)指針top指向棧頂元素，則進(jìn)棧操作為：

InDegree[k]＝top；top＝k。表10－1列出當(dāng)以圖10－12（c）的鄰接表為輸入時(shí)，InDegree數(shù)組值的改變過(guò)程。初始時(shí)，InDegree[i]的值是頂點(diǎn)i的入度。算法執(zhí)行過(guò)程中，表中陰影部分空間用于棧空間，空白部分為空閑部分，其余部分仍保存頂點(diǎn)入度。表10－1InDegree數(shù)組的值10.4.2*關(guān)鍵路徑

1.用邊代表活動(dòng)的網(wǎng)絡(luò)(AOE網(wǎng)絡(luò))

前面討論的AOV網(wǎng)絡(luò)是一種以頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)之間的領(lǐng)先關(guān)系的有向圖。有時(shí)，AOV網(wǎng)絡(luò)的頂點(diǎn)可以帶權(quán)表示完成一次活動(dòng)所需要的時(shí)間。與AOV網(wǎng)絡(luò)相對(duì)應(yīng)的還有一種活動(dòng)網(wǎng)絡(luò)，稱(chēng)為AOE網(wǎng)絡(luò)(activityonedge)，它以頂點(diǎn)代表事件(event)，有向邊表示活動(dòng)(activity)，有向邊的權(quán)表示一項(xiàng)活動(dòng)所需的時(shí)間(duration)。頂點(diǎn)所代表的事件是指它的入邊代表的活動(dòng)均已完成，由它的出邊代表的活動(dòng)可以開(kāi)始這樣一種狀態(tài)。這種網(wǎng)絡(luò)可以用來(lái)估算一項(xiàng)工程的完成時(shí)間。

圖10－13(a)中的邊<i,j>代表編號(hào)為k的活動(dòng)，ak=w(i,j)是邊上的權(quán)值，它是完成活動(dòng)ak所需的時(shí)間。圖10－13(b)是AOE網(wǎng)絡(luò)的一個(gè)例子，它代表一個(gè)包括11項(xiàng)活動(dòng)和9個(gè)事件的工程，其中，事件v0表示整個(gè)工程的開(kāi)始，事件v8表示整個(gè)工程的結(jié)束。每個(gè)事件vi(i=1,…,7)表示在它之前的所有活動(dòng)都已經(jīng)完成，在它之后的活動(dòng)可以開(kāi)始這樣的事件。例如v4表示活動(dòng)a3和a4已經(jīng)完成，a6和a7可以開(kāi)始。a0=6表示活動(dòng)a0需要的時(shí)間是6(天)，類(lèi)似地，a1=4，…,也具有這樣的含義。圖10－13一個(gè)AOE網(wǎng)絡(luò)(a)代表活動(dòng)ak的邊<i,j>；(b)AOE網(wǎng)絡(luò)的例子

由于整個(gè)工程只有一個(gè)開(kāi)始頂點(diǎn)和一個(gè)完成頂點(diǎn)，故在正常情況(無(wú)回路)下，網(wǎng)絡(luò)中只有一個(gè)入度為零的頂點(diǎn)，稱(chēng)為源點(diǎn)(source)，和一個(gè)出度為零的頂點(diǎn)，稱(chēng)為匯點(diǎn)(sink)。

2.關(guān)鍵路徑和關(guān)鍵活動(dòng)利用AOE網(wǎng)絡(luò)可以進(jìn)行工程進(jìn)度估算。如研究完成整個(gè)工程至少需要多少時(shí)間，為縮短工期應(yīng)該加快哪些活動(dòng)的速度，即決定哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵。關(guān)鍵路徑法是解決這些問(wèn)題的一種方法。因?yàn)樵贏OE網(wǎng)絡(luò)中，有些活動(dòng)可以并行地進(jìn)行，所以完成工程所需的最短時(shí)間(minimuntime)是從開(kāi)始頂點(diǎn)到完成頂點(diǎn)的最長(zhǎng)路徑(longestpath)的長(zhǎng)度(這里，路徑長(zhǎng)度等于路徑上各邊的權(quán)之和，而不是路徑上弧的數(shù)目)。這條最長(zhǎng)路徑稱(chēng)為關(guān)鍵路徑。例如，圖10－13中，路徑(v0,v1,v4,v7,v8)就是一條長(zhǎng)度為19(a0+a3+a7+a10=19)的關(guān)鍵路徑，這就是說(shuō)整個(gè)工程至少需要19(天)才能完成。

分析關(guān)鍵路徑的目的在于找出關(guān)鍵活動(dòng)。所謂關(guān)鍵活動(dòng)(criticalactivity)就是對(duì)整個(gè)工程的最短工期(最短完成時(shí)間)有影響的活動(dòng)，如果它不能如期完成就會(huì)影響整個(gè)工程的進(jìn)度。找到關(guān)鍵活動(dòng)，便可對(duì)其給予足夠的重視，投入較多的人力和物力，以確保工程的如期完成，并可爭(zhēng)取提前完成。設(shè)有一個(gè)包含n個(gè)事件和e個(gè)活動(dòng)的AOE網(wǎng)，其中，源點(diǎn)是事件v0，匯點(diǎn)是事件vn－1。為找關(guān)鍵路徑，我們先定義幾個(gè)有關(guān)的量：(1)事件vi的可能的最早發(fā)生時(shí)間earliest(i)：是從開(kāi)始頂點(diǎn)v0到頂點(diǎn)vi的最長(zhǎng)路徑的長(zhǎng)度。

(2)事件vi的允許的最遲發(fā)生時(shí)間latest(i)：是在保證完成頂點(diǎn)vi在earliest(n－1)時(shí)刻發(fā)生的前提下，事件vi允許的最晚發(fā)生時(shí)間，即在不影響工期的條件下，事件vi允許的最晚發(fā)生時(shí)間，它等于earliest(n－1)減去從vi

到vn－1的最長(zhǎng)路徑的長(zhǎng)度。頂點(diǎn)vi

到vn－1的最長(zhǎng)路徑的長(zhǎng)度表示從事件vi實(shí)際發(fā)生以后(如果一切按進(jìn)度規(guī)定執(zhí)行)到事件vn－1發(fā)生之間所需的時(shí)間。(3)活動(dòng)ak可能的最早開(kāi)始時(shí)間early(k)：等于事件vi

可能的最早發(fā)生時(shí)間earliest(i)。設(shè)與活動(dòng)ak關(guān)聯(lián)的邊為<vi,vj>。

(4)活動(dòng)ak允許的最遲開(kāi)始時(shí)間late(k)：它等于latest(i)－w(i,j)，w(i,j)是活動(dòng)ak所需的時(shí)間。設(shè)與活動(dòng)ak關(guān)聯(lián)的邊為<vi,vj>。若early(k)=late(k)，則活動(dòng)ak是關(guān)鍵活動(dòng)。如果一個(gè)活動(dòng)ak是關(guān)鍵活動(dòng)，它必須在它可能的最早開(kāi)始時(shí)間立即開(kāi)始，毫不拖延才能保證不影響工程在earliest(n－1)時(shí)完成，否則由于ak的延誤，則整個(gè)工程將延期。

3.關(guān)鍵路徑算法從上面的討論可知，求解關(guān)鍵路徑的核心是計(jì)算earliest和latest。

(1)求事件可能的最早發(fā)生時(shí)間earliest:(10－1)

公式（10－1）是計(jì)算各事件可能的最早發(fā)生時(shí)間的遞推公式。計(jì)算從源點(diǎn)earliest(0)=0開(kāi)始，按照一定次序遞推計(jì)算其他頂點(diǎn)的earliest(j)的值。其中，P(j)是所有以j為頭的邊〈i,j〉的尾結(jié)點(diǎn)i的集合。為了使公式(10－1)的遞推計(jì)算順利進(jìn)行，必須保證在計(jì)算每個(gè)earliest(j)的值時(shí)，所有的earliest(i)，i

P(j)的值已經(jīng)求得。為了滿(mǎn)足這一點(diǎn)，計(jì)算可以按照頂點(diǎn)的拓?fù)浯涡蜻M(jìn)行。(2)求事件允許的最遲發(fā)生時(shí)間latest：(10－2)

公式10－2是計(jì)算各事件允許的最遲發(fā)生時(shí)間的遞推公式。計(jì)算從匯點(diǎn)latest(n－1)=earliest(n－1)開(kāi)始，從后向前遞推計(jì)算其他頂點(diǎn)的latest(i)的值。其中，S(i)是所有以i為尾的邊〈i,j〉的頭結(jié)點(diǎn)j的集合。這一公式的計(jì)算要求保證，當(dāng)計(jì)算某個(gè)latest(i)的值時(shí)，所有的latest(j)j

S(i)已經(jīng)求得。如果已經(jīng)求得AOE網(wǎng)的頂點(diǎn)的拓?fù)湫蛄?，則只需按逆拓?fù)浯涡?reversetopologicalorder)進(jìn)行計(jì)算，便可滿(mǎn)足公式10-2遞推計(jì)算的條件。(3)求活動(dòng)的最早開(kāi)始時(shí)間early(k)和最遲開(kāi)始時(shí)間late(k)：設(shè)有邊ak=〈i,j〉，則early(k)=earliest(i)，而late(k)=latest(i)－w(i,j)，w(i,j)是活動(dòng)ak所需的時(shí)間。圖10－13(b)中AOE網(wǎng)絡(luò)的關(guān)鍵路徑的計(jì)算結(jié)果見(jiàn)圖10－14。圖10－14圖10－13(b)AOE網(wǎng)絡(luò)的關(guān)鍵路徑

4.關(guān)鍵路徑算法的C語(yǔ)言程序程序10－9給出計(jì)算earliest和latest的C語(yǔ)言函數(shù):Earliest和Latest。

(1)函數(shù)Earliest：設(shè)拓?fù)渑判虻慕Y(jié)果已被記錄在order數(shù)組中，算法首先將earliest數(shù)組的所有元素初始化為0，然后按拓?fù)浯涡蛴?jì)算earliest值。

(2)函數(shù)Latest：設(shè)拓?fù)渑判虻慕Y(jié)果已被記錄在order數(shù)組中，算法首先將latest數(shù)組的所有元素初始化為earliest[n?1]，然后按逆拓?fù)浯涡蛴?jì)算latest值。【程序10－9】關(guān)鍵路徑的C語(yǔ)言程序voidEarliest(Graphg,int*order,int*earliest){inti,k,n=g.Vertices;ENode*p;for(i=0;i<n;i++)earliest[i]=0; /*將earliest[]初始化為0*/for(i=0;i<n;i++){k=order[i];/*按拓?fù)浯涡蛴?jì)算*/for(p=g.A[k];p;p=p->NextArc) if(earliest[p->AdjVex]<earliest[k]+p->W) /*計(jì)算earliest[k]*/ earliest[p->AdjVex]=earliest[k]+p->W;}}voidLatest(Graphg,int*order,int*earliest,int*latest){inti,j,k,n=g.Vertices;ENode*p;for(i=0;i<n;i++) latest[i]=earliest[n－1]; /*對(duì)latest[]初始化）*/for(i=n-2;i>－1;i--){ j=order[i];for(p=g.A[j];p;p=p->NextArc){ k=p->AdjVex; if(latest[j]>latest[k]-p->W) latest[j]=latest[k]-p->W;}}}

使用頂點(diǎn)的earliest和latest的值，我們可以計(jì)算early和late的值。我們已經(jīng)知道函數(shù)TopoSort可以測(cè)試網(wǎng)中是否存在有向回路，但網(wǎng)絡(luò)中還可能會(huì)存在其他錯(cuò)誤。例如，網(wǎng)絡(luò)中可能存在某些從源點(diǎn)出發(fā)不可到達(dá)的頂點(diǎn)。當(dāng)我們對(duì)這樣的網(wǎng)絡(luò)進(jìn)行關(guān)鍵路徑分析時(shí)，會(huì)有多個(gè)頂點(diǎn)的earliest[i]=0。我們假定所有活動(dòng)的時(shí)間大于0，只有源點(diǎn)的earliest的值為0。因此，我們可以使用關(guān)鍵路徑法來(lái)發(fā)現(xiàn)工程計(jì)劃中的這種錯(cuò)誤。10.5最小代價(jià)生成樹(shù)

一個(gè)無(wú)向連通圖的生成樹(shù)是一個(gè)極小連通子圖，它包括圖中全部頂點(diǎn)，并且有盡可能少的邊。遍歷一個(gè)連通圖得到圖的一棵生成樹(shù)。圖的生成樹(shù)不是惟一的，采用不同的遍歷方法，從不同的頂點(diǎn)出發(fā)可能得到不同的生成樹(shù)。對(duì)于帶權(quán)的連通圖即網(wǎng)絡(luò)，如何尋找一棵生成樹(shù)使得各條邊上的權(quán)值的總和最小，是一個(gè)很有實(shí)際意義的問(wèn)題。一個(gè)典型的應(yīng)用是設(shè)計(jì)通信網(wǎng)。要在n個(gè)城鎮(zhèn)間建立通信網(wǎng)，至少要架設(shè)n－1條線路，這時(shí)自然會(huì)考慮如何使得造價(jià)最小。在兩個(gè)城鎮(zhèn)間設(shè)立線路，會(huì)有一定的經(jīng)濟(jì)代價(jià)。我們用網(wǎng)絡(luò)來(lái)表示n個(gè)城鎮(zhèn)以及它們之間可能設(shè)立的通信線路，其中，圖中頂點(diǎn)表示城鎮(zhèn)，邊代表兩城鎮(zhèn)之間的線路，邊上的權(quán)值代表相應(yīng)的代價(jià)。對(duì)于一個(gè)有n個(gè)頂點(diǎn)的網(wǎng)絡(luò)，可有多棵不同的生成樹(shù)，我們希望選擇總耗費(fèi)最少的一棵生成樹(shù)。這就是構(gòu)造連通圖的最小代價(jià)生成樹(shù)問(wèn)題。

一棵生成樹(shù)的代價(jià)(cost)是各條邊上的代價(jià)之和。一個(gè)網(wǎng)絡(luò)的各生成樹(shù)中，具有最小代價(jià)的生成樹(shù)稱(chēng)為該網(wǎng)絡(luò)的最小代價(jià)生成樹(shù)(minimum-costspanningtree)。構(gòu)造最小代價(jià)生成樹(shù)有多種算法，下面介紹其中的兩種：普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法。這兩種算法都建立在下面的結(jié)論之上。設(shè)圖G=(V，E)是一個(gè)帶權(quán)連通圖，U是頂點(diǎn)集合V的一個(gè)非空子集。若(u,v)是一條具有最小權(quán)值的邊，其中，u

U，v

V－U，則必存在一棵包含邊(u,v)的最小代價(jià)生成樹(shù)。

可以用反證法證明之。如果圖G的任何一棵最小代價(jià)生成樹(shù)都不包括(u,v)，設(shè)T是G的一棵最小代價(jià)生成樹(shù)。當(dāng)將(u,v)加到T中時(shí)，T中必定存在一條包含邊(u,v)的回路。另一方面，由于T是生成樹(shù)，則T上必定存在另一條邊(u',v')，其中，u'

U，v'

V－U，且u和u'之間，v和v'之間均有路徑相通。刪除邊(u',v')，便可消除回路，并同時(shí)得到另一棵生成樹(shù)T'。因?yàn)?u,v)的代價(jià)不高于(u',v')，則T'的代價(jià)亦不高于T。T'包含(u,v)，故與假設(shè)矛盾。這一結(jié)論是下面討論的Prim算法和Kruskal算法的理論基礎(chǔ)。10.5.1普里姆算法

1．普里姆算法設(shè)G=(V,E)是帶權(quán)的連通圖，T=(V',E')是正在構(gòu)造中的生成樹(shù)。初始狀態(tài)下，這棵生成樹(shù)只有一個(gè)頂點(diǎn)，沒(méi)有邊，即V'={u0}，E'={}，u0是任意選定的頂點(diǎn)。從初始狀態(tài)開(kāi)始，重復(fù)執(zhí)行下列運(yùn)算：尋找一條代價(jià)最小的邊(u',v')，邊(u',v')是一個(gè)端點(diǎn)u在構(gòu)造中的生成樹(shù)上(即u

V')，另一個(gè)端點(diǎn)v不在該樹(shù)上(即v

V－V')的所有這樣的邊(u,v)中代價(jià)最小的。將這條最小邊(u',v')加到生成樹(shù)上(即將v'并入集合V',邊(u',v')并入E')。直到V=V'為止。這時(shí)E'中必有n－1條邊，T=(V',E')是圖G的一棵最小代價(jià)生成樹(shù)。圖10－15普里姆算法構(gòu)造最小代價(jià)生成樹(shù)2．普里姆算法的C語(yǔ)言程序?qū)崿F(xiàn)普里姆算法，要使用兩個(gè)一維輔助數(shù)組nearest和lowcost。初始狀態(tài)下，所有的nearest[v]均為u0，lowcost[v]為∞。在算法執(zhí)行過(guò)程中，設(shè)v是當(dāng)前尚未選入生成樹(shù)的頂點(diǎn)，nearest[v]中保存邊(u,v)在生成樹(shù)上的那個(gè)頂點(diǎn)u，邊(u,v)是所有u(V'的邊中權(quán)值最小的邊。該邊上的權(quán)值保存在lowcost[v]中，即(nearest[v],v,lowcost[v])

代表一條權(quán)值為lowcost[v]，兩個(gè)頂點(diǎn)分別為nearest[v]和v的一條邊，它記錄當(dāng)前對(duì)v而言，與生成樹(shù)上頂點(diǎn)相鄰的所有邊中權(quán)值最小者。輔助數(shù)組mark用于在算法執(zhí)行中，標(biāo)志某個(gè)頂點(diǎn)當(dāng)前是否已被選到生成樹(shù)上。mark[v]=FALSE表示頂點(diǎn)v尚未選入生成樹(shù)，否則表示v已選入。MaxNum是類(lèi)型為T(mén)的一個(gè)不出現(xiàn)在圖的邊上的最大權(quán)值。程序10－10為普里姆算法的C語(yǔ)言程序，該程序要求圖以鄰接表表示。程序10－10的執(zhí)行結(jié)果保存在數(shù)組nearest和lowcost中。對(duì)于圖10－15(a)所示的網(wǎng)，若選擇頂點(diǎn)0為起始頂點(diǎn)，并對(duì)每個(gè)頂點(diǎn)v(0≤v＜n)按(nearest[v],v,lowcost[v])形式輸出，將得到下列生成樹(shù)的邊集：(0,0,0)(2,1,5)(0,2,1)(5,3,2)(1,4,3)(2,5,4)。【程序10－10】普里姆算法的C語(yǔ)言程序。voidPrim(Graphg,intk,int*nearest,T*lowcost){inti,j,min,n=g.Vertices;BOOLmark[MaxVertices];ENode*p;if(k<0||k>n－1){printf("BadInput\n");return;}for(i=0;i<n;i++){/*初始化*/nearest[i]=－1;mark[i]=FALSE;lowcost[i]=MaxNum;}lowcost[k]=0;nearest[k]=k;mark[k]=TRUE; /*源點(diǎn)k加入生成樹(shù)*/for(i=1;i<n;i++){ for(p=g.A[k];p;p=p->NextArc){ /*修改lowcost和nearest的值*/ j=p->AdjVex; if((!mark[j])&&(lowcost[j]>p->W)){lowcost[j]=p->W;nearest[j]=k;}}min=MaxNum; /*求下一條最小權(quán)值的邊*/for(j=0;j<n;j++)if((!mark[j])&&(lowc