第6章圖本章中介紹下列主要內(nèi)容：圖的定義圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷操作圖的幾個(gè)典型問(wèn)題本章目錄6.1圖的基本概念16.2圖的存儲(chǔ)結(jié)構(gòu)26.3圖的遍歷36.4最小生成樹(shù)46.5拓?fù)渑判?6.6AOE網(wǎng)與關(guān)鍵路徑6結(jié)束6.7最短路徑問(wèn)題76.1圖的基本概念6.1.1圖的定義6.1.2圖的基本術(shù)語(yǔ)6.1.3

圖的基本操作返回到總目錄6.1.1圖的定義圖是由一個(gè)非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間關(guān)系即邊（或者?。┑募辖M成，它可以定義為一個(gè)二元組：G=(V,E)其中，G表示一個(gè)圖，V表示圖G中全部頂點(diǎn)組成的非空集合，E是圖G中全部邊組成的集合。按照?qǐng)D中邊是否有方向性，圖分為有向圖和無(wú)向圖兩類(lèi)。圖6-1（a）表示的是無(wú)向圖，圖6-1（b）表示的是有向圖。返回到本節(jié)目錄有向圖和無(wú)向圖的示例（a）無(wú)向圖G1

（b）有向圖G2圖6-1圖的類(lèi)型返回到本節(jié)目錄有向圖和無(wú)向圖的邊的表示在無(wú)向圖中，用圓括號(hào)表示兩個(gè)頂點(diǎn)之間的邊。（vi,vj）表示頂點(diǎn)vi和頂點(diǎn)vj

之間連線(xiàn)表示的邊。若圖中邊有方向，則用尖括號(hào)表示兩個(gè)頂點(diǎn)之間的首尾關(guān)系，有向邊也稱(chēng)為弧。在有向邊<vi,vj>中，vi稱(chēng)為弧尾，vj稱(chēng)為弧頭。返回到本節(jié)目錄6.1.2圖的基本術(shù)語(yǔ)1．無(wú)向圖（Undigraph）

在一個(gè)圖中，如果每條邊都沒(méi)有方向（如圖6-1（a）所示），則稱(chēng)該圖為無(wú)向圖。2．有向圖（Digraph）在一個(gè)圖中，如果每條邊都有方向（如圖6-1（b）所示），則稱(chēng)該圖為有向圖。3．無(wú)向完全圖在一個(gè)無(wú)向圖中，如果任意兩頂點(diǎn)都有一條直接邊相連接，則稱(chēng)該圖為無(wú)向完全圖。如圖6-2（a），可以證明，在一個(gè)含有n個(gè)頂點(diǎn)的無(wú)向完全圖中，有n(n-1)/2條邊。

返回到本節(jié)目錄6.1.2圖的基本術(shù)語(yǔ)4．有向完全圖在一個(gè)有向圖中，如果任意兩頂點(diǎn)之間都有方向互為相反的兩條弧相連接，則稱(chēng)該圖為有向完全圖。如圖6-2（b），在一個(gè)含有n個(gè)頂點(diǎn)的有向完全圖中，有n(n-1)條弧。5．頂點(diǎn)的度、入度、出度在無(wú)向圖中：一個(gè)頂點(diǎn)擁有的邊數(shù)，稱(chēng)為該頂點(diǎn)的度。記為T(mén)D(v)。返回到本節(jié)目錄6.1.2圖的基本術(shù)語(yǔ)在有向圖中：

（a）一個(gè)頂點(diǎn)擁有的弧頭的數(shù)目，稱(chēng)為該頂點(diǎn)的入度，記為ID(v)；

（b）一個(gè)頂點(diǎn)擁有的弧尾的數(shù)目，稱(chēng)為該頂點(diǎn)的出度，記為OD(v)；

（c）一個(gè)頂點(diǎn)度等于頂點(diǎn)的入度+出度，即：TD(v)=ID(v)＋OD(v)。返回到本節(jié)目錄6.1.2圖的基本術(shù)語(yǔ)6．權(quán)圖的邊或弧有時(shí)具有與它有關(guān)的數(shù)據(jù)信息，這個(gè)數(shù)據(jù)信息就稱(chēng)為權(quán)（Weight）。7．網(wǎng)——邊(或弧)上帶權(quán)的圖稱(chēng)為網(wǎng)(Network)。如果每一條邊都有與它相關(guān)的數(shù)，稱(chēng)為權(quán)，我們將這種帶權(quán)的圖叫做網(wǎng)。如果圖中邊是無(wú)方向的帶權(quán)圖，則圖是一個(gè)無(wú)向網(wǎng)；如果圖中邊是有方向的帶權(quán)圖，則就是一個(gè)有向網(wǎng)。返回到本節(jié)目錄6.1.2圖的基本術(shù)語(yǔ)8．路徑、路徑長(zhǎng)度頂點(diǎn)vi到頂點(diǎn)vj之間的路徑是指頂點(diǎn)序列vi，vk1，vk2，…，vkm，vj.。其中：（vi,vk1），(vk1,vk2)，…，(vkm,.vj)分別為圖中的邊。路徑上邊或弧的數(shù)目稱(chēng)為路徑長(zhǎng)度。在圖6-1（a）的無(wú)向圖G1中，v1→v3→v4→v5與v1→v2→v5是從頂點(diǎn)v1

到頂點(diǎn)v5

的兩條路徑，路徑長(zhǎng)度分別為3和2。返回到本節(jié)目錄6.1.2圖的基本術(shù)語(yǔ)9．回路或環(huán)在一個(gè)路徑中，若其第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)是相同的，則稱(chēng)該路徑為一個(gè)回路或環(huán)。10．簡(jiǎn)單路徑若表示路徑的頂點(diǎn)序列中的頂點(diǎn)各不相同，則稱(chēng)這樣的路徑為簡(jiǎn)單路徑。如圖6-1（a）中的v1→v3→v4。11．簡(jiǎn)單回路除了第一個(gè)和最后一個(gè)頂點(diǎn)外，其余各頂點(diǎn)均不重復(fù)出現(xiàn)的回路為簡(jiǎn)單回路。返回到本節(jié)目錄6.1.2圖的基本術(shù)語(yǔ)12．稀疏圖對(duì)于有很少條邊的圖(e<nlog2n，e為邊數(shù)，n為頂點(diǎn)數(shù))稱(chēng)為稀疏圖，反之稱(chēng)為稠密圖。13．子圖對(duì)于圖G=（V，E），G′=（V′，E′），若存在V′是V的子集，E′是E的子集，則稱(chēng)圖G′是G的一個(gè)子圖。14．連通圖、連通分量在無(wú)向圖中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i≠j)有路徑，則稱(chēng)頂點(diǎn)vi和vj是連通的。任意兩頂點(diǎn)都是連通的圖稱(chēng)為連通圖。無(wú)向圖的極大連通子圖稱(chēng)為連通分量。返回到本節(jié)目錄6.1.2圖的基本術(shù)語(yǔ)15．強(qiáng)連通圖、強(qiáng)連通分量對(duì)于有向圖來(lái)說(shuō)，若圖中任意一對(duì)頂點(diǎn)vi

和vj(i≠j)均有從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj有路徑，也有從vj到vi的路徑，則稱(chēng)該有向圖是強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱(chēng)為強(qiáng)連通分量。16．生成樹(shù)連通圖G的一個(gè)子圖如果是一棵包含G的所有頂點(diǎn)的樹(shù)，則該子圖稱(chēng)為G的生成樹(shù)（SpanningTree）。在生成樹(shù)中添加任意一條屬于原圖中的邊必定會(huì)產(chǎn)生回路,n個(gè)頂點(diǎn)的生成樹(shù)具有n-1條邊。返回到本節(jié)目錄6.1.3

