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

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

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

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

E，必有〈v,u〉

E，即E是對稱的，則可以用一個無序?qū)?u,v)代替這兩個有序?qū)?，表示u和v之間的一條邊，便成為無向圖。圖10－2中的G1是無向圖，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>是允許的，這樣的邊稱為自回路(selfloop)，如圖10－3(a)所示。兩頂點(diǎn)間允許有多條相同邊的圖，稱為多重圖(multigraph)，如圖10－3(b)所示。在我們以后的討論中，不允許存在自回路和多重圖。圖10－3自回路和多重圖示例(a)自回路；(b)多重圖圖10－4完全圖示例

如果一個圖有最多的邊數(shù)，稱為完全圖(completegraph)。無向完全圖有n(n－1)/2條邊；有向完全圖有n(n－1)條邊。圖10－4是一個無向完全圖。若(v1,v2)是無向圖的一條邊，則稱頂點(diǎn)v1和v2相鄰接(adjacent)；若〈v1,v2〉是有向圖的一條邊，則稱頂點(diǎn)v1鄰接到(adjacentto)頂點(diǎn)v2,頂點(diǎn)v2鄰接自(adjacentfrom)v1，并稱邊(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的一個子圖(subgraph)是一個圖G'=(V',E')，使得V'(G')

V(G),E'(G')

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

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

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

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

圖中一個頂點(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。

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

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

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

voidCreateGraph(Graph*g,intn,Tnoedge)

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

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

后置條件:向圖中添加權(quán)值為w(若邊上沒有權(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é)中，我們將通過添加新運(yùn)算，陸續(xù)擴(kuò)充ADT10－1的圖抽象數(shù)據(jù)類型。主要包括以下圖運(yùn)算：

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

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

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

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

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

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

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

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

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

圖10－7給出了圖的鄰接矩陣表示的例子。圖10－7(d)是(a)的無向圖G1的鄰接矩陣，它是對稱矩陣，這是因?yàn)橐粭l無向邊被認(rèn)為是兩條有向邊。圖10－7(f)是(c)的網(wǎng)G3的鄰接矩陣，主對角線為0，若<u,v>是圖中的邊，則A(u,v)為邊<u,v>上的權(quán)值，否則A(u,v)為。圖10－7鄰接矩陣示例(a)無向圖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)便是圖的另一種表示方法。對圖10－1的電路，根據(jù)克?；舴蚨?，列出結(jié)點(diǎn)的電流方程為寫成矩陣形式為：

上式左邊的矩陣是圖的關(guān)聯(lián)矩陣A，右邊向量稱為支路電流向量Ib，這樣克?；舴螂娏鞫煽蓪懗删仃嚤硎臼紸·Ib=0。

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

m階矩陣：

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

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

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

4．建立鄰接矩陣函數(shù)CreateGraph構(gòu)造一個有n個頂點(diǎn)，但不包含邊的有向圖，一個無向圖的一條邊可以看成兩條有向邊。由于圖的頂點(diǎn)數(shù)事先并不知道，所以我們使用動態(tài)存儲分配的二維數(shù)組。程序10－1的構(gòu)造函數(shù)CreateGraph完成對二維數(shù)組A的動態(tài)存儲分配。其中，變量NoEdge用于表示A[i][j]處沒有邊時的值。對于不帶權(quán)的圖，NoEdge為0；對于網(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時，表示輸入?yún)?shù)u和v無效，而g->A[u][v]!=g->NoEdge，則表示邊<u，v>已經(jīng)存在，不能再重復(fù)輸入。如果不屬于上述情況，則在鄰接矩陣中添加邊<u,v>，具體做法是：令g->A[u][v]=w;，其中，對帶權(quán)的圖，w的值是邊<u,v>的權(quán)值，對一般的有向圖，有w=1。(2)Delete函數(shù):當(dāng)輸入?yún)?shù)u和v無效，或當(dāng)g->A[u][v]==g->NoEdge時，不能執(zhí)行刪除運(yùn)算，否則從鄰接矩陣中刪除邊<u,v>，即令g->A[u][v]=g->NoEdge。

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

在圖結(jié)構(gòu)中，我們習(xí)慣用編號來標(biāo)識頂點(diǎn)。為了簡單起見，我們常省去保存頂點(diǎn)信息的Element域，圖10－8(e)是圖10－7(a)的無向圖G1的鄰接表表示。在無向圖的鄰接表中，一條邊對應(yīng)兩個邊結(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語言定義下面我們給出用鄰接表作為存儲表示的圖的C語言類型定義。邊結(jié)點(diǎn)的結(jié)構(gòu)類型為ENode，每個結(jié)點(diǎn)有三個域AdjVex、W和NextArc。圖被定義成結(jié)構(gòu)類型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)造一個有n個頂點(diǎn)，但不包含邊的有向圖。由于圖的頂點(diǎn)數(shù)事先并不知道，所以我們使用動態(tài)存儲分配的一維指針數(shù)組。程序10－3的構(gòu)造函數(shù)完成對一維指針數(shù)組A的動態(tài)存儲分配，并對其每個元素賦初值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)對圖的邊的搜索、插入和刪除操作。這基本上是單鏈表上的操作。

