廣度優(yōu)先遍歷

廣度優(yōu)先遍歷廣度優(yōu)先遍歷廣度優(yōu)先遍歷第8章圖知識(shí)點(diǎn)圖的邏輯結(jié)構(gòu)及基本術(shù)語鄰接矩陣和鄰接表的存儲(chǔ)結(jié)構(gòu)和特點(diǎn)深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法圖的連通性和生成樹的概念最短路徑的含義及求最短路徑的算法通過閱讀報(bào)刊，我們能增長見識(shí)，擴(kuò)大自己的知識(shí)面。廣度優(yōu)先遍歷廣度優(yōu)先遍歷廣度優(yōu)先遍歷第8章圖知識(shí)點(diǎn)通1第8章圖知識(shí)點(diǎn)圖的邏輯結(jié)構(gòu)及基本術(shù)語鄰接矩陣和鄰接表的存儲(chǔ)結(jié)構(gòu)和特點(diǎn)深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法圖的連通性和生成樹的概念最短路徑的含義及求最短路徑的算法第8章圖知識(shí)點(diǎn)2難點(diǎn)圖的遍歷最小生成樹最短路徑要求熟練掌握以下內(nèi)容：圖的存儲(chǔ)結(jié)構(gòu)圖的遍歷算法了解以下內(nèi)容：圖的最小生成樹和求最小生成樹算法帶權(quán)有向圖的最短路徑問題難點(diǎn)3第8章目錄8-1圖的定義和術(shù)語8-2圖的存儲(chǔ)表示8-3圖的遍歷8-4圖的連通性8-5最短路徑8-6有向無環(huán)圖及其應(yīng)用小結(jié)驗(yàn)證性實(shí)驗(yàn)8圖子系統(tǒng)自主設(shè)計(jì)實(shí)驗(yàn)８最小生成樹單元練習(xí)8第8章目錄8-1圖的定義和術(shù)語4８-1

圖的定義和術(shù)語

圖（Graph）是一種比樹形結(jié)構(gòu)更復(fù)雜的非線性結(jié)構(gòu)。在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)都可以有多個(gè)直接前驅(qū)和多個(gè)直接后繼。８-1圖的定義和術(shù)語８-1-1圖的定義圖（Graph）是由非空的頂點(diǎn)（Vertices）集合和一個(gè)描述頂點(diǎn)之間關(guān)系——邊（Edges）的有限集合組成的一種數(shù)據(jù)結(jié)構(gòu)?？梢杂枚M定義為：

G＝（V，E）其中，G表示一個(gè)圖，V是圖G中頂點(diǎn)的集合，E是圖G中邊的集合。８-1圖的定義和術(shù)語圖（Graph）是一種比樹形結(jié)5

圖８-1無向圖G1

圖８-2有向圖G2

V1V3V2V4V5V1V3V2V4

G1=（V，E）

V＝{v1,v2,v3,v4,v5}；

E＝{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。(vi,vj)表示頂點(diǎn)vi和頂點(diǎn)vj之間有一條無向直接連線，也稱為邊。G2=(V,E)V={v1,v2,v3,v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}<vi,vj>表示頂點(diǎn)vi和頂點(diǎn)vj之間有一條有向直接連線，也稱為弧。其中vi稱為弧尾，vj稱為弧頭。圖８-1無向圖G1圖８-2有向圖6８-1-2圖的相關(guān)術(shù)語（1）無向圖（Undigraph）在一個(gè)圖中，如果每條邊都沒有方向（如圖８-1），則稱該圖為無向圖。（2）有向圖（Digraph）在一個(gè)圖中，如果每條邊都有方向（如圖８-2），則稱該圖為有向圖。（3）無向完全圖在一個(gè)無向圖中，如果任意兩頂點(diǎn)都有一條直接邊相連接，則稱該圖為無向完全圖?？梢宰C明，在一個(gè)含有n個(gè)頂點(diǎn)的無向完全圖中，有n(n-1)/2條邊。８-1-2圖的相關(guān)術(shù)語7（4）有向完全圖在一個(gè)有向圖中，如果任意兩頂點(diǎn)之間都有方向互為相反的兩條弧相連接，則稱該圖為有向完全圖。在一個(gè)含有n個(gè)頂點(diǎn)的有向完全圖中，有n(n-1)條弧。（5）稠密圖、稀疏圖我們稱邊數(shù)很多的圖為稠密圖；稱邊數(shù)很少的圖為稀疏圖。（6）頂點(diǎn)的度在無向圖中：一個(gè)頂點(diǎn)擁有的邊數(shù)，稱為該頂點(diǎn)的度。記為TD(v)。（4）有向完全圖8

在有向圖中：

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

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

(c)一個(gè)頂點(diǎn)度等于頂點(diǎn)的入度+出度，即：TD(v)=ID(v)＋OD(v)。在圖８-1的G1中有：

TD(v1)=2TD(v2)=3TD(v3)=3TD(v4)=2TD(v5)=2

在圖８

-2的G2中有：

ID(v1)=1OD(v1)=2TD(v1)=3ID(v2)=1OD(v2)=0TD(v2)=1ID(v3)=1OD(v3)=1TD(v3)=2ID(v4)=1OD(v4)=1TD(v4)=2在有向圖中：9

可以證明，對(duì)于具有n個(gè)頂點(diǎn)、e條邊的圖，頂點(diǎn)vi的度TD(vi)與頂點(diǎn)的個(gè)數(shù)以及邊的數(shù)目滿足關(guān)系：

（7）權(quán)圖的邊或弧有時(shí)具有與它有關(guān)的數(shù)據(jù)信息，這個(gè)數(shù)據(jù)信息就稱為權(quán)（Weight）。ACBD58697（8）網(wǎng)——邊（或?。┥蠋?quán)的圖稱為網(wǎng)（Network）。如圖８-3所示，就是一個(gè)無向網(wǎng)。如果邊是有方向的帶權(quán)圖，則就是一個(gè)有向網(wǎng)。圖８-3一個(gè)無向網(wǎng)示意可以證明，對(duì)于具有n個(gè)頂點(diǎn)、e條邊的圖，頂點(diǎn)vi的度10（9）路徑、路徑長度頂點(diǎn)vi到頂點(diǎn)vj之間的路徑是指頂點(diǎn)序列vi,vi1,vi2,

…,vim,vj.。其中，（vi,vi1），(vi1,vi2)，…,(vim,.vj)分別為圖中的邊。路徑上邊的數(shù)目稱為路徑長度。在圖８-1的無向圖G1中，v1→v4→v3→v5與v1→v2→v5是從頂點(diǎn)v1

到頂點(diǎn)v5

的兩條路徑，路徑長度分別為3和2。（10）回路、簡單路徑、簡單回路在一條路徑中，如果其起始點(diǎn)和終止點(diǎn)是同一頂點(diǎn)，則稱其為回路或者環(huán)。如果一條路徑上所有頂點(diǎn)除起始點(diǎn)和終止點(diǎn)外彼此都是不同的，則稱該路徑為簡單路徑。在圖８-1中，前面提到的v1到v5的兩條路徑都為簡單路徑。除起始點(diǎn)和終止點(diǎn)外，其他頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡單回路，或者簡單環(huán)。如圖８