圖的基本操作圖的基本操作有：（1）CreatGraph(G)：輸入圖G的頂點(diǎn)和邊，建立圖G的存儲(chǔ)。（2）DFSTraverse(G，v)：在圖G中，從頂點(diǎn)v出發(fā)深度優(yōu)先遍歷圖G。（3）BFSTtaverse(G，v)：在圖G中，從頂點(diǎn)v出發(fā)廣度優(yōu)先遍歷圖G。

返回到本節(jié)目錄6.2圖的存儲(chǔ)結(jié)構(gòu)6.2.1鄰接矩陣6.2.2鄰接表返回到總目錄6.2.1鄰接矩陣1．圖的鄰接矩陣圖的鄰接矩陣是使用順序結(jié)構(gòu)存儲(chǔ)圖。假設(shè)圖G＝（V，E）有n個(gè)頂點(diǎn)，即V＝{v0,v1,…,vn-1}，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣：A[i][j]=1

若(vi,vj)或<vi,vj>是E(G)中的邊

0

若(vi,vj)或<vi,vj>不是E(G)中的邊返回到本節(jié)目錄（a）G1的鄰接矩陣（b）G2的鄰接矩陣圖6-6圖6-1的鄰接矩陣返回到本節(jié)目錄2．網(wǎng)的鄰接矩陣若G是網(wǎng)，則鄰接矩陣可定義為：

wij

若(vi,vj)或<vi,vj>是E(G)中的邊

A[i][j]=0若i=j時(shí)

∞

若(vi,vj)或<vi,vj>不是E(G)中的邊其中，wij表示邊(vi,vj)或<vi,vj>上的權(quán)值；∞表示一個(gè)計(jì)算機(jī)允許的、大于所有邊的權(quán)值的數(shù)。圖6-7（a）所示的無(wú)向網(wǎng)G4用鄰接矩陣表示法如圖6-7（b）所示；返回到本節(jié)目錄（a）無(wú)向網(wǎng)G4的示意圖（b）無(wú)向網(wǎng)G4的鄰接矩陣圖6-7網(wǎng)和網(wǎng)的鄰接矩陣返回到本節(jié)目錄3．圖的鄰接矩陣表示法的特點(diǎn)（1）無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)的，而有向圖的鄰接矩陣不一定對(duì)稱(chēng)。（2）對(duì)于無(wú)向圖，頂點(diǎn)vi的度是鄰接矩陣中第i行（或第i列）的非零元素的個(gè)數(shù)。（3）對(duì)于有向圖，頂點(diǎn)vi的度是鄰接矩陣中第i行和第i列的非零元素的個(gè)數(shù)之和。（4）用鄰接矩陣方法存儲(chǔ)圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連，但要確定圖中的邊數(shù)，則必須按行、按列對(duì)每個(gè)元素進(jìn)行檢查，所花費(fèi)的時(shí)間代價(jià)很大。這是鄰接矩陣存儲(chǔ)圖的局限性。返回到本節(jié)目錄4．建立一個(gè)圖的鄰接矩陣的算法（1）以鄰接矩陣存儲(chǔ)圖頂點(diǎn)間的關(guān)系定義圖的一種存儲(chǔ)結(jié)構(gòu)。#defineMAXVEX100/*圖中最大頂點(diǎn)個(gè)數(shù)*/typedefcharVertexType[3];/*定義VertexType為char數(shù)組類(lèi)型*/typedefstructvertex{intadjvex;/*頂點(diǎn)編號(hào)*/VertexTypedata;/*頂點(diǎn)的信息*/}VType;/*頂點(diǎn)類(lèi)型*/返回到本節(jié)目錄typedefstructgraph{intn,e;/*n為實(shí)際頂點(diǎn)數(shù)，e為實(shí)際邊數(shù)*/VTypevexs[MAXVEX];/*頂點(diǎn)集合*/intedges[MAXVEX][MAXVEX];/*邊的集合*/}AdjMatix;/*圖的鄰接矩陣類(lèi)型*/返回到本節(jié)目錄（2）用鄰接矩陣為存儲(chǔ)結(jié)構(gòu)建立圖的算法（如算法6.1）。

算法6.1intCreateMatix(AdjMatix*g){inti,j,k,b,t,e;intw;printf("\n頂點(diǎn)數(shù)(n))和邊數(shù)(e)：");scanf("%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){printf("序號(hào)為%d的頂點(diǎn)信息：",i);scanf("%s",g->vexs[i].data);g->vexs[i].adjvex=i;}返回到本節(jié)目錄for(i=0;i<g->n;i++)for(j=0;j<g->n;j++)g->edges[i][j]=0;/*將鄰接矩陣元素全部置0*/for(k=0;k<g->e;k++){printf("序號(hào)為%d的邊=>",k);printf("起點(diǎn)號(hào)終點(diǎn)號(hào)

權(quán)值：");scanf("%d%d%d",&b,&t,&w);/*輸入行數(shù)，列數(shù)和權(quán)值*/

返回到本節(jié)目錄if(b<g->n&&t<g->n&&w>0)g->edges[b][t]=w;/*將b行、t列權(quán)值w存入鄰接矩陣*/else{printf("\n輸入錯(cuò)誤！");return(0);}}return(1);}返回到本節(jié)目錄6.2.2鄰接表1．圖的鄰接表鄰接表(AdjacencyList)是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。鄰接表表示法類(lèi)似于樹(shù)的孩子鏈表表示法。就是對(duì)于圖G中的每個(gè)頂點(diǎn)vi，該方法將所有鄰接于vi的頂點(diǎn)vj連成一個(gè)單鏈表，這個(gè)單鏈表就稱(chēng)為頂點(diǎn)vi的鄰接表。再將所有點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。在鄰接表表示中有兩種結(jié)點(diǎn)結(jié)構(gòu)，如圖6-8所示。返回到本節(jié)目錄圖6-8鄰接矩陣表示的結(jié)點(diǎn)結(jié)構(gòu)對(duì)于網(wǎng)的邊表需再增設(shè)一個(gè)存儲(chǔ)邊上信息（如權(quán)值等）的域（info），網(wǎng)的邊表結(jié)構(gòu)如圖6-9所示。圖6-9

網(wǎng)的邊表結(jié)構(gòu)返回到本節(jié)目錄

圖6-1（a）中的圖G1和（b）中的圖G2的鄰接表如圖6-10（a）、（b）所示。為了便于確定頂點(diǎn)i的入度或以頂點(diǎn)i為頭的弧，可以建立一個(gè)逆鄰接表。逆鄰接表是對(duì)每個(gè)頂點(diǎn)i建立一個(gè)鏈接以它為頭的弧尾頂點(diǎn)的鏈表。圖6-9（c）就是圖6-1（b）中圖G2逆鄰接表。圖G1的鄰接表（b）圖G2的鄰接表（c）圖G2的逆鄰接表圖6-10圖的鄰接表返回到本節(jié)目錄2．圖的鄰接表表示法的特點(diǎn)（1）無(wú)向圖中若有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表需要n個(gè)表頭指針和2e個(gè)邊結(jié)點(diǎn)。而有向圖中有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表需要n個(gè)表頭指針和e個(gè)邊結(jié)點(diǎn)。（2）對(duì)于無(wú)向圖，頂點(diǎn)vi的度是第i個(gè)鏈表的結(jié)點(diǎn)數(shù)。（3）對(duì)于有向圖，頂點(diǎn)vi的出度是第i個(gè)鏈表的結(jié)點(diǎn)數(shù)，而求入度則必須遍歷整個(gè)鄰接表，即在所有鏈表中找鄰接點(diǎn)域的值為i的邊結(jié)點(diǎn)的個(gè)數(shù)。所以，對(duì)于那些需要經(jīng)常查找頂點(diǎn)入邊或入邊鄰接點(diǎn)的運(yùn)算，為此專(zhuān)門(mén)建立一個(gè)逆鄰接表，該表中每個(gè)頂點(diǎn)的單鏈表存儲(chǔ)所有入邊的信息。返回到本節(jié)目錄3．建立鄰接表的算法