(1)Exist函數(shù)：頂點(diǎn)u的單鏈表中的每個邊結(jié)點(diǎn)指示u的一個鄰接點(diǎn)v。表頭指針A[u]指向第一個邊結(jié)點(diǎn)。Exist函數(shù)從A[u]出發(fā)，在u的單鏈表中搜索AdjVex域?yàn)関的邊結(jié)點(diǎn)，若存在，則返回TRUE，否則返回FALSE。(2)Add函數(shù)：Add函數(shù)首先創(chuàng)建一個代表一條權(quán)為w的邊〈u,v〉的新邊結(jié)點(diǎn)，并將其插入鄰接表中由指針A[u]所指示的單鏈表的最前面。函數(shù)ENode*NewENode(intvex,Tweight,ENode*nextarc)構(gòu)造一個新的邊結(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)，則刪除之。刪除操作與在單鏈表中刪除一個結(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)用鄰接表表示無向圖(見圖10－8(e))時，每條邊以(u,v)和(v,u)的形式在鄰接表中出現(xiàn)兩次。在某些圖問題的求解中，需要給被處理的邊加上標(biāo)記，以免重復(fù)處理。若采用鄰接表表示，需同時對鄰接表中代表同一條邊的兩個邊結(jié)點(diǎn)加標(biāo)記，而這兩處邊結(jié)點(diǎn)又不在同一個頂點(diǎn)單鏈表中，這給搜索帶來很大的不便。用鄰接多重表表示無向圖可簡化上述問題的處理。圖10-9有向圖的正交鏈表和無向圖的多重表表示2．無向圖的多重表表示法

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

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

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

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

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

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

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

2.深度優(yōu)先搜索的遞歸算法程序10－5給出了實(shí)現(xiàn)深度優(yōu)先搜索的DFS遞歸函數(shù)，以及深度優(yōu)先遍歷的Traversal_DFS函數(shù)。后者調(diào)用前者完成對圖的深度優(yōu)先遍歷。若算法采用圖10－10(b)的鄰接表表示，則在該鄰接表上執(zhí)行DFS算法得到的深度優(yōu)先遍歷的生成森林見圖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)，或者說查看頂點(diǎn)v的所有出邊，對其中未標(biāo)記的鄰接點(diǎn)嵌套調(diào)用DFS函數(shù)。因此DFS算法對有向圖的每條邊都恰好查看一次。對無向圖，一條無向邊被視作兩條有向邊，被查看兩次。此外，DFS算法中每個頂點(diǎn)僅被訪問一次。設(shè)圖的頂點(diǎn)數(shù)為n，邊數(shù)為e，則遍歷圖算法的時間為O(n+e)。如果用鄰接矩陣表示圖，則所需時間為O(n2)。10.3.2寬度優(yōu)先遍歷

1.寬度優(yōu)先搜索假定初始時，圖G的所有頂點(diǎn)都未被訪問過，那么從圖中某個頂點(diǎn)v出發(fā)的寬度優(yōu)先搜索圖的過程BFS可以描述為：訪問頂點(diǎn)v，并對v打上已訪問標(biāo)記，然后依次訪問v的各個未訪問過的鄰接點(diǎn)，接著再依次訪問分別與這些鄰接點(diǎn)相鄰接且未訪問過的頂點(diǎn)。對圖10－11(a)的無向圖G，從頂點(diǎn)0出發(fā)的寬度優(yōu)先搜索過程是：首先訪問頂點(diǎn)0，然后訪問與它相鄰接的頂點(diǎn)1，11，10，接著再依次訪問這三個頂點(diǎn)的鄰接點(diǎ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)無向圖G；(b)圖G的寬度優(yōu)先搜索生成樹

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