-2中的v1→v3→v4→v1。（9）路徑、路徑長度11（11）子圖對(duì)于圖G=（V，E），G’=（V’，E’），若存在V’是V的子集，E’是E的子集，則稱圖G’是G的一個(gè)子圖。圖８-4(a)表示出了圖8-1無向圖G1的一個(gè)子圖，圖８-4(b)表示出了圖8-2有向圖G2的一個(gè)子圖。圖８-4圖G1和G2的兩個(gè)子圖示意(a)G1的子圖(b)G2的子圖V1V4V2V1V3V2V4V5（11）子圖圖８-4圖G1和G2的兩個(gè)子圖12（12）連通圖、連通分量在無向圖中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i≠j)有路徑，則稱頂點(diǎn)vi和vj是連通的。任意兩頂點(diǎn)都是連通的圖稱為連通圖。無向圖的極大連通子圖稱為連通分量。圖８-5(a)中有兩個(gè)連通分量，如圖８

-5(b)所示。AEBFCDAEBFCD(a)無向圖G3(b)G3的兩個(gè)連通分量

圖８-5無向圖及連通分量示意（12）連通圖、連通分量AEBFCDAEBFCD13（13）強(qiáng)連通圖、強(qiáng)連通分量對(duì)于有向圖來說，若圖中任意一對(duì)頂點(diǎn)vi

和vj(i≠j)均有從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj有路徑，也有從vj到vi的路徑，則稱該有向圖是強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。圖８-2中有兩個(gè)強(qiáng)連通分量，分別是{v1,v3,v4}和{v2}，如圖8-6所示。（14）生成樹連通圖G的一個(gè)子圖如果是一棵包含G的所有頂點(diǎn)的樹，則該子圖稱為G的生成樹（SpanningTree）。在生成樹中添加任意一條屬于原圖中的邊必定會(huì)產(chǎn)生回路，因?yàn)樾绿砑拥倪吺蛊渌栏降膬蓚€(gè)頂點(diǎn)之間有了第二條路徑。若生成樹中減少任意一條邊，則必然成為非連通的。n個(gè)頂點(diǎn)的生成樹具有n-1條邊。V1V3V2V4圖８-6有向圖G2的兩個(gè)強(qiáng)連通分量示意（13）強(qiáng)連通圖、強(qiáng)連通分量（14）生成樹V1V3V2V4圖148-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。

圖的存儲(chǔ)結(jié)構(gòu)比較多。對(duì)于圖的存儲(chǔ)結(jié)構(gòu)的選擇取決于具體的應(yīng)用和需要進(jìn)行的運(yùn)算。

下面介紹幾種常用的圖的存儲(chǔ)結(jié)構(gòu)。8-2

圖的存儲(chǔ)表示8-1-3圖的基本操作圖的存儲(chǔ)結(jié)構(gòu)比較多。對(duì)15

鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。假設(shè)圖G＝（V，E）有n個(gè)頂點(diǎn)，即V＝{v0,v1,…,vn-1}，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣：

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

A[i][j]=

0若(vi,vj)或<vi,vj>不是E(G)中的邊若G是網(wǎng)，則鄰接矩陣可定義為：

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

A[i][j]=0或∞若(vi,vj)或<vi,vj>不是E(G)中的邊其中，wij表示邊(vi,vj)或<vi,vj>上的權(quán)值（如圖7-3）；∞表示一個(gè)計(jì)算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。16

無向圖用鄰接矩陣表示如圖8-7所示；有向網(wǎng)用鄰接矩陣表示如圖8-8所示。圖8-7一個(gè)無向圖的鄰接矩陣表示圖8-8一個(gè)有向網(wǎng)的鄰接矩陣表示無向圖用鄰接矩陣表示如圖8-7所示；有向網(wǎng)用17

從圖的鄰接矩陣存儲(chǔ)具有以下性質(zhì)：（1）無向圖的鄰接矩陣一定是一個(gè)對(duì)稱矩陣。因此，在具體存放鄰接矩陣時(shí)只需存放上（或下）三角矩陣的元素即可。（2）對(duì)于無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的度TD(vi)。（3）對(duì)于有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的出度OD(vi)（或入度ID(vi)）。（4）用鄰接矩陣方法存儲(chǔ)圖，很容易確定圖中任意兩個(gè)頂點(diǎn)之間是否有邊相連；但是，要確定圖中有多少條邊，則必須按行、按列對(duì)每個(gè)元素進(jìn)行檢測，所花費(fèi)的時(shí)間代價(jià)很大。這是用鄰接矩陣存儲(chǔ)圖的局限性。從圖的鄰接矩陣存儲(chǔ)具有以下性質(zhì)：18圖的鄰接矩陣存儲(chǔ)的描述如下：#defineMAXLEN10typedefstruct{charvexs[MAXLEN];intedges[MAXLEN][MAXLEN];intn,e;}MGraph;建立一個(gè)有向圖的鄰接矩陣存儲(chǔ)的算法如下：