(1)下面先給出一個(gè)以鄰接表為存儲(chǔ)結(jié)構(gòu)的圖類(lèi)型（ALGRAPH）定義:#defineNULL0/*NULL為空指針*/#defineMAXVEX100/*數(shù)組最大元素個(gè)數(shù)*/typedefcharVertexType[3];typedefstructedgenode{intadjvex;/*鄰接點(diǎn)序號(hào)*/intvalue;/*邊的權(quán)值*/structedgenode*next;/*下一條邊的頂點(diǎn)*/}ArcNode;/*每個(gè)頂點(diǎn)建立的單鏈表中結(jié)點(diǎn)的類(lèi)型*/返回到本節(jié)目錄typedefstructvexnode{VertexTypedata;/*結(jié)點(diǎn)信息*/ArcNode*firstarc;/*指向第一條邊結(jié)點(diǎn)*/}VHeadNode;/*單鏈表的頭結(jié)點(diǎn)類(lèi)型*/typedefstruct{intn,e;/*n為實(shí)際頂點(diǎn)數(shù)，e為實(shí)際邊數(shù)*/VHeadNodeadjlist[MAXVEX];/*單鏈表頭結(jié)點(diǎn)數(shù)組*/}AdjList;/*圖的鄰接表類(lèi)型*/返回到本節(jié)目錄2．圖的鄰接表表示法的特點(diǎn)（1）無(wú)向圖中若有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表需要n個(gè)表頭指針和2e個(gè)邊結(jié)點(diǎn)。而有向圖中有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表需要n個(gè)表頭指針和e個(gè)邊結(jié)點(diǎn)。（2）對(duì)于無(wú)向圖，頂點(diǎn)vi的度是第i個(gè)鏈表的結(jié)點(diǎn)數(shù)。（3）對(duì)于有向圖，頂點(diǎn)vi的出度是第i個(gè)鏈表的結(jié)點(diǎn)數(shù)，而求入度則必須遍歷整個(gè)鄰接表，即在所有鏈表中找鄰接點(diǎn)域的值為i的邊結(jié)點(diǎn)的個(gè)數(shù)。所以，對(duì)于那些需要經(jīng)常查找頂點(diǎn)入邊或入邊鄰接點(diǎn)的運(yùn)算，可以為此專(zhuān)門(mén)建立一個(gè)逆鄰接表，該表中每個(gè)頂點(diǎn)的單鏈表存儲(chǔ)所有入邊的信息。返回到本節(jié)目錄3．建立鄰接表的算法（1）以鄰接表為存儲(chǔ)結(jié)構(gòu)定義圖類(lèi)型ALGRAPH。#defineNULL0/*NULL為空指針*/#defineMAXVEX100/*數(shù)組最大元素個(gè)數(shù)*/typedefcharVertexType[3];typedefstructedgenode{intadjvex;/*鄰接點(diǎn)序號(hào)*/intvalue;/*邊的權(quán)值*/structedgenode*next;/*下一條邊的頂點(diǎn)*/}ArcNode;/*每個(gè)頂點(diǎn)建立的單鏈表中結(jié)點(diǎn)的類(lèi)型*/返回到本節(jié)目錄typedefstructvexnode{VertexTypedata;/*結(jié)點(diǎn)信息*/ArcNode*firstarc;/*指向第一條邊結(jié)點(diǎn)*/}VHeadNode;/*單鏈表的頭結(jié)點(diǎn)類(lèi)型*/typedefstruct{intn,e;/*n為實(shí)際頂點(diǎn)數(shù)，e為實(shí)際邊數(shù)*/VHeadNodeadjlist[MAXVEX];/*單鏈表頭結(jié)點(diǎn)數(shù)組*/}AdjList;/*圖的鄰接表類(lèi)型*/返回到本節(jié)目錄(2)用鄰接表為存儲(chǔ)結(jié)構(gòu)建立圖的算法（如算法6.3所示）

