廣度優(yōu)先遍歷

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

圖的定義和術語

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

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

在有向圖中：

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

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

(c)一個頂點度等于頂點的入度+出度，即：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

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

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

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

到頂點v5

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

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

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

圖８-5無向圖及連通分量示意（12）連通圖、連通分量AEBFCDAEBFCD13（13）強連通圖、強連通分量對于有向圖來說，若圖中任意一對頂點vi

和vj(i≠j)均有從一個頂點vi到另一個頂點vj有路徑，也有從vj到vi的路徑，則稱該有向圖是強連通圖。有向圖的極大強連通子圖稱為強連通分量。圖８-2中有兩個強連通分量，分別是{v1,v3,v4}和{v2}，如圖8-6所示。（14）生成樹連通圖G的一個子圖如果是一棵包含G的所有頂點的樹，則該子圖稱為G的生成樹（SpanningTree）。在生成樹中添加任意一條屬于原圖中的邊必定會產生回路，因為新添加的邊使其所依附的兩個頂點之間有了第二條路徑。若生成樹中減少任意一條邊，則必然成為非連通的。n個頂點的生成樹具有n-1條邊。V1V3V2V4圖８-6有向圖G2的兩個強連通分量示意（13）強連通圖、強連通分量（14）生成樹V1V3V2V4圖148-1-3圖的基本操作圖的基本操作有：（1）CreatGraph（G）輸入圖G的頂點和邊，建立圖G的存儲。（2）DFSTraverse（G，v）在圖G中，從頂點v出發(fā)深度優(yōu)先遍歷圖G。（3）BFSTtaverse（G，v）在圖G中，從頂點v出發(fā)廣度優(yōu)先遍歷圖G。

圖的存儲結構比較多。對于圖的存儲結構的選擇取決于具體的應用和需要進行的運算。

下面介紹幾種常用的圖的存儲結構。8-2

圖的存儲表示8-1-3圖的基本操作圖的存儲結構比較多。對15

鄰接矩陣是表示頂點之間相鄰關系的矩陣。假設圖G＝（V，E）有n個頂點，即V＝{v0,v1,…,vn-1}，則G的鄰接矩陣是具有如下性質的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>上的權值（如圖7-3）；∞表示一個計算機允許的、大于所有邊上權值的數(shù)。鄰接矩陣是表示頂點之間相鄰關系的矩陣。16

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

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

圖的鄰接矩陣存儲的描述如下：19voidCreateMGraph(MGraph&G){inti,j,k;charch1,ch2;printf("請輸入頂點數(shù)和邊數(shù)(輸入格式為:頂點數(shù),邊數(shù)):\n");scanf("%d%d",&(G.n),&(G.e));printf("請輸入頂點信息(頂點標志)每個頂點以回車作為結束:\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("請輸入每條邊所對應的兩個頂點（先輸入弧尾，后輸入弧頭）!\n");for(k=0;k<G.e;k++){fflush(stdin);printf("請輸入第%d條邊的兩個頂點標志(用逗號分隔)：",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;} //將輸入邊對應的矩陣元素值設為1}voidCreateMGraph(MGraph&G)208-2-2鄰接表鄰接表(AdjacencyList)是圖的一種順序存儲與鏈式存儲結合的存儲方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對于圖G中的每個頂點vi，該方法將所有鄰接于vi的頂點vj鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表。再將所有點的鄰接表表頭放到數(shù)組中，就構成了圖的鄰接表。在鄰接表表示中有兩種結點結構，如圖8-9所示。

圖8-9鄰接矩陣表示的結點結構8-2-2鄰接表21

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

圖8-10網(wǎng)的邊表結構一種是頂點表的結點結構，它由頂點域（vert22

圖8-11給出無向圖8-7對應的鄰接表表示。

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

structedgenode*next;//指向下一個鄰接邊結點的指針}EdgeNode; //定義邊結點類型typedefstruct{VertexTypevertex;//頂點標志

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

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

intTailPoi,HeadPoi;//保存弧尾、弧頭下標

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

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

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

G.adjlist[i].firstedge=NULL;}//指向第一個邊結點的指針設為空

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

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

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

s->adjvex=HeadPoi;//構造新邊結點

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

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

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

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

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

structarcnode*TLink,*HLink;//指向同弧尾和同弧頭的下一個弧結點的指針

intweight;//弧的權值信息}ArcNode; //定義弧結點的類型typedefstructvexnode{charvertex; //頂點標志

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

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

G.list[i].FirstIn=NULL; //初始化弧結點指針

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

G.list[i].FirstIn=NULL; //初始化弧結點指針

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

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

structedgenode*iLink,*jLink;//指向具有相同端點的下一個邊結點的指針

intweight;//邊的權值信息}EdgeNode; //定義邊結點的類型typedefstructvexnode{charvertex; //頂點標志

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

圖的遍歷

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

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

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

→v6

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

顯然，以上方法是一個遞歸的過程。為了在遍歷過程中便于區(qū)分頂點是否已被訪問，需附設訪問標志數(shù)組visited[0:n-1],，其初值為FALSE，一旦某個頂點被訪問，則其相應的分量置為TRUE。從圖的某一點v出發(fā)，遞歸地進行深度優(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);

}顯然，以上方法是一個遞歸的過程。為了在遍歷過程37voidDFSM(MGraph*G,inti){intj;printf("\t\t深度優(yōu)先遍歷結點:結點%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);}

在遍歷時，對圖中每個頂點至多調用一次DFSM函數(shù)，因為一旦某個頂點被標志成已被訪問，就不再從它出發(fā)進行搜索。因此，遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結構。當用二維數(shù)組表示鄰接矩陣圖的存儲結構時，查找每個頂點的鄰接點所需時間為O(n2)，其中n為圖中頂點數(shù)。voidDFSM(MGraph*G,inti)38

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

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

和v1的鄰接點v2和v3，然后依次訪問v2

的鄰接點v4

和v5

及v3

的鄰接點v6和v7，最后訪問v4

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

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

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

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

從圖的某一點v出發(fā)，遞歸地進行廣度優(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);}從圖的某一點v出發(fā)，遞歸地進行廣度優(yōu)先遍歷的過程如下面41voidBFSM(MGraph*G,intk){inti,j;CirQueueQ;InitQueue(&Q);printf("廣度優(yōu)先遍歷結點:結點%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)先遍歷結點:%c\n",G->vexs[j]);visited[j]=TRUE;EnQueue(&Q,j);}}}voidBFSM(MGraph*G,intk)42８-4