圖的鄰接矩陣存儲(chǔ)的描述如下：19voidCreateMGraph(MGraph&G){inti,j,k;charch1,ch2;printf("請輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為:頂點(diǎn)數(shù),邊數(shù)):\n");scanf("%d%d",&(G.n),&(G.e));printf("請輸入頂點(diǎn)信息(頂點(diǎn)標(biāo)志)每個(gè)頂點(diǎn)以回車作為結(jié)束:\n");for(i=0;i<G.n;i++){fflush(stdin);scanf("%c",&(G.vexs[i]));}for(i=0;i<G.n;i++)for(j=0;j<G.n;j++) G.edges[i][j]=0; //鄰接矩陣初始化

printf("請輸入每條邊所對(duì)應(yīng)的兩個(gè)頂點(diǎn)（先輸入弧尾，后輸入弧頭）!\n");for(k=0;k<G.e;k++){fflush(stdin);printf("請輸入第%d條邊的兩個(gè)頂點(diǎn)標(biāo)志(用逗號(hào)分隔)：",k+1);scanf("%c,%c",&ch1,&ch2);for(i=0;ch1!=G.vexs[i];i++); for(j=0;ch2!=G.vexs[j];j++) G.edges[i][j]=1;} //將輸入邊對(duì)應(yīng)的矩陣元素值設(shè)為1}voidCreateMGraph(MGraph&G)208-2-2鄰接表鄰接表(AdjacencyList)是圖的一種順序存儲(chǔ)與鏈?zhǔn)酱鎯?chǔ)結(jié)合的存儲(chǔ)方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對(duì)于圖G中的每個(gè)頂點(diǎn)vi，該方法將所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，這個(gè)單鏈表就稱為頂點(diǎn)vi的鄰接表。再將所有點(diǎn)的鄰接表表頭放到數(shù)組中，就構(gòu)成了圖的鄰接表。在鄰接表表示中有兩種結(jié)點(diǎn)結(jié)構(gòu)，如圖8-9所示。

圖8-9鄰接矩陣表示的結(jié)點(diǎn)結(jié)構(gòu)8-2-2鄰接表21

一種是頂點(diǎn)表的結(jié)點(diǎn)結(jié)構(gòu)，它由頂點(diǎn)域（vertex）和指向第一條鄰接邊的指針域（firstedge）構(gòu)成，另一種是邊表結(jié)點(diǎn)，它由鄰接點(diǎn)域(adjvex)和指向下一條鄰接邊的指針域(next)構(gòu)成。對(duì)于網(wǎng)的邊表需再增設(shè)一個(gè)存儲(chǔ)邊上信息（如權(quán)值等）的域（info），網(wǎng)的邊表結(jié)構(gòu)如圖8-10所示。

圖8-10網(wǎng)的邊表結(jié)構(gòu)一種是頂點(diǎn)表的結(jié)點(diǎn)結(jié)構(gòu)，它由頂點(diǎn)域（vert22

圖8-11給出無向圖8-7對(duì)應(yīng)的鄰接表表示。

圖8-11圖8-7無向圖的鄰接表表示鄰接表表示形式描述如下：圖8-11給出無向圖8-7對(duì)應(yīng)的鄰接表表示。圖8-23＃defineMAXLEN10//最大頂點(diǎn)數(shù)為10typedefstructedgenode{intadjvex; //鄰接頂點(diǎn)的下標(biāo)

structedgenode*next;//指向下一個(gè)鄰接邊結(jié)點(diǎn)的指針}EdgeNode; //定義邊結(jié)點(diǎn)類型typedefstruct{VertexTypevertex;//頂點(diǎn)標(biāo)志

EdgeNode*firstedge;//保存第一個(gè)邊結(jié)點(diǎn)地址的指針}VertexNode; //定義頂點(diǎn)結(jié)點(diǎn)類型typedefstruct{VertexNodeadjlist[MAXLEN];//頂點(diǎn)數(shù)組

intn,e;//頂點(diǎn)數(shù)和邊數(shù)}ALGraph;//定義鄰接表的類型名ALGraph＃defineMAXLEN1024voidCreateGraphAL(ALGraph&G)//有向圖的鄰接表存儲(chǔ)算法{inti,k;EdgeNode*s;charArcTail,ArcHead; //保存弧尾、弧頭標(biāo)志

intTailPoi,HeadPoi;//保存弧尾、弧頭下標(biāo)

printf("請輸入頂點(diǎn)數(shù)和邊數(shù)(輸入格式為:頂點(diǎn)數(shù),邊數(shù))：\n");scanf("%d%d",&(G.n),&(G.e)); //讀入頂點(diǎn)數(shù)和邊數(shù)

printf("請輸入頂點(diǎn)信息(輸入格式為:頂點(diǎn)號(hào)<CR>)以回車作為結(jié)束:\n");for(i=0;i<G.n;i++)//建立有n個(gè)頂點(diǎn)的頂點(diǎn)表

{scanf("%c",&(G.adjlist[i].vertex));//輸入頂點(diǎn)信息

G.adjlist[i].firstedge=NULL;}//指向第一個(gè)邊結(jié)點(diǎn)的指針設(shè)為空

printf("請輸入邊的信息(輸入格式為:弧尾,弧頭)：\n"); for(k=0;k<G.e;k++) //建立邊表

{scanf(“%c,%c”,&ArcTail,&ArcHead);for(i=0;i<G.n;i++)//查找弧尾和弧頭頂點(diǎn)的下標(biāo)

{if(G.adjlist[i].vertex==ArcTail) TailPoi=i; if(G.adjlist[i].vertex==ArcHead) HeadPoi=i;} s=newEdgeNode; //給新邊結(jié)點(diǎn)開辟空間

s->adjvex=HeadPoi;//構(gòu)造新邊結(jié)點(diǎn)

s->next=G.adjlist[TailPoi].firstedge; G.adjlist[i].firstedge=s;}}voidCreateGraphAL(ALGraph&G25

若無向圖中有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表需n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。顯然，在邊稀疏(e<<n(n-1)/2)的情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲(chǔ)空間，當(dāng)和邊相關(guān)的信息較多時(shí)更是如此。在無向圖的鄰接表中，頂點(diǎn)vi的度恰為第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)；但在有向圖中，第i個(gè)鏈表中的結(jié)點(diǎn)個(gè)數(shù)只是頂點(diǎn)vi的出度。如果要求入度，則必須遍歷整個(gè)鄰接表才能得到結(jié)果。有時(shí)，為了便于確定頂點(diǎn)的入度或以頂點(diǎn)vi為頭的弧，可以建立一個(gè)有向圖的逆鄰接表，即對(duì)每個(gè)頂點(diǎn)vi

建立一個(gè)鏈接，以vi為弧頭的弧的鏈表。例如圖8-12所示為有向圖G2（見圖8-2）的鄰接表和逆鄰接表。若無向圖中有n個(gè)頂點(diǎn)、e條邊，則它的鄰接表26

在建立鄰接表或逆鄰接表時(shí)，若輸入的頂點(diǎn)信息即為頂點(diǎn)的編號(hào)，則建立鄰接表的復(fù)雜度為O（n+e），否則，需要通過查找才能得到頂點(diǎn)在圖中位置，則時(shí)間復(fù)雜度為O（n*e）。

圖8-12圖8-8有向網(wǎng)的鄰接表和逆鄰接表在建立鄰接表或逆鄰接表時(shí)，若輸入的頂點(diǎn)信息即為頂點(diǎn)的278.2.3十字鏈表由于鄰接表中通過某頂點(diǎn)查找以該頂點(diǎn)為弧尾的弧結(jié)點(diǎn)很方便，但是通過該頂點(diǎn)查找以其為弧頭的弧結(jié)點(diǎn)則需要遍歷整個(gè)鄰接表；而逆鄰接表在查找弧結(jié)點(diǎn)方面的優(yōu)缺點(diǎn)則剛好與鄰接表相反。為了通過某頂點(diǎn)能夠方便地同時(shí)查找到以該頂點(diǎn)為弧尾和弧頭的弧結(jié)點(diǎn)，可以將鄰接表和逆鄰接表合并，這樣就構(gòu)成了有向圖的十字鏈表存儲(chǔ)結(jié)構(gòu)。十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)如圖所示：圖8-13十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)8.2.3十字鏈表圖8-13十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)28十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義如下：#defineMAXLEN20typedefstructarcnode{intTailVex,HeadVex;//弧尾和弧頭頂點(diǎn)的下標(biāo)

structarcnode*TLink,*HLink;//指向同弧尾和同弧頭的下一個(gè)弧結(jié)點(diǎn)的指針

intweight;//弧的權(quán)值信息}ArcNode; //定義弧結(jié)點(diǎn)的類型typedefstructvexnode{charvertex; //頂點(diǎn)標(biāo)志

ArcNode*FirstIn,*FirstOut;//指向第一個(gè)弧頭結(jié)點(diǎn)和弧尾結(jié)點(diǎn)的指針}VexNode;//定義頂點(diǎn)結(jié)點(diǎn)的類型typedefstruct{VexNodelist[MAXLEN];//頂點(diǎn)數(shù)組

intVexNum,ArcNum;//頂點(diǎn)數(shù)和弧數(shù)}OLGraph; //定義十字鏈表的類型十字鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義如下：29圖8-8所示有向網(wǎng)的十字鏈表存儲(chǔ)結(jié)構(gòu)如圖8-14所示。圖8-14有向圖的十字鏈表結(jié)構(gòu)創(chuàng)建十字鏈表的算法如下：圖8-8所示有向網(wǎng)的十字鏈表存儲(chǔ)結(jié)構(gòu)如圖8-14所示。圖8-30voidCreateOrthList(OLGraph&G){ArcNode*p;inti,j;charArcTail,ArcHead;charArcTail,ArcHead;printf("請輸入有向網(wǎng)的頂點(diǎn)數(shù)和弧數(shù):\n");scanf("%d%d",&G.VexNum,&G.ArcNum);printf("請依次輸入%d個(gè)頂點(diǎn)(用回車分隔):\n",G.VexNum);for(i=0;i<graph->vexnum;i++){scanf("%c",&G.list[i].vertex); //輸入頂點(diǎn)標(biāo)志

G.list[i].FirstIn=NULL; //初始化弧結(jié)點(diǎn)指針