2.寬度優(yōu)先搜索算法程序10－6給出了實(shí)現(xiàn)寬度優(yōu)先搜索的BFS函數(shù)以及寬度優(yōu)先遍歷的Traversal_BFS函數(shù)。后者調(diào)用前者完成對圖的寬度優(yōu)先遍歷。該算法需要創(chuàng)建一個隊(duì)列，作為輔助數(shù)據(jù)結(jié)構(gòu)。在遍歷中，對某個頂點(diǎn)v(它自身已訪問)，算法依次訪問它的所有未訪問過的鄰接點(diǎn)時，需將這些鄰接點(diǎn)保存在隊(duì)列中。當(dāng)頂點(diǎn)v的所有鄰接點(diǎn)全部訪問完畢后，從隊(duì)列中取出一個頂點(diǎn)，接著訪問這個頂點(diǎn)的鄰接點(diǎn)，并依次進(jìn)隊(duì)列。需使用語句#include"queue.h"將隊(duì)列數(shù)據(jù)結(jié)構(gòu)包含在內(nèi)。對圖10－11(a)的無向圖G執(zhí)行BFS，得到的寬度優(yōu)先遍歷的生成樹見圖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)先搜索圖的算法，可知每個頂點(diǎn)都進(jìn)隊(duì)列一次，而對于每個從隊(duì)列取走的頂點(diǎn)v都查看其所有的鄰接點(diǎn)，或者說查看頂點(diǎn)v的所有出邊，因此BFS算法對無向圖的每條邊都恰好查看兩次。此外，BFS算法中每個頂點(diǎn)僅被訪問一次。設(shè)圖的頂點(diǎn)數(shù)為n，邊數(shù)為e，則寬度優(yōu)先遍歷圖算法的時間為O(n+e)。如果用鄰接矩陣表示圖，則所需時間為O(n2)。10.4拓?fù)渑判蚝完P(guān)鍵路徑10.4.1拓?fù)渑判?/p>

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

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

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

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

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

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

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

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

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

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

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

4.拓?fù)渑判蛩惴ǖ腃語言程序程序10－7給出了拓?fù)渑判虻腃語言程序。程序采用鄰接表表示圖，并為每個頂點(diǎn)i設(shè)立了一個計(jì)數(shù)器InDegree[i]，保存頂點(diǎn)i的入度?？梢酝ㄟ^修改程序10－1和程序10－2的圖的構(gòu)造函數(shù)CreateGraph和插入函數(shù)Add，在建立鄰接表的同時計(jì)算頂點(diǎn)的入度，并將其保存在InDegree數(shù)組中(見程序10－8)。設(shè)MaxVertices是圖的最多可能的頂點(diǎn)數(shù)，數(shù)組order[MaxVertices]保存求得的一個拓?fù)湫蛄小！境绦?0－7】拓?fù)渑判駽語言程序。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中沒有專門創(chuàng)建一個堆棧來保存入度為零的頂點(diǎn)，而是直接利用InDegree數(shù)組空間，形成鏈?zhǔn)蕉褩?，保存入度為零的頂點(diǎn)。當(dāng)一個頂點(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）的鄰接表為輸入時，InDegree數(shù)組值的改變過程。初始時，InDegree[i]的值是頂點(diǎn)i的入度。算法執(zhí)行過程中，表中陰影部分空間用于?？臻g，空白部分為空閑部分，其余部分仍保存頂點(diǎn)入度。表10－1InDegree數(shù)組的值10.4.2*關(guān)鍵路徑

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.關(guān)鍵路徑算法的C語言程序程序10－9給出計(jì)算earliest和latest的C語言函數(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值?！境绦?0－9】關(guān)鍵路徑的C語言程序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]; /*對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可以測試網(wǎng)中是否存在有向回路，但網(wǎng)絡(luò)中還可能會存在其他錯誤。例如，網(wǎng)絡(luò)中可能存在某些從源點(diǎn)出發(fā)不可到達(dá)的頂點(diǎn)。當(dāng)我們對這樣的網(wǎng)絡(luò)進(jìn)行關(guān)鍵路徑分析時，會有多個頂點(diǎn)的earliest[i]=0。我們假定所有活動的時間大于0，只有源點(diǎn)的earliest的值為0。因此，我們可以使用關(guān)鍵路徑法來發(fā)現(xiàn)工程計(jì)劃中的這種錯誤。10.5最小代價生成樹

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

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

U，v

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

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

U，v'

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

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

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

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

代表一條權(quán)值為lowcost[v]，兩個頂點(diǎn)分別為nearest[v]和v的一條邊，它記錄當(dāng)前對v而言，與生成樹上頂點(diǎn)相鄰的所有邊中權(quán)值最小者。輔助數(shù)組mark用于在算法執(zhí)行中，標(biāo)志某個頂點(diǎn)當(dāng)前是否已被選到生成樹上。mark[v]=FALSE表示頂點(diǎn)v尚未選入生成樹，否則表示v已選入。MaxNum是類型為T的一個不出現(xiàn)在圖的邊上的最大權(quán)值。程序10－10為普里姆算法的C語言程序，該程序要求圖以鄰接表表示。程序10－10的執(zhí)行結(jié)果保存在數(shù)組nearest和lowcost中。對于圖10－15(a)所示的網(wǎng)，若選擇頂點(diǎn)0為起始頂點(diǎn)，并對每個頂點(diǎn)v(0≤v＜n)按(nearest[v],v,lowcost[v])形式輸出，將得到下列生成樹的邊集：(0,0,0)(2,1,5)(0,2,1)(5,3,2)(1,4,3)(2,5,4)。【程序10－10】普里姆算法的C語言程序。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加入生成樹*/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