算法6.3intCreateAdjList(AdjList*g){inti,b,t,w;ArcNode*p;printf("\n頂點(diǎn)數(shù)(n)，邊數(shù)(e)：");scanf("%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){printf("\n序號(hào)為%d的頂點(diǎn)信息：",i);scanf("%s",g->adjlist[i].data);/*輸入每個(gè)頂點(diǎn)的數(shù)據(jù)域*/g->adjlist[i].firstarc=NULL;/*鄰接表的每個(gè)單鏈表頭指針置空*/}返回到本節(jié)目錄for(i=0;i<g->e;i++){printf("\n序號(hào)為邊=>",i);printf("\n起點(diǎn)號(hào)

終點(diǎn)號(hào)

權(quán)值：");scanf("%d%d%d",&b,&t,&w);/*輸入邊的起始點(diǎn)、終止點(diǎn)和邊的權(quán)值*/if(b<g->n&&t<g->n&&w>0)/*當(dāng)輸入數(shù)據(jù)正確時(shí)，生成新結(jié)點(diǎn)，插入鄰接表的某個(gè)鏈表頭部*/返回到本節(jié)目錄{p=(ArcNode*)malloc(sizeof(ArcNode));p->value=w;p->adjvex=t;p->next=g->adjlist[b].firstarc;g->adjlist[b].firstarc=p;}else{printf("\n輸入錯(cuò)誤！");return(0);}}return(1);}返回到本節(jié)目錄【例6.1】設(shè)計(jì)一個(gè)算法將有向圖G的鄰接矩陣存儲(chǔ)結(jié)構(gòu)結(jié)構(gòu)轉(zhuǎn)換成鄰接表存儲(chǔ)結(jié)構(gòu)。解：給定鄰接矩陣g，先創(chuàng)建鄰接表G，給g.n個(gè)頭結(jié)點(diǎn)置初值，掃描鄰接矩陣g，對(duì)于不為0的權(quán)值g.edges[i][j]，創(chuàng)建一個(gè)結(jié)點(diǎn)，其value域值置為g.edges[i][j]，adjvex域置為j，將其插入到G->adjlist[i]為頭結(jié)點(diǎn)的單鏈表的開(kāi)頭。最后設(shè)置G->n和G->e值。對(duì)應(yīng)算法如算法6.5所示。返回到本節(jié)目錄算法6.5AdjList*MatToList(AdjMatixg){inti,j;ArcNode*p;AdjList*G;G=(AdjList*)malloc(sizeof(AdjList));/*生成由G指向新的鄰接表結(jié)點(diǎn)*/for(i=0;i<g.n;i++){G->adjlist[i].firstarc=NULL;strcpy(G->adjlist[i].data,g.vexs[i].data);/*復(fù)制圖的數(shù)據(jù)域信息*/}返回到本節(jié)目錄for(i=0;i<g.n;i++)for(j=0;j<=g.n-1;j++)if(g.edges[i][j]!=0){p=(ArcNode*)malloc((sizeof(ArcNode)));/*新建鄰接表內(nèi)鏈表結(jié)點(diǎn)*/p->value=g.edges[i][j];/*賦邊的權(quán)值*/p->adjvex=j;/*賦值為該頂點(diǎn)的下一個(gè)鄰接頂點(diǎn)*/p->next=G->adjlist[i].firstarc;/*p與下一個(gè)結(jié)點(diǎn)相連*/G->adjlist[i].firstarc=p;/*將p賦給鄰接表頭指針，為頭插法*/}G->n=g.n;G->e=g.e;return(G);}返回到本節(jié)目錄6.3圖的遍歷所謂圖的遍歷（traversinggraph）是指從圖中的某一頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪(fǎng)問(wèn)一次，而且只訪(fǎng)問(wèn)一次。6.3.1深度優(yōu)先搜索法6.3.2廣度優(yōu)先搜索法返回到總目錄6.3.1深度優(yōu)先搜索法1．深度優(yōu)先搜索的方法：（1）首先從圖中某個(gè)頂點(diǎn)發(fā)v出發(fā)，首先訪(fǎng)問(wèn)此頂點(diǎn)，將其標(biāo)記為已訪(fǎng)問(wèn)過(guò)；（2）然后任選一個(gè)v的未被訪(fǎng)問(wèn)的鄰接點(diǎn)w出發(fā)，繼續(xù)進(jìn)行深度優(yōu)先搜索，（3）直到圖中所有和v路徑相通的頂點(diǎn)都被訪(fǎng)問(wèn)到；（4）若此時(shí)圖中還有頂點(diǎn)未被訪(fǎng)問(wèn)到，則另選一個(gè)未被訪(fǎng)問(wèn)的頂點(diǎn)作為起始點(diǎn)。重復(fù)上面的做法，直至圖中所有的頂點(diǎn)都被訪(fǎng)問(wèn)。返回到本節(jié)目錄（a）無(wú)向G5

（b）圖G5的鄰接表圖6-11圖G5

及其鄰接表返回到本節(jié)目錄我們以圖6-11（a）的無(wú)向圖G5為例來(lái)說(shuō)明其深度優(yōu)先搜索的方法。假定我們以鄰接表為存儲(chǔ)結(jié)構(gòu)。調(diào)用算法6.2，建成的鄰接表如圖6-11（b）所示(單鏈表中結(jié)點(diǎn)的插入方式為頭插法)。則從頂點(diǎn)0出發(fā)，開(kāi)始遍歷（這里的0～7所說(shuō)的是各頂點(diǎn)的編號(hào)）。圖的深度優(yōu)先搜索過(guò)程是一個(gè)遞歸過(guò)程，訪(fǎng)問(wèn)過(guò)程為：首先訪(fǎng)問(wèn)0（訪(fǎng)問(wèn)完，做上訪(fǎng)問(wèn)過(guò)標(biāo)記）。查看0的鏈表，它的第一個(gè)未訪(fǎng)問(wèn)鄰接點(diǎn)為2，于是訪(fǎng)問(wèn)2，并以2為出發(fā)點(diǎn)繼續(xù)深度遍歷。返回到本節(jié)目錄查看2的鏈表，它的第一個(gè)未訪(fǎng)問(wèn)鄰接點(diǎn)為6，于是訪(fǎng)問(wèn)6。從6號(hào)鏈表可知它第一個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)為5，于是訪(fǎng)問(wèn)5。查看5的鏈表，它的鄰接點(diǎn)2已經(jīng)訪(fǎng)問(wèn)過(guò)，于是回到6號(hào)鏈表，搜索下一未被訪(fǎng)問(wèn)的鄰接點(diǎn)。發(fā)現(xiàn)下一個(gè)鄰接點(diǎn)2已經(jīng)訪(fǎng)問(wèn)過(guò)且該鏈表不存在未被訪(fǎng)問(wèn)的鄰接點(diǎn)，于是回到2號(hào)鏈表，搜索下一未被訪(fǎng)問(wèn)鄰接點(diǎn)。發(fā)現(xiàn)2號(hào)也不存在未被訪(fǎng)問(wèn)鄰接點(diǎn)，于是回到0號(hào)鏈表，搜索到下一個(gè)未被訪(fǎng)問(wèn)鄰接點(diǎn)為1，于是訪(fǎng)問(wèn)1。返回到本節(jié)目錄查看1的鏈表，它的第一個(gè)未被訪(fǎng)問(wèn)鄰接點(diǎn)為4，于是訪(fǎng)問(wèn)4。查看4的鏈表，它的第一個(gè)未被訪(fǎng)問(wèn)的鄰接點(diǎn)是7，于是訪(fǎng)問(wèn)7。查看7的鏈表，它的第一個(gè)鄰接點(diǎn)已被訪(fǎng)問(wèn)，繼續(xù)搜索下一未被訪(fǎng)問(wèn)鄰接點(diǎn)是3，于是訪(fǎng)問(wèn)3。查看3鏈表已經(jīng)不存在未被訪(fǎng)問(wèn)鄰接點(diǎn)，于是回到4號(hào)表繼續(xù)搜索，再回到1號(hào)鏈表，再回到0號(hào)鏈表，遍歷最后完成。結(jié)果深度優(yōu)先遍歷序列是：0，2，6，5，1，4，7，3返回到本節(jié)目錄2．深度優(yōu)先搜索的算法算法6.6intvisited[MAXVEX];/*全局變量，訪(fǎng)問(wèn)數(shù)組*/voidDFS(AdjList*g,intvi){ArcNode*p;printf("%3d",vi);visited[vi]=1;p=g->adjlist[vi].firstarc;while(p!=NULL){if(visited[p->adjvex]==0)DFS(g,p->adjvex);p=p->next;}}返回到本節(jié)目錄6.3.2廣度優(yōu)先搜索法1．廣度優(yōu)先搜索的方法：假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪(fǎng)問(wèn)了v之后依次訪(fǎng)問(wèn)v的各個(gè)未曾訪(fǎng)問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪(fǎng)問(wèn)它們的鄰接點(diǎn)，并使“先被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪(fǎng)問(wèn)，直至圖中所有已被訪(fǎng)問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪(fǎng)問(wè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)到為止。返回到本節(jié)目錄我們還是以圖6-11所示的無(wú)向圖G5及其鄰接表為例來(lái)說(shuō)明其廣度優(yōu)先搜索的方法。初始準(zhǔn)備，給標(biāo)志數(shù)組visited[N]的每個(gè)元素賦初值0；假定從0號(hào)頂點(diǎn)出發(fā)，首先讓0入隊(duì)，做訪(fǎng)問(wèn)標(biāo)記。廣度優(yōu)先搜索遍歷過(guò)程如下：訪(fǎng)問(wèn)并刪除隊(duì)首結(jié)點(diǎn)0，然后遍歷0號(hào)鏈表，讓它的所有未做訪(fǎng)問(wèn)標(biāo)記的鄰接點(diǎn)（2，1）依次入隊(duì)，并做訪(fǎng)問(wèn)標(biāo)記。訪(fǎng)問(wèn)并刪除隊(duì)首結(jié)點(diǎn)2，然后遍歷2號(hào)鏈表，讓它的所有未做訪(fǎng)問(wèn)標(biāo)記的鄰接點(diǎn)（6，5）依次入隊(duì)，并做訪(fǎng)問(wèn)標(biāo)記。返回到本節(jié)目錄訪(fǎng)問(wèn)并刪除隊(duì)首結(jié)點(diǎn)1，然后遍歷1號(hào)鏈表，讓它的所有未做訪(fǎng)問(wèn)標(biāo)記的鄰接點(diǎn)（4，3）依次入隊(duì)，并做訪(fǎng)問(wèn)標(biāo)記。訪(fǎng)問(wèn)并刪除隊(duì)首結(jié)點(diǎn)6，然后遍歷6號(hào)鏈表。此時(shí)，鏈表中已無(wú)未做訪(fǎng)問(wèn)標(biāo)記的頂點(diǎn)。訪(fǎng)問(wèn)并刪除隊(duì)首結(jié)點(diǎn)5，然后遍歷5號(hào)鏈表。此時(shí)，鏈表中已無(wú)未做訪(fǎng)問(wèn)標(biāo)記的頂點(diǎn)。訪(fǎng)問(wèn)并刪除隊(duì)首結(jié)點(diǎn)4，然后遍歷4號(hào)鏈表。讓它唯一未做訪(fǎng)問(wèn)標(biāo)記的鄰接點(diǎn)7入隊(duì)，并做訪(fǎng)問(wèn)標(biāo)記。訪(fǎng)問(wèn)并刪除隊(duì)首結(jié)點(diǎn)3，然后遍歷3號(hào)鏈表。此時(shí)，鏈表中已無(wú)未做訪(fǎng)問(wèn)標(biāo)記的頂點(diǎn)。訪(fǎng)問(wèn)并刪除隊(duì)首結(jié)點(diǎn)7，然后遍歷7號(hào)鏈表。此時(shí)，鏈表中已無(wú)未做訪(fǎng)問(wèn)標(biāo)記的頂點(diǎn)。此時(shí)，隊(duì)列已空，遍歷完成，最后的輸出結(jié)果序列是：0，2，1，6，5，4，3，7。返回到本節(jié)目錄2．廣度優(yōu)先搜索的算法算法6.7voidBFS(AdjList*g,intvi){inti,v,visited[MAXVEX];intqu[MAXVEX],front=0,rear=0;/*定義循環(huán)隊(duì)列*/ArcNode*p;for(i=0;i<g->n;i++)/*輔助的訪(fǎng)問(wèn)數(shù)組賦初值*/visited[i]=0;printf("%5d",vi);/*輸出起始訪(fǎng)問(wèn)頂點(diǎn)*/visited[vi]=1;

返回到本節(jié)目錄rear=(rear+1)%MAXVEX;/*隊(duì)尾指針后移*/qu[rear]=vi;/*將vi入隊(duì)*/while(front!=rear)/*當(dāng)隊(duì)不空時(shí)*/{front=(front+1)%MAXVEX;v=qu[front];/*將隊(duì)頭元素出隊(duì)，賦給頂點(diǎn)v*/p=g->adjlist[v].firstarc;/*將頂點(diǎn)v的下一條鄰接邊頂點(diǎn)指針賦給p*/while(p!=NULL){if(visited[p->adjvex]==0)/*若未訪(fǎng)問(wèn)過(guò)*/返回到本節(jié)目錄{visited[p->adjvex]=1;/*訪(fǎng)問(wèn)數(shù)組該元素置1，已訪(fǎng)問(wèn)*/ printf("%5d",p->adjvex);/*輸出該頂點(diǎn)*/rear=(rear+1)%MAXVEX;/*隊(duì)尾指針后移*/qu[rear]=p->adjvex;/*將p所指的頂點(diǎn)入隊(duì)*/}p=p->next;/*p指針后移*/}}}返回到本節(jié)目錄6.4最小生成樹(shù)在一個(gè)無(wú)向連通圖G中，如果取它的全部頂點(diǎn)和一部分邊構(gòu)成一個(gè)子圖，即：V(G′)=V(G)和

E（G′）

E（G）若邊集E（G′）中的邊既將圖G中的所有頂點(diǎn)連通又不形成回路，則稱(chēng)子圖G′是原圖G的一棵生成樹(shù)。6.4.1普里姆(Prim)算法6.4.2克魯斯卡爾(Kruskal)算法返回到總目錄6.4.1普里姆(Prim)算法1．基本思想假設(shè)G=（V，E）是一個(gè)具有n個(gè)頂點(diǎn)的連通圖，T=（U，TE）是G的最小生成樹(shù)，其中U是T的頂點(diǎn)集，TE是T的邊集。U和TE初值均為空集。此算法的基本思想是：首先是從V中任取一個(gè)頂點(diǎn)（假定取v0），將它并入U(xiǎn)中，即U={v0}，然后只要U是V的真子集，就從那些其中一個(gè)端點(diǎn)已在T中，另一個(gè)端點(diǎn)仍在T外的所有邊中，找一條權(quán)值最小的邊，假定為(vi,vj)，其中vi∈U，

vj∈(V-U)，并把該邊(vi,vj)和頂點(diǎn)vj分別并入T的邊集TE和頂點(diǎn)集U，如此不斷重復(fù)，直到U=V，TE中含有n-1條邊，T就是最后得到的最小生成樹(shù)。返回到本節(jié)目錄【例6.2】對(duì)于如圖6-13所示的無(wú)向帶權(quán)圖，求利用普里姆算法從頂點(diǎn)a開(kāi)始構(gòu)造最小生成樹(shù)的過(guò)程（可用表6-1的形式將每個(gè)步驟選擇哪條邊，U集合和V-U集合的變化過(guò)程表示出來(lái)），最后畫(huà)出該圖的最小生成樹(shù)。圖6-13帶權(quán)無(wú)向圖G7返回到本節(jié)目錄解：用普里姆算法從頂點(diǎn)a開(kāi)始構(gòu)造最小生成樹(shù)。設(shè)U為生成樹(shù)頂點(diǎn)集合，V-U為未包含到生成樹(shù)的圖中頂點(diǎn)集合，構(gòu)造最小生成樹(shù)的生成過(guò)程如表6-2。表6-2圖G7的最小生成樹(shù)生成過(guò)程步驟當(dāng)前V-U集合的內(nèi)容當(dāng)前U集合的內(nèi)容生成樹(shù)選擇的邊邊的權(quán)值初始{a,b,c,d,e,f,g}{}{b,c,d,e,f,g}{a}1{b,c,d,e,f}{a,g}(a,g)32{b,c,d,f}{a,g,e}(g,e)23{b,c,d}{a,g,e,f}(e,f)14{b,c}{a,g,e,f,d}(e,d)35{c}{a,g,e,f,d,b}(g,b)66{}{a,g,e,f,d,b,c}(g,c)5返回到本節(jié)目錄由表6-2得到圖G7的最小生成樹(shù)如圖6-14所示。圖6-14例6.2用普里姆算法構(gòu)造的最小生成樹(shù)返回到本節(jié)目錄2．對(duì)應(yīng)的普里姆算法算法6.8#defineMAXVEX100/*圖中最大頂點(diǎn)個(gè)數(shù)*/#defineM32767/*32767代表無(wú)窮大*/voidPrim(intcost[][MAXVEX],intn,intv){intlowcost[MAXVEX],min;intclosest[MAXVEX],i,j,k;for(i=0;i<n;i++)/*給lowcost和closest賦初值*/{lowcost[i]=cost[v][i];closest[i]=v;}返回到本節(jié)目錄for(i=1;i<n;i++)/*找出n-1個(gè)頂點(diǎn)*/{min=M;for(j=0;j<n;j++)/*在V-U中找出離U最近的頂點(diǎn)k*/if(lowcost[j]!=0&&lowcost[j]<min){min=lowcost[j];k=j;}printf("\n邊(%d,%d)權(quán)為:%d",closest[k],k,min);lowcost[k]=0;/*標(biāo)記k已經(jīng)加入U(xiǎn)*/for(j=0;j<n;j++)/*修改數(shù)組lowcost和closest*/if(cost[k][j]!=0&&cost[k][j]<lowcost[j]){lowcost[j]=cost[k][j];closest[j]=k;}}}返回到本節(jié)目錄6.4.2克魯斯卡爾(Kruskal)算法

1.基本思想克魯斯卡爾（Kruskal）算法的思想是：假設(shè)G=（V，E）是一個(gè)具有n個(gè)頂點(diǎn)的連通網(wǎng)，T=（U，TE）是G的最小生成樹(shù)。U的初值等于V，即即有G中的全部頂點(diǎn)。算法開(kāi)始時(shí)，TE的初值為空集。將圖G中的邊按權(quán)值從小到大的順序依次選取，若選取的邊使生成樹(shù)T不形成回路，則把它并入TE中，保留作為T(mén)的一條邊；若選取的邊使生成樹(shù)T形成回路，則將其舍棄，如此進(jìn)行下去，直到TE中包含n-1條邊為止，此是的T即為最小生成樹(shù)。返回到本節(jié)目錄【例6.3】對(duì)于如圖6-13所示的帶權(quán)無(wú)向圖G7，求利用普里姆算法從頂點(diǎn)a開(kāi)始構(gòu)造最小生成樹(shù)的過(guò)程（可用表的形式寫(xiě)出生成樹(shù)的集合變化情況和每次選擇的邊），并將生成樹(shù)畫(huà)出來(lái)。解：初始設(shè)每個(gè)頂點(diǎn)都是單獨(dú)的一個(gè)生成樹(shù)集合，按權(quán)值從小到大依次選擇各邊，只要兩邊的頂點(diǎn)分別在不同的生成樹(shù)頂點(diǎn)集合里時(shí)，選擇該邊加入生成樹(shù)邊中。并將這兩個(gè)頂點(diǎn)集合合并成一個(gè)集合。重復(fù)得到整個(gè)生成樹(shù)。表6-4表示用克魯斯卡爾算法生成最小生成樹(shù)時(shí)生成樹(shù)頂點(diǎn)集合的變化過(guò)程。返回到本節(jié)目錄表6-4圖G7用克魯斯卡爾算法生成最小生成樹(shù)的頂點(diǎn)集合變化過(guò)程步驟生成樹(shù)中各頂點(diǎn)集合生成樹(shù)的邊生成樹(shù)的權(quán)值初始狀態(tài){a},,{c},gyg06qa,{e},{f},{g}1{a},,{c},mwqao0k,{e,f},{g}(e,f)12{a},,{c},6oyc0oq,{e,f,g}(e,g)23{a,e,f,g},,{c},4cyacwi(a,g)34{a,e,f,g,d},,{c}(e,d)35{a,e,f,g,d,c},(g,c)56{a,e,f,g,d,c,b}(g,b)6返回到本節(jié)目錄由表6-4克魯斯卡爾算法求最小生成樹(shù)的過(guò)程如圖6-16所示。圖6-16例6.3題用克魯斯卡爾算法構(gòu)造的最小生成樹(shù)返回到本節(jié)目錄2．對(duì)應(yīng)的克魯斯卡爾算法（1）邊的類(lèi)型定義如下：#defineMAXVEX100typedefstruct{intu;/*邊的起始頂點(diǎn)*/intv;/*邊的終止頂點(diǎn)*/intw;/*邊的權(quán)值*/}Edge;/*邊的類(lèi)型定義*/返回到本節(jié)目錄（2）克魯斯卡爾算法如算法6.9所示。算法6.9voidKruskal(EdgeE[],intn){inti,j,m1,m2,sn1,sn2,k;intvset[MAXVEX];for(i=0;i<n;i++)/*初始化輔助數(shù)組*/vset[i]=i;k=1;/*生成樹(shù)中的第幾條邊*/j=0;/*E中邊的下標(biāo),初值為0*/while(k<n)/*生成的邊數(shù)小于n時(shí)循環(huán)*/{m1=E[j].u;m2=E[j].v;/*取一條邊的兩個(gè)頂點(diǎn)*/

返回到本節(jié)目錄sn1=vset[m1];sn2=vset[m2];/*得到兩條邊的不同邊號(hào)*/if(sn1!=sn2){printf("\n邊(%d,%d)的權(quán)為:%d",m1,m2,E[j].w);k++;/*生成的邊數(shù)加1*/for(i=0;i<n;i++)if(vset[i]==sn2)/*合并兩個(gè)集合編號(hào)*/vset[i]=sn1;}j++;/*掃描下一條邊*/}}返回到本節(jié)目錄6.5拓?fù)渑判駻OV-網(wǎng)（ActivityOnVertex）：用頂點(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)。例如，一個(gè)計(jì)算機(jī)專(zhuān)業(yè)的學(xué)生必須學(xué)習(xí)一系列基本課程，其中有些課程是基礎(chǔ)課，如高等數(shù)學(xué)，它獨(dú)立于其他課程，而另一些課程必須在學(xué)完作為它的基礎(chǔ)的選修課才能開(kāi)始。如通常應(yīng)該在學(xué)完“程序設(shè)計(jì)基礎(chǔ)”和“離散數(shù)學(xué)”之后才開(kāi)始學(xué)習(xí)“數(shù)據(jù)結(jié)構(gòu)”。這種課程間的優(yōu)先關(guān)系如圖6-17表示。用頂點(diǎn)表示課程，弧表示先決條件，若課程Ci是課程Cj的先決條件，則有弧<Ci,Cj>存在。返回到總目錄課程編號(hào)課程名稱(chēng)先修課程C1高等數(shù)學(xué)無(wú)C2程序設(shè)計(jì)基礎(chǔ)無(wú)C3普通物理C1C4離散數(shù)學(xué)C1,C2C5C語(yǔ)言程序設(shè)計(jì)C2C6數(shù)據(jù)結(jié)構(gòu)C2,C4,C5C7編譯原理C5,C6C8計(jì)算機(jī)原理C3C9操作系統(tǒng)C6,C8表6-5計(jì)算機(jī)專(zhuān)業(yè)課必修示例返回到本節(jié)首頁(yè)在AOV網(wǎng)中不應(yīng)該存在回路，因?yàn)槌霈F(xiàn)回路則表示某活動(dòng)應(yīng)以它自己的完成作為先決條件，這顯然是不可能的。檢測(cè)有向圖是否存在回路的方法之一就是求圖中頂點(diǎn)的一個(gè)滿(mǎn)足下列性質(zhì)的排列：即若有向圖中有弧<i,j>存在，則在這個(gè)序列，i一定排在j之前，稱(chēng)有向圖的這一操作為拓?fù)渑判?。圖6-17表示課程之間優(yōu)先關(guān)系的有向無(wú)環(huán)圖返回到本節(jié)首頁(yè)1．進(jìn)行拓?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ù)湫蛄?。返回到本?jié)首頁(yè)2．拓?fù)渑判虼鎯?chǔ)結(jié)構(gòu)為了實(shí)現(xiàn)拓?fù)渑判虻乃惴?，?duì)于給定的有向圖，采用鄰接表作為存儲(chǔ)結(jié)構(gòu)，為每個(gè)頂點(diǎn)設(shè)立一個(gè)鏈表，每個(gè)鏈表有一個(gè)表頭結(jié)點(diǎn)，這些表頭結(jié)點(diǎn)構(gòu)成一個(gè)數(shù)組，表頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域count。注意，其它結(jié)構(gòu)體類(lèi)型與前面介紹的鄰接表定義的各類(lèi)型相同，只將鄰接表定義中的VHeadNode類(lèi)型修改如下：typedefstructvexnode{VertexTypedata;/*結(jié)點(diǎn)信息*/intcount;/*該頂點(diǎn)的入度*/ArcNode*firstarc;/*指向第一條邊結(jié)點(diǎn)*/}VHeadNode;/*單鏈表的頭結(jié)點(diǎn)類(lèi)型*/返回到本節(jié)首頁(yè)3．拓?fù)渑判虻膶?shí)現(xiàn)算法intCreateAdjList(AdjList*g){inti,b,t,w;ArcNode*p;printf("\n頂點(diǎn)數(shù)(n)，邊數(shù)(e)：");scanf("%d%d",&g->n,&g->e);for(i=0;i<g->n;i++){printf("序號(hào)為%d的頂點(diǎn)信息：",i);scanf("%s",g->adjlist[i].data);/*輸入每個(gè)頂點(diǎn)的數(shù)據(jù)域*/g->adjlist[i].firstarc=NULL;/*鄰接表的每個(gè)單鏈表頭指針置空*/g->adjlist[i].count=0;/*鄰接表的頂點(diǎn)入度域置為0*/}返回到本節(jié)首頁(yè)for(i=0;i<g->e;i++){printf(“序號(hào)為%d的邊=>",i);printf("起點(diǎn)號(hào)

終點(diǎn)號(hào)

權(quán)值：");scanf("%d%d%d",&b,&t,&w);/*輸入邊的起始點(diǎn)、終止點(diǎn)和邊的權(quán)值*/if(b<g->n&&t<g->n&&w>0)/*當(dāng)輸入數(shù)據(jù)正確時(shí)，生成新結(jié)點(diǎn)，插入鄰接表的某個(gè)鏈表頭部*/{p=(ArcNode*)malloc(sizeof(ArcNode));p->value=w;p->adjvex=t;p->next=g->adjlist[b].firstarc;返回到本節(jié)首頁(yè) g->adjlist[b].firstarc=p;g->adjlist[t].count++;/*鄰接表的頂點(diǎn)入度加1*/}else{printf("\n輸入錯(cuò)誤！");return(0);}}return(1);}返回到本節(jié)首頁(yè)6.6AOE網(wǎng)與關(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)。

1．AOE網(wǎng)中的基本概念（1）源點(diǎn)存在唯一的、入度為零的頂點(diǎn)，叫源點(diǎn)。（2）匯點(diǎn)存在唯一的、出度為零的頂點(diǎn)，叫匯點(diǎn)。返回到總目錄（3）關(guān)鍵路徑從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑的長(zhǎng)度即為完成整個(gè)工程任務(wù)所需的時(shí)間，該路徑叫做關(guān)鍵路徑。（4）關(guān)鍵活動(dòng)關(guān)鍵路徑上的活動(dòng)叫做關(guān)鍵活動(dòng)。如圖6-18所示的AOE-網(wǎng)。1為源點(diǎn)，表示整個(gè)工程可以開(kāi)始，9為匯點(diǎn)，表示整個(gè)工程結(jié)束。返回到本節(jié)首頁(yè)（1）事件vi的最早發(fā)生時(shí)間事件vi的最早發(fā)生時(shí)間用ve(i)表示。它是從源點(diǎn)到頂點(diǎn)vi的最長(zhǎng)路徑的長(zhǎng)度。求ve(i)時(shí)可從源點(diǎn)開(kāi)始，按拓?fù)漤樞蛳騾R點(diǎn)遞推：ve(0)=0；ve(i)=max{ve(k)＋<k,i>上的權(quán)}（<k,i>∈T,1≤i≤n-1）其中，T為所有以i為頭的弧<k,i>的集合。2．AOE中幾個(gè)重要的參量定義返回到本節(jié)首頁(yè)（2）事件vi的最遲發(fā)生時(shí)間事件vi的最遲發(fā)生時(shí)間用vl(i)表示，它是指在不推遲整個(gè)工程完成的前提下，該事件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)＋(<i,k>上的權(quán)}（<i,k>∈S,0≤i≤n-2）其中，S為所有以i為尾的弧<i,k>的集合。返回到本節(jié)首頁(yè)（3）活動(dòng)ai的最早開(kāi)始時(shí)間活動(dòng)ai的最早開(kāi)始時(shí)間用e(i)表示，它是該活動(dòng)的起點(diǎn)所表示的事件最早發(fā)生時(shí)間。如果活動(dòng)ai對(duì)應(yīng)的弧為<j,k>，則e(i)等于從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑的長(zhǎng)度，即：e(i)=ve(j)（4）活動(dòng)ai的最晚開(kāi)始時(shí)間活動(dòng)ai的最晚開(kāi)始時(shí)間用l(i)表示，如果活動(dòng)ai對(duì)應(yīng)的弧為<j,k>，則有：l(i)=vl(k)-<j,k>上的權(quán)返回到本節(jié)首頁(yè)（5）活動(dòng)ai的時(shí)間余量活動(dòng)ai的時(shí)間余量可以用d(i)表示，ai的最晚開(kāi)始時(shí)間與ai的最早開(kāi)始時(shí)間之差d(i)=l(i)-e(i)顯然，松弛時(shí)間（時(shí)間余量）為0的活動(dòng)為關(guān)鍵活動(dòng)。返回到本節(jié)首頁(yè)3．求關(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)。返回到本節(jié)首頁(yè)4．求關(guān)鍵路徑的過(guò)程（1）求AOE網(wǎng)中所有事件的最早發(fā)生時(shí)間ve(i)。（2）求AOE網(wǎng)中所有事件的最遲發(fā)生時(shí)間vl(i)。（3）求AOE網(wǎng)中所有活動(dòng)的最早開(kāi)始時(shí)間e(i)。（4）求AOE網(wǎng)中所有活動(dòng)的最遲開(kāi)始時(shí)間l(i)。（5）求AOE網(wǎng)中所有活動(dòng)的時(shí)間余量d(i)。時(shí)間余量為0的活動(dòng)即為關(guān)鍵路徑。返回到本節(jié)首頁(yè)【例6.4】對(duì)于圖6-18所示的AOE網(wǎng)，求事件i的最早發(fā)生時(shí)間ve(i)和最遲發(fā)生時(shí)間vl(i)，求出活動(dòng)ai的最早開(kāi)始時(shí)間e(i)和最遲開(kāi)始時(shí)間l(i)，并求出每個(gè)活動(dòng)的時(shí)間余量d(i)，并確定該AOE網(wǎng)的關(guān)鍵路徑。解：（1）求事件i的最早發(fā)生時(shí)間ve(i)如下：ve(1)=0ve(2)=6ve(3)=4ve(4)=5ve(5)=max{ve(2)+1,ve(3)+1}=7ve(6)=ve(4)+2=7ve(7)=ve(5)+9=16ve(8)=max{ve(5)+7,ve(6)+4}=14ve(9)=max{ve(7)+2,ve(8)+4}=18返回到本節(jié)首頁(yè)（2）求事件i的最遲發(fā)生時(shí)間vl(i)如下：vl(9)=ve(9)=18vl(8)=vl(9)-4=14vl(7)=vl(9)-2=16vl(6)=vl(8)-4=10vl(5)=min{vl(7)-9,vl(8)-7}=7vl(4)=vl(6)-2=8vl(3)=vl(5)-1=6vl(2)=vl(5)-1=6vl(1)=min{vl(2)-6,vl(3)-4,vl(4)-5}=0（3）求所有活動(dòng)的e(i)、l(i)和d(i)活動(dòng)a1：

e(1)=ve(1)=0l(1)=vl(2)-6=0d(1)=0活動(dòng)a2：

e(2)=ve(1)=0l(2)=vl(3)-3=3d(2)=3活動(dòng)a3：

e(3)=ve(1)=0l(3)=vl(4)-5=3d(3)=3返回到本節(jié)首頁(yè)活動(dòng)a4：

e(4)=ve(2)=6l(4)=vl(5)-1=6d(4)=0活動(dòng)a5：

e(5)=ve(3)=4l(5)=vl(5)-1=6d(5)=2活動(dòng)a6：

e(6)=ve(4)=5l(6)=vl(8)-4=10d(6)=5活動(dòng)a7：

e(7)=ve(5)=7l(7)=vl(7)-9=7d(7)=0活動(dòng)a8：

e(8)=ve(5)=7l(8)=vl(8)-7=7d(8)=0活動(dòng)a9：

e(9)=ve(6)=7l(9)=vl(8)-4=10d(9)=3活動(dòng)a10：e(10)=ve(7)=16l(10)=vl(9)-2=16d(10)=0活動(dòng)a11：e(11)=ve(8)=14l(11)=vl(9)-4=14d(11)=0當(dāng)d(i)=0的路徑為關(guān)鍵路徑，所以圖6-19所示的AOE網(wǎng)的關(guān)鍵路徑為：a1，a4，a7，a8，a10，a11。因此關(guān)鍵路徑為：（1，2，5，7，9）和（1，2，5，8，9）返回到本節(jié)首頁(yè)6.7最短路徑問(wèn)題在網(wǎng)中，求點(diǎn)A到點(diǎn)B的所有路徑中，邊的權(quán)值之和最短的那一條路徑。這條路徑就稱(chēng)為兩點(diǎn)之間的最短路徑，并稱(chēng)路徑上的第一個(gè)頂點(diǎn)為源點(diǎn)（Sourse），最后一個(gè)頂點(diǎn)為終點(diǎn)（Destination）。6.7.1求一個(gè)頂點(diǎn)到其他各頂點(diǎn)的最短路徑6.7.2求每一對(duì)頂點(diǎn)之間的最短路徑返回到總目錄6.7.1求一個(gè)頂點(diǎn)到其他各頂點(diǎn)的最短路徑

迪杰斯特拉（Dijkstra）提出了一個(gè)按長(zhǎng)度遞增的次序產(chǎn)生最短路徑的算法。該算法的思路是：設(shè)有向圖G=（V，E），其中，V={v0,v1,…,vn-1}，cost表示G的鄰接矩陣（帶權(quán)鄰接矩陣）cost[i][j]是表示有向邊<vi,vj>的權(quán)值。若不存在有向邊<vi,vj>，則cost[i][j]的權(quán)值為無(wú)窮大（∞）。設(shè)置一維數(shù)組s[0..n-1]，用于標(biāo)記已找到最短路徑的頂點(diǎn)。設(shè)頂點(diǎn)v為源點(diǎn)，集合s的初態(tài)只包含頂點(diǎn)v。即：返回到本節(jié)目錄以下用M表示∞，通常取大于最大權(quán)值的某個(gè)數(shù)值。設(shè)置一維數(shù)組s[0..n-1]，用于標(biāo)記已找到最短路徑的頂點(diǎn)。返回到本節(jié)目錄數(shù)組dist記錄從源點(diǎn)到其他各頂點(diǎn)當(dāng)前的最短距離，其初值為dist[i]=cost[v][i]，從s之外的頂點(diǎn)集合V-S中選中一個(gè)頂點(diǎn)vu，使dist[u]的值最小。于是從源點(diǎn)到達(dá)vu只通過(guò)s中的頂點(diǎn)，把u加入集合s中調(diào)整dist中記錄的從源點(diǎn)到V-S中每個(gè)頂點(diǎn)vj的距離：從原來(lái)的dist[j]和dist[u]+cost[u][j]中選擇較小的值作為新的dist[j]。重復(fù)上述過(guò)程，直到s中包含其余各頂點(diǎn)的最短路徑。返回到本節(jié)目錄【例6.5】用迪杰斯特拉方法求圖G8中從頂點(diǎn)0到達(dá)其它頂點(diǎn)的最短路徑。解：使用迪杰斯特拉方法，令S={0}，數(shù)組dist初始值為源點(diǎn)0到其他各頂點(diǎn)的鄰接邊的權(quán)值，不鄰接時(shí)對(duì)應(yīng)的值為極大值M，如6-6所示的表的步驟0對(duì)應(yīng)的行；選到某頂點(diǎn)的路徑的最小值為10（0->2），利用頂點(diǎn)2修正從源點(diǎn)0到其他頂點(diǎn)的當(dāng)前距離和當(dāng)前路徑，如頂點(diǎn)3的當(dāng)前路徑為M，而從源點(diǎn)1到2再到3的路徑現(xiàn)在為50小于M，替換頂點(diǎn)1到頂點(diǎn)3的路徑為(0,2,3)，并將頂點(diǎn)2并入集合S中。下次再取余下所有路徑中的最小值30（0->4），利用頂點(diǎn)4修正從源點(diǎn)0到其它頂點(diǎn)的當(dāng)前距離和當(dāng)前路徑，…，直到最后所有的頂點(diǎn)都并入到集合S中，求得從源點(diǎn)0到達(dá)其他各頂點(diǎn)的最短路徑。返回到本節(jié)目錄表6-6單源最短路徑求解過(guò)程執(zhí)行步驟頂點(diǎn)1頂點(diǎn)2頂點(diǎn)3頂點(diǎn)4頂點(diǎn)5經(jīng)過(guò)VjS0M10(0,2)M30(0,4)100(0,5)-{0}170(0,2,1)60(0,2,3)30(0,4)100(0,5)2{0,2}270(0,2,1)50(0,4,3)90(0,4,5)4{0,2,4}370(0,2,1)60(0,4,3,5)3{0,2,4,3}470(0,2,1)5{0,2,4,3,5}51{0,2,4,3,5,1}返回到本節(jié)目錄所以頂點(diǎn)0到達(dá)其它頂點(diǎn)的最短路徑為：0->1：最短路徑長(zhǎng)度為70，路徑為0->2->10->2：最短路徑長(zhǎng)度為10，路徑為0->20->3：最短路徑長(zhǎng)度為50，路徑為0->4->30->4：最短路徑長(zhǎng)度為30，路徑為0->40->5：最短路徑長(zhǎng)度為60，路徑為0->4->3->5返回到本節(jié)目錄(1)迪杰斯特拉算法如算法6.11所示。算法6.11#defineMAXVEX100#defineM10000/*圖的鄰接矩陣中的極大值*/voidDijkstra(intcost[][MAXVEX],intn,intv){intdist[MAXVEX],path[MAXVEX];ints[MAXVEX];intmindis,i,j,u,pre;for(i=0;i<n;i++){dist[i]=cost[v][i];/*初始化距離*/s[i]=0;/*輔助數(shù)組s[]置初值為0*/if(cost[v][i]<M)path[i]=v;elsepath[i]=-1;}返回到本節(jié)目錄s[v]=1;path[v]=0;for(i=0;i<n;i++){mindis=M;u=-1;for(j=0;j<n;j++)if(s[j]==0&&dist[j]<mindis){u=j;mindis=dist[j];}if(u!=-1){s[u]=1;for(j=0;j<n;j++)if(s[j]==0)if(cost[u][j]<M&&dist[u]+cost[u][j]<dist[j]){dist[j]=dist[u]+cost[u][j];path[j]=u;}}}返回到本節(jié)目錄printf("\nDijkstra算法求解如下：\n");for(i=0;i<n;i++){if(i!=v){printf("\n%d->%d:",v,i);if(s[i]==1){printf("路徑長(zhǎng)度為%2d,",dist[i]);pre=i;printf("路徑逆序?yàn)椋?);while(pre!=v){printf("%d,",pre);pre=path[pre];}printf("%d\n",pre);}elseprintf("不存在路徑\n");}}}返回到本節(jié)目錄6.7.2求每一對(duì)頂點(diǎn)之間的最短路徑1．弗洛伊德（Floyed）算法弗洛伊德（Floyed）