G.list[i].FirstOut=NULL;}printf("頂點(diǎn)數(shù)組創(chuàng)建成功！\n");voidCreateOrthList(OLGraph&G31voidCreateOrthList(OLGraph&G){ArcNode*p;inti,j;charArcTail,ArcHead;charArcTail,ArcHead;printf("請輸入有向網(wǎng)的頂點(diǎn)數(shù)和弧數(shù):\n");scanf("%d%d",&G.VexNum,&G.ArcNum);printf("請依次輸入%d個(gè)頂點(diǎn)(用回車分隔):\n",G.VexNum);for(i=0;i<graph->vexnum;i++){scanf("%c",&G.list[i].vertex); //輸入頂點(diǎn)標(biāo)志

G.list[i].FirstIn=NULL; //初始化弧結(jié)點(diǎn)指針

G.list[i].FirstOut=NULL;}printf("頂點(diǎn)數(shù)組創(chuàng)建成功！\n");}voidCreateOrthList(OLGraph&G32

類似于有向圖（或網(wǎng)）的十字鏈表存儲(chǔ)結(jié)構(gòu)，無向圖（或網(wǎng)）還有一種鄰接多重表（AdjacencyMultiList）的存儲(chǔ)結(jié)構(gòu)。雖然鄰接表是無向圖的一種很有效的存儲(chǔ)結(jié)構(gòu)，但是，在無向圖的鄰接表結(jié)構(gòu)中，每條邊都存在兩個(gè)頂點(diǎn)，并且這兩個(gè)頂點(diǎn)分別位于兩個(gè)鏈表中，這給無向圖的某些操作帶來了不便。例如，在某些圖的問題中需要對(duì)某條邊進(jìn)行某種操作，如插入或刪除一條邊等，此時(shí)都必須找到表示同一條邊的兩個(gè)邊結(jié)點(diǎn)，并分別對(duì)其操作，這樣顯得比較繁瑣。因此，在處理和邊有關(guān)的大量問題中，更多的時(shí)候鄰接多重表比鄰接表顯得更為合適。鄰接多重表的每條邊都用一個(gè)邊結(jié)點(diǎn)表示，其邊結(jié)點(diǎn)和頂點(diǎn)結(jié)點(diǎn)的結(jié)構(gòu)分別如圖8-15中的(a)(b)所示。圖8-15鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu)類似于有向圖（或網(wǎng)）的十字鏈表存儲(chǔ)結(jié)構(gòu)，無向33鄰接多重表的類型定義如下：#defineMAXLEN20typedefstructedgenode{intiVex,jVex; //邊兩端頂點(diǎn)的下標(biāo)

structedgenode*iLink,*jLink;//指向具有相同端點(diǎn)的下一個(gè)邊結(jié)點(diǎn)的指針

intweight;//邊的權(quán)值信息}EdgeNode; //定義邊結(jié)點(diǎn)的類型typedefstructvexnode{charvertex; //頂點(diǎn)標(biāo)志

ArcNode*FirstEdge;//指向第一個(gè)鄰接邊結(jié)點(diǎn)的指針}VexNode; //定義頂點(diǎn)結(jié)點(diǎn)的類型typedefstruct{VexNodelist[MAXLEN]; //頂點(diǎn)數(shù)組intVexNum,EdgeNum;//頂點(diǎn)數(shù)和邊數(shù)}AMLGraph; //定義鄰接多重表的類型鄰接多重表的類型定義如下：34８-3

圖的遍歷

圖的遍歷（traversinggraph）是指從圖中的某一頂點(diǎn)出發(fā)，對(duì)圖中的所有頂點(diǎn)訪問一次，而且僅訪問一次。圖的遍歷是圖的一種基本操作。由于圖結(jié)構(gòu)本身的復(fù)雜性，所以圖的遍歷操作也較復(fù)雜，主要表現(xiàn)在以下四個(gè)方面：（1）在圖結(jié)構(gòu)中，每一個(gè)結(jié)點(diǎn)的地位都是相同的，沒有一個(gè)“自然”的首結(jié)點(diǎn)，圖中任意一個(gè)頂點(diǎn)都可作為訪問的起始結(jié)點(diǎn)。（2）在非連通圖中，從一個(gè)頂點(diǎn)出發(fā)，只能夠訪問它所在的連通分量上的所有頂點(diǎn)，因此，還需考慮如何訪問圖中其余的連通分量。（3）在圖結(jié)構(gòu)中，如果有回路存在，那么一個(gè)頂點(diǎn)被訪問之后，有可能沿回路又回到該頂點(diǎn)。（4）在圖中，一個(gè)頂點(diǎn)可以和其它多個(gè)頂點(diǎn)相連，當(dāng)這個(gè)頂點(diǎn)訪問過后，就要考慮如何選取下一個(gè)要訪問的頂點(diǎn)。８-3圖的遍歷圖的遍歷（traversing35８-3-1深度優(yōu)先搜索

深度優(yōu)先搜索（Depth-FisrstSearch）遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)未曾被訪問，則深度優(yōu)先搜索可從圖中某個(gè)頂點(diǎn)發(fā)v出發(fā)，首先訪問此頂點(diǎn)，然后任選一個(gè)v的未被訪問的鄰接點(diǎn)w出發(fā)，繼續(xù)進(jìn)行深度優(yōu)先搜索，直到圖中所有和v路徑相通的頂點(diǎn)都被訪問到；若此時(shí)圖中還有頂點(diǎn)未被訪問到，則另選一個(gè)未被訪問的頂點(diǎn)作為起始點(diǎn)，重復(fù)上面的做法，直至圖中所有的頂點(diǎn)都被訪問。V1V5V2V4V8V3V6V7圖８-16無向圖G5

以圖８-16的無向圖G5為例，其深度優(yōu)先搜索得到的頂點(diǎn)訪問序列為：v1→v2→v4→v8→v5→v3

→v6

、→v7動(dòng)畫演示８-3-1深度優(yōu)先搜索V1V5V2V4V8V3V6V7圖８36

顯然，以上方法是一個(gè)遞歸的過程。為了在遍歷過程中便于區(qū)分頂點(diǎn)是否已被訪問，需附設(shè)訪問標(biāo)志數(shù)組visited[0:n-1],，其初值為FALSE，一旦某個(gè)頂點(diǎn)被訪問，則其相應(yīng)的分量置為TRUE。從圖的某一點(diǎn)v出發(fā)，遞歸地進(jìn)行深度優(yōu)先遍歷的過程如下面算法所示。

voidDFSTraverseM(MGraph*G)

{inti;

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

visited[i]=FALSE;//FALSE在c語言中定義為0，下同

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

if(!visited[i])

DFSM(G,i);

}顯然，以上方法是一個(gè)遞歸的過程。為了在遍歷過程37voidDFSM(MGraph*G,inti){intj;printf("\t\t深度優(yōu)先遍歷結(jié)點(diǎn):結(jié)點(diǎn)%c\n",G->vexs[i]);visited[i]=TRUE; //TRUE在c語言中定義為1，以下同

for(j=0;j<G->n;j++)if(G->edges[i][j]==1&&!visited[j]) DFSM(G,j);}

在遍歷時(shí)，對(duì)圖中每個(gè)頂點(diǎn)至多調(diào)用一次DFSM函數(shù)，因?yàn)橐坏┠硞€(gè)頂點(diǎn)被標(biāo)志成已被訪問，就不再從它出發(fā)進(jìn)行搜索。因此，遍歷圖的過程實(shí)質(zhì)上是對(duì)每個(gè)頂點(diǎn)查找其鄰接點(diǎn)的過程。其耗費(fèi)的時(shí)間則取決于所采用的存儲(chǔ)結(jié)構(gòu)。當(dāng)用二維數(shù)組表示鄰接矩陣圖的存儲(chǔ)結(jié)構(gòu)時(shí)，查找每個(gè)頂點(diǎn)的鄰接點(diǎn)所需時(shí)間為O(n2)，其中n為圖中頂點(diǎn)數(shù)。voidDFSM(MGraph*G,inti)38