圖的連通性

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

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

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

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

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

這兩個頂點集分別加上所有依附于這些頂點的邊，便構成了非連通圖G3的兩個連通分量。

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

設E(G)為連通圖G中所有邊的集合，則從圖中任一頂點出發(fā)遍歷圖時，必定將E(G)分成兩個集合T(G)和B(G)，其中T(G)是遍歷圖過程中歷經的邊的集合；B(G)是剩余的邊的集合。顯然，T(G)和圖G中所有頂點一起構成連通圖G的極小連通子圖。兩次調用DFS過程（即分別從頂點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)中的邊，實線為集合T(G)中的邊。圖８-18(a)G5的深度優(yōu)先生成樹圖８-18(b)G5的廣度優(yōu)先生成樹V1V5V2V4V8V3V6V7V1V5V2V4V8V3V6V7按照８-1-2節(jié)的定義，它是連通圖的一棵生成樹，并且由46

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

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

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

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

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

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

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

最短路徑

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

圖８-23V1

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

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

從上面的序列中，可以看出一個規(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;//沒有存儲任何最短路徑，所以全部元素均為False D[v]=G.arcs[v0][v];//初始的最短路徑長度設置為v0到相應頂點弧的權值

if(D[v]<INFINITY)//若v0到頂點v的弧存在，則在P中設置好相應路徑

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

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

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

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

//權路徑長度最小的最短路徑終

//點，該終點的下標保存在v中

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

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

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

//向量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)中，從頂點A到其余各頂點的最短路徑如表8-1所示。圖8-25有向網(wǎng)表8-1頂點A到其它頂點的最短路徑如圖8-25所示的有向網(wǎng)中，從頂點A到其余各頂點的最短路徑如60

以圖8-25所示的有向網(wǎng)為實例，迪杰斯特拉算法求解該網(wǎng)中從源點A到其余各頂點最短路徑的過程如圖8-26所示。圖8-26迪杰斯特拉算法的求解過程以圖8-25所示的有向網(wǎng)為實例，迪杰斯特拉算618.6有向無環(huán)圖及其應用一個不存在環(huán)的有向圖稱為有向無環(huán)圖（DirectedAcyclineGraph，簡稱為DAG圖）。有向無環(huán)圖可用于描述某項工程的進行過程。除最簡單的情況之外，幾乎所有工程都可分為若干個稱作活動的子工程，而這些子工程之間，通常受著一定條件的約束，如其中某些子工程的開始必須在另一些子工程完成之后。對于整個工程，人們往往最關心兩個方面的問題：一是工程能否順利進行；二是估算整個工程完成所必須的最短時間。其中前一個問題就是有向圖能否拓撲排序的問題，后一個問題則和關鍵路徑有關，下面分別討論之。8.6有向無環(huán)圖及其應用628.6.1拓撲排序拓撲排序是有向圖的一個重要操作。在給定的有向圖G中，若頂點序列滿足下列條件：若在有向圖G中從頂點到頂點有一條路徑，則在序列中頂點必在頂點之前，便稱這個序列為一個拓撲序列。求一個有向圖拓撲序列的過程稱為拓撲排序（TopologicalSort），實質上，拓撲排序由某個集合上的偏序關系得到該集合上的一個全序關系的過程。在離散數(shù)學課程中關于偏序關系和全序關系有如下定義：若集合S上的關系R是自反的、反對稱的和傳遞的，則稱R是集合S上的偏序關系。設R是集合S上的偏序（PartialOrder），如果對每個必有xRy或yRx，則稱R是集合S上的全序關系。直觀地看，偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。8.6.1拓撲排序63

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

在AOV網(wǎng)中，不應該出現(xiàn)有向環(huán)，因為存在環(huán)意味著某項活動應以自己為先決條件，如果這樣，只能說明該活動是無法完成的，整個工程也無法再進行下去。因此，對AOV網(wǎng)應首先進行是否存在環(huán)的判定，如果不存在環(huán)，則可以進行拓撲排序得到相應的拓撲序列，反之，則不能得到拓撲序列。拓撲排序及檢測是否存在環(huán)的步驟如下：（1）從有向圖中選取一個入度為零的頂點將其輸出，如果同時有多個頂點的入度為零，則從這些頂點中任選一個。（2）從圖中刪除選取的頂點以及以它為弧尾的所有弧。（3）不斷重復以上兩步，直至所有頂點全部輸出，則所有頂點的輸出順序即為該圖的拓撲序列；如果圖中還有剩余頂點尚未輸出，但是圖中已找不到入度為零的頂點了，則說明圖中存在環(huán)，不能進行拓撲排序。在AOV網(wǎng)中，不應該出現(xiàn)有向環(huán)，因為存在環(huán)意658.6.2關鍵路徑

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

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

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

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

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

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

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

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

因此，圖8-30中弧的各個相關屬性值的計算有下列公式存在：此外，假定活動的持續(xù)時間為，富余時間為。圖871

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

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