當(dāng)以鄰接表作圖的存儲(chǔ)結(jié)構(gòu)時(shí)，找鄰接點(diǎn)所需時(shí)間為O(e)，其中e為無向圖中邊的數(shù)或有向圖中弧的數(shù)。由此，當(dāng)以鄰接表作存儲(chǔ)結(jié)構(gòu)時(shí)，深度優(yōu)先遍歷的時(shí)間復(fù)雜度為O(n+e)。８-3-2廣度優(yōu)先搜索廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷。假設(shè)從圖中某頂點(diǎn)vi出發(fā)，在訪問了vi之后依次訪問vi的各個(gè)未曾訪問過的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問它們的鄰接點(diǎn)，并使“先被訪問的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接點(diǎn)”被訪問，直至圖中所有已被訪問的頂點(diǎn)的鄰接點(diǎn)都被訪問到。若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。當(dāng)以鄰接表作圖的存儲(chǔ)結(jié)構(gòu)時(shí)，找鄰接點(diǎn)所需時(shí)間為O(e39

對(duì)圖８-16無向圖進(jìn)行廣度優(yōu)先遍歷，首先訪問v1

和v1的鄰接點(diǎn)v2和v3，然后依次訪問v2

的鄰接點(diǎn)v4

和v5

及v3

的鄰接點(diǎn)v6和v7，最后訪問v4

的鄰接點(diǎn)v8。由于這些頂點(diǎn)的鄰接點(diǎn)均已被訪問，并且圖中所有頂點(diǎn)都被訪問，由些完成了圖的遍歷。得到的頂點(diǎn)訪問序列為：

v1→v2→v3→v4→v5→v6→v7→v8

和深度優(yōu)先搜索類似，在遍歷的過程中也需要一個(gè)訪問標(biāo)志數(shù)組。并且，為了順次訪問路徑長度為2、3、…的頂點(diǎn)，需附設(shè)隊(duì)列以存儲(chǔ)已被訪問的路徑長度為1、2、…的頂點(diǎn)。V1V5V2V4V8V3V6V7圖８-16無向圖G5

動(dòng)畫演示對(duì)圖８-16無向圖進(jìn)行廣度優(yōu)先遍歷，首先訪40

從圖的某一點(diǎn)v出發(fā)，遞歸地進(jìn)行廣度優(yōu)先遍歷的過程如下面的算法所示。

voidBFSTraverseM(MGraph*G){inti;for(i=0;i<G->n;i++)visited[i]=FALSE;for(i=0;i<G->n;i++)if(!visited[i])BFSM(G,i);}從圖的某一點(diǎn)v出發(fā)，遞歸地進(jìn)行廣度優(yōu)先遍歷的過程如下面41voidBFSM(MGraph*G,intk){inti,j;CirQueueQ;InitQueue(&Q);printf("廣度優(yōu)先遍歷結(jié)點(diǎn):結(jié)點(diǎn)%c\n",G->vexs[k]);visited[k]=TRUE;EnQueue(&Q,k);while(!QueueEmpty(&Q)){i=DeQueue(&Q);for(j=0;j<G->n;j++)if(G->edges[i][j]==1&&!visited[j]){printf("廣度優(yōu)先遍歷結(jié)點(diǎn):%c\n",G->vexs[j]);visited[j]=TRUE;EnQueue(&Q,j);}}}voidBFSM(MGraph*G,intk)42８-4

圖的連通性

分析上述算法，每個(gè)頂點(diǎn)至多進(jìn)一次隊(duì)列。遍歷圖的過程實(shí)質(zhì)是通過邊或弧找鄰接點(diǎn)的過程，因此廣度優(yōu)先搜索遍歷圖和深度優(yōu)先搜索遍歷的時(shí)間復(fù)雜度是相同的，兩者不同之處僅僅在于對(duì)頂點(diǎn)訪問的順序不同。

判定一個(gè)圖的連通性是圖的一個(gè)應(yīng)用問題，我們可以利用圖的遍歷算法來求解這一問題。本節(jié)將討論無向圖的連通性問題，并討論最小代價(jià)生成樹等問題。８-4圖的連通性分析上述算法，每個(gè)頂點(diǎn)至多43８-4-1無向圖的連通分量和生成樹

在對(duì)無向圖進(jìn)行遍歷時(shí)，對(duì)于連通圖，僅需從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有頂點(diǎn)。對(duì)非連通圖，則需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行搜索，而每一次從一個(gè)新的起始點(diǎn)出發(fā)進(jìn)行搜索過程中得到的頂點(diǎn)訪問序列恰為其各個(gè)連通分量中的頂點(diǎn)集。例如，圖８-17(a)是一個(gè)非連通圖，按照圖８-17(b)所示的鄰接表進(jìn)行深度優(yōu)先搜索遍歷

圖８-17(a)非連通圖圖８-17(b)G6的鄰接表AEBFCD８-4-1無向圖的連通分量和生成樹圖８-17(a)非44

兩次調(diào)用DFS過程（即分別從頂點(diǎn)A和D出發(fā)），得到的頂點(diǎn)訪問序列為：ABFECE

這兩個(gè)頂點(diǎn)集分別加上所有依附于這些頂點(diǎn)的邊，便構(gòu)成了非連通圖G3的兩個(gè)連通分量。

因此，要想判定一個(gè)無向圖是否為連通圖，或有幾個(gè)連通分量，就可設(shè)一個(gè)計(jì)數(shù)變量count，初始時(shí)取值為0，在深度優(yōu)先搜索算法循環(huán)中，每調(diào)用一次DFS，就給count增1。這樣，當(dāng)整個(gè)算法結(jié)束時(shí)，依據(jù)count的值，就可確定圖的連通性了。

設(shè)E(G)為連通圖G中所有邊的集合，則從圖中任一頂點(diǎn)出發(fā)遍歷圖時(shí)，必定將E(G)分成兩個(gè)集合T(G)和B(G)，其中T(G)是遍歷圖過程中歷經(jīng)的邊的集合；B(G)是剩余的邊的集合。顯然，T(G)和圖G中所有頂點(diǎn)一起構(gòu)成連通圖G的極小連通子圖。兩次調(diào)用DFS過程（即分別從頂點(diǎn)A和D出發(fā)45

按照８-1-2節(jié)的定義，它是連通圖的一棵生成樹，并且由深度優(yōu)先搜索得到的為深度優(yōu)先生成樹；由廣度優(yōu)先搜索得到的為廣度優(yōu)先生成樹。例如，圖８-18(a)和(b)所示分別為圖８-16連通圖G5的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖中虛線為集合B(G)中的邊，實(shí)線為集合T(G)中的邊。圖８-18(a)G5的深度優(yōu)先生成樹圖８-18(b)G5的廣度優(yōu)先生成樹V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7按照８-1-2節(jié)的定義，它是連通圖的一棵生成樹，并且由46

對(duì)于非連通圖，通過這樣的遍歷，將得到的是生成森林。例如，圖８-19(b)所示為圖８-19(a)的深度優(yōu)先生成的森林，它由三棵深度優(yōu)先生成樹組成。圖８-19(a)非連通無向圖G６圖８-19(b)G６的深度優(yōu)先生成樹林JHKLMAICFGBDEJHKLMAICFGBDE對(duì)于非連通圖，通過這樣的遍歷，將得到的是生成森林。例如47８-4-2最小生成樹1．最小生成樹的基本概念由生成樹的定義可知，無向連通圖的生成樹不一定是唯一的。連通圖的一次遍歷所經(jīng)過的邊的集合及圖中所有頂點(diǎn)的集合就構(gòu)成了該圖的一棵生成樹，對(duì)連通圖的不同遍歷，就可能得到不同的生成樹。圖８-20(a)、(b)和(c)所示的均為圖８-16的無向連通圖G5的生成樹。V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7

圖８-17無向連通圖G5的三棵生成樹（a）（b）（c）８-4-2最小生成樹V1V5V2V4V8V3V6V7V148

可以證明，對(duì)于有n個(gè)頂點(diǎn)的無向連通圖，無論其生成樹的形態(tài)如何，所有生成樹中都有且僅有n-1條邊。如果無向連通圖是一個(gè)網(wǎng)，那么，它的所有生成樹中必有一棵邊的權(quán)值之和為最小的生成樹，簡稱為最小生成樹。最小生成樹的概念可以應(yīng)用到許多實(shí)際問題中。例如有這樣一個(gè)問題：以盡可能抵的總造價(jià)建造城市間的通訊網(wǎng)絡(luò)，把十個(gè)城市聯(lián)系在一起。在這十個(gè)城市中，任意兩個(gè)城市之間都可以建造通訊線路，通訊線路的造價(jià)依據(jù)城市間的距離不同而有不同的造價(jià)，可以構(gòu)造一個(gè)通訊線路造價(jià)網(wǎng)絡(luò)，在網(wǎng)絡(luò)中，每個(gè)頂點(diǎn)表示城市，頂點(diǎn)之間的邊表示城市之間可構(gòu)造通訊線路，每條邊的權(quán)值表示該條通訊線路的造價(jià)，要想使總的造價(jià)最低，實(shí)際上就是尋找該網(wǎng)絡(luò)的最小生成樹?？梢宰C明，對(duì)于有n個(gè)頂點(diǎn)的無向連通圖，無論其492．常用的構(gòu)造最小生成樹的方法（1）構(gòu)造最小生成樹的Prim算法假設(shè)G＝（V，E）為一連通網(wǎng)，頂點(diǎn)集V={v1，v2，…，vn}，E為網(wǎng)中所有帶權(quán)邊的集合。設(shè)置兩個(gè)新的集合U和T，其中集合U用于存放G的最小生成樹中的頂點(diǎn)，集合T存放G的最小生成樹中的邊。令集合U的初值為U＝{v1}（假設(shè)構(gòu)造最小生成樹時(shí)，從頂點(diǎn)v1出發(fā)），集合T的初值為T＝{}。

Prim算法的基本思想：從所有u∈U，v∈V－U的邊中，選取具有最小權(quán)值的邊（u，v），將頂點(diǎn)v加入集合U中，將邊（u，v）加入集合T中，如此不斷重復(fù)，直到U＝V時(shí)，最小生成樹構(gòu)造完畢，這時(shí)集合T中包含了最小生成樹的所有邊。圖８-21(a)所示的一個(gè)網(wǎng)，按照Prim方法，從頂點(diǎn)A出發(fā)，該網(wǎng)的最小生成樹的產(chǎn)生過程如圖８-21(b)、(c)、(d)、(e)、(f)所示。2．常用的構(gòu)造最小生成樹的方法50圖８-21Prim算法構(gòu)造最小生成樹的過程示意圖

AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)6812141617515666668888812121214145圖８-21Prim算法構(gòu)造最小生成樹的過程示意圖AE51（2）構(gòu)造最小生成樹的Kruskal算法

Kruskal算法是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。其基本思想是：首先選取全部的n個(gè)頂點(diǎn)，將其看成n個(gè)連通分量；然后按照網(wǎng)中邊的權(quán)值由小到大的順序，不斷選取當(dāng)前未被選取的邊集中權(quán)值最小的邊。依據(jù)生成樹的概念，n個(gè)結(jié)點(diǎn)的生成樹，有n-1條邊，故反復(fù)上述過程，直到選取了n-1條邊為止，就構(gòu)成了一棵最小生成樹。圖8－22為Kruskal算法構(gòu)造最小生成樹的過程示意圖。（2）構(gòu)造最小生成樹的Kruskal算法52圖８-22Kruskal算法構(gòu)造最小生成樹的過程示意圖

AEBFCDAEBFCDAEBFCDAEBFCDAEBFCDAEBFCD(a)(b)(c)(d)(e)(f)68121416175155666688885121255145圖８-22Kruskal算法構(gòu)造最小生成樹的過程示意圖53８-5

最短路徑

最短路徑問題是圖的又一個(gè)比較典型的應(yīng)用問題。例如，某一地區(qū)的一個(gè)交通網(wǎng)，給定了該網(wǎng)內(nèi)的n個(gè)城市以及這些城市之間的相通公路的距離，問題是如何在城市A和城市B之間找一條最近的通路。如果將城市用頂點(diǎn)表示，城市間的公路用邊表示，公路的長度則作為邊的權(quán)值，那么，這個(gè)問題就可歸結(jié)為在網(wǎng)中，求點(diǎn)A到點(diǎn)B的所有路徑中，邊的權(quán)值之和最短的那一條路徑。這條路徑就稱為兩點(diǎn)之間的最短路徑，并稱路徑上的第一個(gè)頂點(diǎn)為源點(diǎn)（Sourse），最后一個(gè)頂點(diǎn)為終點(diǎn)（Destination）。在不帶權(quán)的圖中，最短路徑是指兩點(diǎn)之間經(jīng)歷的邊數(shù)最少的路徑。例如在圖８-23中，設(shè)V1為源點(diǎn)，則從V1出發(fā)的路徑有（括號(hào)里為路徑長度）：８-5最短路徑最短路徑問題是圖的又一個(gè)54V1到V2的路徑有條：V1→V2(20)V1到V3的路徑有條：V1→V3(15),V1→V2→V3(55)V1到V4的路徑有條：V1→V2→V4(30),V1→V3→V4(45),V1→V2→V3→V4(85)V1到V5的路徑有條：V1→V2→V3→V5(65),V1→V3→V5(25)選出V1到其它各頂點(diǎn)的最短路徑，并按路徑長度遞增順序排列如下：V1→V3(15)，V1→V2(20)，V1→V3→V5(25)，V1→V2→V4(30)。

圖８-23V1

出發(fā)的路徑V1V5V2V4V3201035101530V1到V2的路徑有條：V1→V2(20)圖８-23V1出55

從上面的序列中，可以看出一個(gè)規(guī)律：按路徑長度遞增順序生成從源點(diǎn)到其它各頂點(diǎn)的最短路徑時(shí)，當(dāng)前正生成的最短路徑上除終點(diǎn)外，其它頂點(diǎn)的最短路徑已經(jīng)生成。迪杰斯特拉算法正是根據(jù)此規(guī)律得到的。迪杰斯特拉（Dijkstra）算法的基本思想：設(shè)置兩個(gè)頂點(diǎn)集S和T，S中存放已確定最短路徑的頂點(diǎn)，T中存放待確定最短路徑的頂點(diǎn)。初始時(shí)S中僅有一個(gè)源點(diǎn)，T中含除源點(diǎn)外其余頂點(diǎn)，此時(shí)各頂點(diǎn)的當(dāng)前最短長度為源點(diǎn)到該頂點(diǎn)的弧上的權(quán)值。接著選取T中當(dāng)前最短路徑長度最小的一個(gè)頂點(diǎn)v加入S，然后修改T中剩余頂點(diǎn)的當(dāng)前最短路徑長度，修改原則是：當(dāng)v的最短路徑長度與v到T中頂點(diǎn)之間的權(quán)值之和小于該頂點(diǎn)的當(dāng)前最短路徑長度時(shí)，用前者替換后者。重復(fù)以上過程，直到S中包含所有頂點(diǎn)為止，其過程如圖8－２4。

從上面的序列中，可以看出一個(gè)規(guī)律：按路徑長度遞增順序56圖８-24用迪杰斯特拉算法求有向圖的最短路徑過程

V1V5V2V4V3201035101530V1V5V2V4V32015V1V5V2V4V320101530V1V5V2V4V320101530V1V5V2V4V32010153010圖８-24用迪杰斯特拉算法求有向圖的最短路徑過程V1V557迪杰斯特拉算法求最短路徑的過程描述如下：#defineINFINITY99999#defineMAXLEN20typedefboolPathMatrix[MAXLEN][MAXLEN];typedefintShortPathTable[MAXLEN];voidShortestPath(MGraphG,intv0,PathMatrix&P,ShortPathTable&D){for(v=0;v<G.VexNum;v++){final[v]=False; //初始化S集合為空

for(w=0;w<G.VexNum;w++) //初始化最短路徑矩陣P P[v][w]=False;//沒有存儲(chǔ)任何最短路徑，所以全部元素均為False D[v]=G.arcs[v0][v];//初始的最短路徑長度設(shè)置為v0到相應(yīng)頂點(diǎn)弧的權(quán)值

if(D[v]<INFINITY)//若v0到頂點(diǎn)v的弧存在，則在P中設(shè)置好相應(yīng)路徑

{P[v][v0]=True;P[v][v]=True; }}迪杰斯特拉算法求最短路徑的過程描述如下：58

D[v0]=0;//設(shè)置v0到自身的最短路徑為0final[v0]=True; //將頂點(diǎn)v0加入到已選取頂點(diǎn)集合S中

for(i=1;i<G.VexNum;i++) { min=INFINITY;

for(w=0;w<G.VexNum;w++)//查找尚未加入到集合S中，并且?guī)?/p>

//權(quán)路徑長度最小的最短路徑終

//點(diǎn)，該終點(diǎn)的下標(biāo)保存在v中

if(!final[w]&&D[w]<min)//更新v的值

{v=w;min=D[w];} final[v]=True;//將頂點(diǎn)v加入到已選取頂點(diǎn)集合S中

for(w=0;w<G.VexNum;w++)//更新當(dāng)前最短帶權(quán)路徑長度

//向量D及路徑矩陣P if(!final[w]&&min+G.arcs[v][w]<D[w]) {D[w]=min+G.arcs[v][w]; P[w]=P[v]; P[w][w]=True;} }}D[v0]=0;59如圖8-25所示的有向網(wǎng)中，從頂點(diǎn)A到其余各頂點(diǎn)的最短路徑如表8-1所示。圖8-25有向網(wǎng)表8-1頂點(diǎn)A到其它頂點(diǎn)的最短路徑如圖8-25所示的有向網(wǎng)中，從頂點(diǎn)A到其余各頂點(diǎn)的最短路徑如60

以圖8-25所示的有向網(wǎng)為實(shí)例，迪杰斯特拉算法求解該網(wǎng)中從源點(diǎn)A到其余各頂點(diǎn)最短路徑的過程如圖8-26所示。圖8-26迪杰斯特拉算法的求解過程以圖8-25所示的有向網(wǎng)為實(shí)例，迪杰斯特拉算618.6有向無環(huán)圖及其應(yīng)用一個(gè)不存在環(huán)的有向圖稱為有向無環(huán)圖（DirectedAcyclineGraph，簡稱為DAG圖）。有向無環(huán)圖可用于描述某項(xiàng)工程的進(jìn)行過程。除最簡單的情況之外，幾乎所有工程都可分為若干個(gè)稱作活動(dòng)的子工程，而這些子工程之間，通常受著一定條件的約束，如其中某些子工程的開始必須在另一些子工程完成之后。對(duì)于整個(gè)工程，人們往往最關(guān)心兩個(gè)方面的問題：一是工程能否順利進(jìn)行；二是估算整個(gè)工程完成所必須的最短時(shí)間。其中前一個(gè)問題就是有向圖能否拓?fù)渑判虻膯栴}，后一個(gè)問題則和關(guān)鍵路徑有關(guān)，下面分別討論之。8.6有向無環(huán)圖及其應(yīng)用628.6.1拓?fù)渑判蛲負(fù)渑判蚴怯邢驁D的一個(gè)重要操作。在給定的有向圖G中，若頂點(diǎn)序列滿足下列條件：若在有向圖G中從頂點(diǎn)到頂點(diǎn)有一條路徑，則在序列中頂點(diǎn)必在頂點(diǎn)之前，便稱這個(gè)序列為一個(gè)拓?fù)湫蛄?。求一個(gè)有向圖拓?fù)湫蛄械倪^程稱為拓?fù)渑判颍═opologicalSort），實(shí)質(zhì)上，拓?fù)渑判蛴赡硞€(gè)集合上的偏序關(guān)系得到該集合上的一個(gè)全序關(guān)系的過程。在離散數(shù)學(xué)課程中關(guān)于偏序關(guān)系和全序關(guān)系有如下定義：若集合S上的關(guān)系R是自反的、反對(duì)稱的和傳遞的，則稱R是集合S上的偏序關(guān)系。設(shè)R是集合S上的偏序（PartialOrder），如果對(duì)每個(gè)必有xRy或yRx，則稱R是集合S上的全序關(guān)系。直觀地看，偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。8.6.1拓?fù)渑判?3

圖8-27表示偏序和全序關(guān)系的有向圖，假設(shè)圖中弧<x,y>表示的關(guān)系為x≤y，則（a）表示偏序關(guān)系，（b）表示全序關(guān)系。（a）圖之所以為偏序關(guān)系，是因?yàn)椋╝）圖中存在頂點(diǎn)B和頂點(diǎn)C是不可比較的；由于關(guān)系是傳遞的，顯然（b）圖中的所有頂點(diǎn)之間均是可比較的，所以（b）圖表示的是全序關(guān)系。一個(gè)表示偏序關(guān)系的有向圖可用來表示一個(gè)流程圖。它或者是一個(gè)施工流程圖，或者是一個(gè)產(chǎn)品生產(chǎn)的流程圖，再或者是一個(gè)數(shù)據(jù)流圖（每個(gè)頂點(diǎn)表示一個(gè)過程）。圖中每一條有向邊表示兩個(gè)子工程完成的先后次序。這種用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)（ActivityOnVertex），簡稱AOV網(wǎng)。圖8-27表示偏序和全序關(guān)系的有向圖，假設(shè)64

在AOV網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，因?yàn)榇嬖诃h(huán)意味著某項(xiàng)活動(dòng)應(yīng)以自己為先決條件，如果這樣，只能說明該活動(dòng)是無法完成的，整個(gè)工程也無法再進(jìn)行下去。因此，對(duì)AOV網(wǎng)應(yīng)首先進(jìn)行是否存在環(huán)的判定，如果不存在環(huán)，則可以進(jìn)行拓?fù)渑判虻玫较鄳?yīng)的拓?fù)湫蛄?，反之，則不能得到拓?fù)湫蛄?。拓?fù)渑判蚣皺z測是否存在環(huán)的步驟如下：（1）從有向圖中選取一個(gè)入度為零的頂點(diǎn)將其輸出，如果同時(shí)有多個(gè)頂點(diǎn)的入度為零，則從這些頂點(diǎn)中任選一個(gè)。（2）從圖中刪除選取的頂點(diǎn)以及以它為弧尾的所有弧。（3）不斷重復(fù)以上兩步，直至所有頂點(diǎn)全部輸出，則所有頂點(diǎn)的輸出順序即為該圖的拓?fù)湫蛄?；如果圖中還有剩余頂點(diǎn)尚未輸出，但是圖中已找不到入度為零的頂點(diǎn)了，則說明圖中存在環(huán)，不能進(jìn)行拓?fù)渑判?。在AOV網(wǎng)中，不應(yīng)該出現(xiàn)有向環(huán)，因?yàn)榇嬖诃h(huán)意658.6.2關(guān)鍵路徑

與AOV網(wǎng)相對(duì)應(yīng)的是AOE網(wǎng)（ActivityOnEdge）。AOE網(wǎng)中是用邊表示活動(dòng)的，它是一種邊帶權(quán)值的有向無環(huán)圖。AOE網(wǎng)中的頂點(diǎn)表示事件，弧表示活動(dòng)，弧的權(quán)值一般表示執(zhí)行活動(dòng)需要的時(shí)間。通常，AOE網(wǎng)用來估算工程的完成時(shí)間。例如，圖8-28是一個(gè)假想的有11項(xiàng)活動(dòng)的AOE網(wǎng)。其中有9個(gè)事件A，B，C，D，E，F(xiàn)，G，H，I，每個(gè)事件表示在它之前的活動(dòng)已經(jīng)完成，在它之后的活動(dòng)才可以開始。如A表示整個(gè)工程開始，I表示整個(gè)工程結(jié)束，E表示a4和a5都已經(jīng)完成，a7和a8才可以開始。與每個(gè)活動(dòng)相聯(lián)系的數(shù)是執(zhí)行該活動(dòng)所需的時(shí)間。比如，a1活動(dòng)需要6個(gè)時(shí)間單位，a2需要4個(gè)時(shí)間單位。8.6.2關(guān)鍵路徑66圖8-28AOE網(wǎng)

一般情況下，整個(gè)工程只有一個(gè)開始點(diǎn)（入度為零的頂點(diǎn)）和一個(gè)完成點(diǎn)（出度為零的頂點(diǎn)），開始點(diǎn)也稱為源點(diǎn)，完成點(diǎn)也稱為匯點(diǎn)。和AOV網(wǎng)不同，對(duì)AOE網(wǎng)有待研究的問題是：（1）完成整項(xiàng)工程至少需要多少時(shí)間？（2）網(wǎng)中的哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵？

圖8-28AOE網(wǎng)一般情況下，整個(gè)工程只有67圖8-29結(jié)點(diǎn)V的直接前驅(qū)Ri和直接后繼Hi

由于AOE網(wǎng)中有些活動(dòng)可以并行地進(jìn)行，所以完成工程的最短時(shí)間是從開始點(diǎn)到完成點(diǎn)的最長路徑的長度（這里所說的路徑長度是指路徑上各活動(dòng)持續(xù)時(shí)間之和，不是路徑上弧的數(shù)目）。從開始點(diǎn)到完成點(diǎn)之間路徑長度最長的路徑叫做關(guān)鍵路徑（CriticalPath），關(guān)鍵路徑上的所有活動(dòng)稱為關(guān)鍵活動(dòng)。圖8-29結(jié)點(diǎn)V的直接前驅(qū)Ri和直接后繼Hi68

由于AOE網(wǎng)中的頂點(diǎn)代表事件，事件的發(fā)生有早有晚，假設(shè)頂點(diǎn)V的最早發(fā)生時(shí)刻為Early(V)，最晚發(fā)生時(shí)刻為Late(V)，則圖8-29中的弧頭頂點(diǎn)V的最早發(fā)生時(shí)刻：

即為所有弧尾頂點(diǎn)的最早發(fā)生時(shí)刻和對(duì)應(yīng)弧的權(quán)值之和的最大值。圖8-29中的弧尾頂點(diǎn)V的最晚發(fā)生時(shí)刻：即為所有弧頭頂點(diǎn)的最晚發(fā)生時(shí)刻和對(duì)應(yīng)弧的權(quán)值之差的最小值。規(guī)定起始點(diǎn)的最早發(fā)生時(shí)刻為0，所有頂點(diǎn)的最早發(fā)生時(shí)刻應(yīng)從起始點(diǎn)開始，沿著弧的指向方向逐個(gè)頂點(diǎn)計(jì)算，直至完成點(diǎn)；計(jì)算出完成點(diǎn)的最早發(fā)生時(shí)刻后，規(guī)定其最晚發(fā)生時(shí)刻和最早發(fā)生時(shí)刻相等；然后從完成點(diǎn)開始，沿著弧的逆向方向逐個(gè)頂點(diǎn)計(jì)算所有頂點(diǎn)的最晚發(fā)生時(shí)刻。最終求出起始點(diǎn)的最晚發(fā)生時(shí)刻應(yīng)該也為0。求出所有頂點(diǎn)的最早和最晚發(fā)生時(shí)刻如表8-2所示。由于AOE網(wǎng)中的頂點(diǎn)代表事件，事件的發(fā)生有早69

由于AOE網(wǎng)中的弧代表活動(dòng)，活動(dòng)的開始和完成均有早有晚，假設(shè)活動(dòng)的最早開始時(shí)刻為，最晚開始時(shí)刻為，最早完成時(shí)刻為，最晚完成時(shí)刻為。由于AOE網(wǎng)中的弧代表活動(dòng)，活動(dòng)的開始和完成均70

此外，假定活動(dòng)的持續(xù)時(shí)間為，富余時(shí)間為。由于事件發(fā)生，以該事件為弧尾的所有活動(dòng)即可開始，所以活動(dòng)的開始時(shí)刻取決于其弧尾頂點(diǎn)的發(fā)生時(shí)刻。當(dāng)以某頂點(diǎn)為弧頭的所有活動(dòng)都完成，則該頂點(diǎn)代表的事件即可發(fā)生，所以活動(dòng)的完成時(shí)刻決定了其弧頭頂點(diǎn)的發(fā)生時(shí)刻。圖8-30弧ai的弧尾R和弧頭H

因此，圖8-30中弧的各個(gè)相關(guān)屬性值的計(jì)算有下列公式存在：此外，假定活動(dòng)的持續(xù)時(shí)間為，富余時(shí)間為。圖871

根據(jù)以上公式，計(jì)算所有活動(dòng)的相關(guān)屬性值如表8-3所示。富余時(shí)間為0的活動(dòng)即為關(guān)鍵活動(dòng)。表8-3所有活動(dòng)的相關(guān)屬性值根據(jù)以上公式，計(jì)算所有活動(dòng)的相關(guān)屬性值如表872

從表8-3可知，圖8-28所示AOE網(wǎng)的關(guān)鍵路徑由a1,a4,a7,a8,a10,a11這6個(gè)關(guān)鍵活動(dòng)構(gòu)成。分析關(guān)鍵路徑的目的在于辨別哪些活動(dòng)是關(guān)鍵活動(dòng)，只有縮短關(guān)鍵活動(dòng)的持續(xù)時(shí)間，才有可能縮短整個(gè)工程的工期。圖8-31AOE網(wǎng)及其關(guān)鍵路徑從表8-3可知，圖8-28所示AO