數(shù)據(jù)結構與算法：第七章 圖 學習指導材料

第八章圖

第一部分知識點及例題精選

圖狀結構是一種比樹形結構更復雜的非線性結構。在樹狀結構中，結點間具有分支層次

關系，每一層上的結點只能和上一層中的至多一個結點相關，但可能和下一層的多個結點相

關。而在圖狀結構中，任意兩個結點之間都可能相關，即結點之間的鄰接關系可以是任意的。

因此，圖狀結構被用于描述各種復雜的數(shù)據(jù)對象，在自然科學、社會科學和人文科學等許多

領域有著非常廣泛的應用。

8.1圖的基本概念

8.1.1圖的定義和術語

1.圖的定義

圖(Graph)是由非空的頂點集合和一個描述頂點之間關系一一邊(或者弧)的集合組成,

其形式化定義為：

G=(V,E)

V={vi|vi￡dataobject}

E={(vi,vj)|vi.vjGVAP(vi,vj))

其中，G表示一個圖，V是圖G中頂點的集合，E是圖G中邊的集合，集合E中P(vi,vj)表

示頂點vi和頂點vj之間有一條直接連線，即偶對(vi,vj)表示一條邊。圖8.1給出了一個圖的

示例，在該圖中：

集合V={v1,v2,v3,v4,v5}；

集合E={(vl,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5),(v2,v5)}。

圖8.1無向圖G1圖&2有向圖G2

2.圖的相關術語

(1)無向圖。在一個圖中，如果任意兩個頂點構成的偶對(vi,vj)6E是無序的，即

頂點之間的連線是沒有方向的，則稱該圖為無向圖。如圖8.1所示是一個無向圖G1。

(2)有向圖。在一個圖中，如果任意兩個頂點構成的偶對(vi,vj)6E是有序的，即

頂點之間的連線是有方向的，則稱該圖為有向圖。如圖8.2所示是一個有向圖G2：

G2=(V2,E2)

V2={vl,v2,v3,v4}

E2={<vl,v2>,<v1,v3>,<v3,v4>,<v4,v1>}

(3)頂點、邊、弧、弧頭、弧尾。圖中，數(shù)據(jù)元素vi稱為頂點(vertex)；P(vi,vj)表示

在頂點vi和頂點vj之間有一條直接連線。如果是在無向圖中，則稱這條連線為邊；如果是

在有向圖中，一般稱這條連線為弧。邊用頂點的無序偶對(vi,vj)來表示，稱頂點vi和頂

點vj互為鄰接點，邊(vi,vj)依附于頂點vi與頂點vj；弧用頂點的有序偶對<vi,vj>來表示,

有序偶對的第一個結點Vi被稱為始點(或弧尾)，在圖中就是不帶箭頭的一端；有序偶對的

第二個結點vj被稱為終點(或弧頭)，在圖中就是帶箭頭的一端。

(4)無向完全圖。在一個無向圖中，如果任意兩頂點都有一條直接邊相連接，則稱該

圖為無向完全圖?？梢宰C明，在一個含有n個頂點的無向完全圖中，有n(n-l)/2條邊。

(5)有向完全圖。在一個有向圖中，如果任意兩頂點之間都有方向互為相反的兩條弧

相連接，則稱該圖為有向完全圖。在一個含有n個頂點的有向完全圖中，有n(n-l)條邊。

(6)稠密圖、稀疏圖。若一個圖接近完全圖，稱為稠密圖；稱邊數(shù)很少的圖為稀疏圖。

(7)頂點的度、入度、出度。頂點的度(degree)是指依附于某頂點v的邊數(shù)，通常

記為TD(v)。在有向圖中，要區(qū)別頂點的入度與出度的概念。頂點v的入度是指以頂點為

終點的弧的數(shù)目。記為ID(v)；頂點v出度是指以頂點v為始點的弧的數(shù)目，記為OD(v)。

有TD(v)=ID(v)+OD(v)。

例如,在G1中有：

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

在G2中有：

ID(vl)=lOD(vl)=2TD(vl)=3

ID(v2)=lOD(v2)=0TD(v2)=l

ID(v3)=lOD(v3)=lTD(v3)=2

ID(V4)=1OD(v4)=lTD(v4)=2

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

的數(shù)目滿足關系：n

2e=(ITD(vi))/2

(8)邊的權、網(wǎng)圖。8’邊有關的數(shù)據(jù)信息稱為權(weight)。在實際應用中，權值可以

有某種含義。比如，在一個反映城市交通線路的圖中，邊上的權值可以表示該條線路的長度

或者等級；對于一個電子線路圖，邊上的權值可以表示兩個端點之間的電阻、電流或電壓值;

對于反映工程進度的圖而言，邊上的權值可以表示從前一個工程到后一個工程所需要的時間

等等。邊上帶權的圖稱為網(wǎng)圖或網(wǎng)絡(network)。如圖8.3所示，就是一個無向網(wǎng)圖。如果

邊是有方向的帶權圖，則就是一個有向網(wǎng)圖。

(9)路徑、路徑長度。頂點Vp到頂點Vq之間的路徑(path)是指頂點序列Vp,V“,Vi2,....

Vim,Vq,其中,(Vp,VH),(91,環(huán)2),…,(％為)分別為圖中的邊。路徑上邊的數(shù)目稱為路徑長度。

圖8.1所示的無向圖G1中，vlfv4fv3fv5與vl^v2-v5是從頂點vl到頂點v5的兩條

路徑，路徑長度分別為3和2。

(10)回路、簡單路徑、簡單回路。稱vi的路徑為回路或者環(huán)(cycle),序列中頂點不

重復出現(xiàn)的路徑稱為簡單路徑。在圖8.1中，前面提到的vl到v5的兩條路徑都為簡單路徑。

除第一個頂點與最后一個頂點之外，其他頂點不重復出現(xiàn)的回路稱為簡單回路,或者簡單環(huán)。

如圖8.2中的vl-v3-v4-vl?

(11)子圖。對于圖G=(V,E),G=(V',E，)，若存在V，是V的子集，E，是E的

子集，則稱圖G'是G的一個子圖。圖8.4示出了G2和G1的兩個子圖G，和G”。

圖&3一個無向網(wǎng)圖示意圖&4圖G2和G1的兩個子圖示意

(a)無向圖G3(b)G3的兩個連通分量

圖8.5無向圖及連通分量示意圖&6有向圖G2的兩個強連通分量示意

(12)連通的、連通圖、連通分量。在無向圖中，如果從一個頂點vi到另一個頂點vj(i

Wj)有路徑，則稱頂點vi和vj是連通的。如果圖中任意兩頂點都是連通的，則稱該圖是連

通圖。無向圖的極大連通子圖稱為連通分量。圖8.5(a)中有兩個連通分量，如圖8.5(b)所示。

(13)強連通圖、強連通分量。對于有向圖來說，若圖中任意一對頂點vi和vj(iWj)

均有從一個頂點vi到另一個頂點vj有路徑，也有從vj到vi的路徑，則稱該有向圖是強連

通圖。有向圖的極大強連通子圖稱為強連通分量。圖8.2中有兩個強連通分量，分別是

{vl,v2,v3}和{v4},如圖8.6所示。

(14)生成樹。所謂連通圖G的生成樹，是G的包含其全部n個頂點的一個極小連通

子圖。它必定包含且僅包含G的n-1條邊。圖8.4(切6”示出了圖8.13)中61的一棵生成樹。

在生成樹中添加任意一條屬于原圖中的邊必定會產(chǎn)生回路，因為新添加的邊使其所依附的兩

個頂點之間有了第二條路徑。若生成樹中減少任意一條邊，則必然成為非連通的。

(15)生成森林。在非連通圖中，由每個連通分量都可得到一個極小連通子圖，即一棵

生成樹。這些連通分量的生成樹就組成了一個非連通圖的生成森林。

8.2圖的存儲表示

圖是一種結構復雜的數(shù)據(jù)結構，表現(xiàn)在不僅各個頂點的度可以千差萬別，而且頂點之間

的邏輯關系也錯綜復雜。從圖的定義可知，一個圖的信息包括兩部分，即圖中頂點的信息以

及描述頂點之間的關系一一邊或者弧的信息。因此無論采用什么方法建立圖的存儲結構，都

要完整、準確地反映這兩方面的信息。

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

8.2.1鄰接矩陣

所謂鄰接矩陣(AdjacencyMatrix)的存儲結構，就是用一維數(shù)組存儲圖中頂點的信息,

用矩陣表示圖中各頂點之間的鄰接關系。假設圖G=(V,E)有n個確定的頂點，即丫=

{vo,w,…,ve},則表示G中各頂點相鄰關系為一個nXn的矩陣，矩陣的元素為：

1若(Vi,Vj)或＜Vi,Vj＞是E(G)中的邊

o若(％,vj)或＜Vi,Vj＞不是E(G)中的邊

若G是網(wǎng)圖，則鄰接矩陣可定義為：

Wij若(vi,vj)或＜Vi,Vj＞是E(G)中的邊

A"""I0或8若(vi,*)或不是E(G)中的邊

其中，Wij表示邊(Vi,Vj)或＜Vi,Vj＞上的權值；8表示一個計算機允許的、大于所有邊上權

值的數(shù)。

用鄰接矩陣表示法表示圖如圖8.7所示。

用鄰接矩陣表示法表示網(wǎng)圖如圖8.8所示。

圖8.7一個無向圖的鄰接矩陣表示

圖8.8一個網(wǎng)圖的鄰接矩陣表示

從圖的鄰接矩陣存儲方法容易看出這種表示具有以下特點：

①無向圖的鄰接矩陣一定是一個對稱矩陣。因此，在具體存放鄰接矩陣時只需存放上

（或下）三角矩陣的元素即可。

②對于無向圖，鄰接矩陣的第i行（或第i歹!!）非零元素（或非8元素）的個數(shù)正好

是第i個頂點的度TD（vi）。

③對于有向圖，鄰接矩陣的第i行（或第i歹D非零元素（或非8元素）的個數(shù)正好

是第i個頂點的出度OD（vi）（或入度ID（vi））。

④用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相連；但是，要

確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這

是用鄰接矩陣存儲圖的局限性。

下面介紹圖的鄰接矩陣存儲表示。

在用鄰接矩陣存儲圖時，除了用一個二維數(shù)組存儲用于表示頂點間相鄰關系的鄰接矩陣

外，還需用一個一維數(shù)組來存儲頂點信息，另外還有圖的頂點數(shù)和邊數(shù)。故可將其形式描述

如下：

#defineMaxVertexNum100/*最大頂點數(shù)設為100*/

typedefcharVertexType;/*頂點類型設為字符型*/

typedefintEdgeType;/*邊的權值設為整型*/

typedefstruct{

VertexTypevexs[MaxVerlexNum];/*頂點表*/

EdeTypeedges[MaxVertexNum][MaxVertexNum];/*鄰接矩陣，即邊表*/

intn,e;/*頂點數(shù)和邊數(shù)*/

JMgragh;Z*Maragh是以鄰接矩陣存儲的圖類型*/

建立一個圖的鄰接矩陣存儲的算法如下:

voidCreateMGmph(MGniph*G)

{/*建立有向圖G的鄰接矩陣存儲*/

inti,j,k,w;

charch;

prinlf(”請輸入頂點數(shù)和邊數(shù)(輸入格式為:頂點數(shù)，邊數(shù)):\n)

scanf("％d,%d”,&(G?>n),&(G->e));/*輸入頂點數(shù)和邊數(shù)*/

printf(”請輸入頂點信息(輸入格式為:頂點號<CR>):\n)

for(i=0;i<G->n;i++)scanf(n\n%cH,&(G->vexs[i]));/*輸入頂點信息，建立頂點表*/

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

for(j=O;j<G->n;j++)G->edges[i][j]=O;/*初始化鄰接矩陣*/

prinlf("請輸入每條邊對應的兩個頂點的序號(輸入格式為:i,j):\n”)；

for(k=0;k<G->e;k++)

{scanf(n\n%d,%dH,&i,&j);/*輸入e條邊，建立鄰接矩陣*/

G->edges[i][j]=l;/*若加入G->edges[j][i]=l;,*/

/*則為無向圖的鄰接矩陣存儲建立*/

)

}/*CreatcMGraph*/

算法8.1

8.2.2鄰接表

鄰接表(AdjacencyList)是圖的一種順序存儲與鏈式存儲結合的存儲方法。鄰接表表示法

類似于樹的孩子鏈表表示法。就是對于圖G中的每個頂點vi,將所有鄰接于vi的頂點vj鏈

成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表，再將所有點的鄰接表表頭放到數(shù)組中，

就構成了圖的鄰接表。在鄰接表表示中有兩種結點結構，如圖8.9所示。

頂點域邊表頭指針鄰接點域指針域

vertexfirstedgeadjvexnext

頂點表邊表

圖8.9鄰接矩陣表示的結點結構

一種是頂點表的結點結構，它由頂點域(vertex)和指向第一條鄰接邊的指針域(firstedge)

構成，另一種是邊表(即鄰接表)結點，它由鄰接點域(adjvex)和指向下一條鄰接邊的指針

域(next)構成。對于網(wǎng)圖的邊表需再增設一個存儲邊上信息(如權值等)的域(info),網(wǎng)圖

的邊表結構如圖&10所示。

鄰接點域邊上信息指針域

adjvexinfonext

圖8.10網(wǎng)圖的邊表結構

圖8.11給出無向圖8.7對應的鄰接表表示。

序號vertexfirstedge

—

V03A

圖8.11圖的鄰接表表示

鄰接表表示的形式描述如下:

#defineMaxVerNum100/*最大頂點數(shù)為100*/

typedefstructnode{/*邊表結點*/

intadjvex;/*鄰接點域*/

structnode*next;/*指向下一個鄰接點的指針域*/

/*若要表示邊上信息，則應增加一個數(shù)據(jù)域info*/

}EdgeNode;

typedefstructvnode{/*頂點表結點*/

VertexTypevertex;/*頂點域*/

EdgeNode*firstedge;/*邊表頭指針*/

}VertexNode;

typedefVertexNodeAdjList[MaxVertexNum];/*AdjList是鄰接表類型*/

typedefstruct{

AdjListadjlist;/*鄰接表*/

intn,e;/*頂點數(shù)和邊數(shù)*/

}ALGraph；/*ALGraph是以鄰接表方式存儲的圖類型*/

建立一個有向圖的鄰接表存儲的算法如下：

voidCreateALGraph(ALGraph*G)

{/*建立有向圖的鄰接表存儲切

inti,j,k;

EdgeNode*s;

prinlf(”請輸入頂點數(shù)和邊數(shù)(輸入格式為:頂點數(shù)，邊數(shù))：\n)

scanf(u%d,%dM,&(G->n),&(G>>e));/*讀入頂點數(shù)和邊數(shù)*/

printf("請輸入頂點信息(輸入格式為:頂點號<CR>)：\n")；

for(i=0;i<G->n;i++)/*建立有n個頂點的頂點表*/

{scanf("\n%c",&(G->adjlist[i].vertex));/*讀入頂點信息*/

G->adjlist[i].firstedge=NULL;/*頂點的邊表頭指針設為空刃

)

printf("請輸入邊的信息(輸入格式為:i,j)：\nu);

for(k=0;k<G->e;k++)/*建立邊表*/

{scanf(M\n%d,%d",&i,&j);/*讀入邊<Vi,Vj>的頂點對應序號*/

s=(EdgeNode*)malloc(sizeof(EdgeNode));/*生成新邊表結點s*/

s->adjvex=j;/*鄰接點序號為產(chǎn)/

s->next=G->adjlist[i].firstedge;/*將新邊表結點S插入到頂點Vi的邊表頭部*/

G->adjlist[i].firstedge=s;

}/*CreateALGraph*/

算法8.2

若無向圖中有n個頂點、e條邊，則它的鄰接表需n個頭結點和2e個表結點。顯然，

在邊稀疏(e?n(n-l)/2)的情況下，用鄰接表表示圖比鄰接矩陣節(jié)省存儲空間，當和邊相關的

信息較多時更是如此。

在無向圖的鄰接表中，頂點vi的度恰為第i個鏈表中的結點數(shù)；而在有向圖中，第i

個鏈表中的結點個數(shù)只是頂點vi的出度，為求入度，必須遍歷整個鄰接表。在所有鏈表中

其鄰接點域的值為i的結點的個數(shù)是頂點vi的入度。有時，為了便于確定頂點的入度或以

(a)鄰接表(b)逆鄰接表

圖8.12圖8.2的鄰接表和逆鄰接表

在建立鄰接表或逆鄰接表時，若輸入的頂點信息即為頂點的編號，則建立鄰接表的復雜

度為O(n+e),否則，需要通過查找才能得到頂點在圖中位置，則時間復雜度為O(me)。

在鄰接表上容易找到任一頂點的第一個鄰接點和下一個鄰接點，但要判定任意兩個頂點

(vi和vj)之間是否有邊或弧相連，則需搜索第i個或第j個鏈表，因此，不及鄰接矩陣方

便。

8.2.3十字鏈表

十字鏈表(OrthogonalList)是有向圖的一種存儲方法，它實際上是鄰接表與逆鄰接表

的結合，即把每一條邊的邊結點分別組織到以弧尾頂點為頭結點的鏈表和以弧頭頂點為頭頂

點的鏈表中。在十字鏈表表示中，頂點表和邊表的結點結構分別如圖&13的(a)和(b)所示。

頂點值域指針域指針域

vertexfirstinfirstout

(a)十字鏈表頂點表結點結構

弧尾結點弧頭結點弧上信息指針域指針域

tailvexheadvexinfohlinktlink

(b)十字鏈表邊表的弧結點結構

圖&13十字鏈表頂點表、邊表的弧結點結構示意

8.3圖的遍歷

圖的遍歷是指從圖中的任一頂點出發(fā)，對圖中的所有頂點訪問一次且只訪問一次。圖的

遍歷操作和樹的遍歷操作功能相似。圖的遍歷是圖的一種基本操作，圖的許多其它操作都是

建立在遍歷操作的基礎之上。

圖的遍歷通常有深度優(yōu)先搜索和廣度優(yōu)先搜索兩種方式，下面分別介紹。

8.3.1深度優(yōu)先搜索

深度優(yōu)先搜索(Depth_FisrstSearch)遍歷類似于樹的先根遍歷，是樹的先根遍歷的推

廣。

假設初始狀態(tài)是圖中所有頂點未曾被訪問，則深度優(yōu)先搜索可從圖中某個頂點發(fā)v出

發(fā)，訪問此頂點，然后依次從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和

v有路徑相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪

間的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。

以圖8.17的無向圖G5為例，進行圖的深度優(yōu)先搜索。假設從頂點vl出發(fā)進行搜索，

在訪問了頂點vl之后，選擇鄰接點v2。因為v2未曾訪問，則從v2出發(fā)進行搜索。依次類

推，接著從v4、v8、v5出發(fā)進行搜索。在訪問了v5之后，由于v5的鄰接點都已被訪問,

則搜索回到v8。由于同樣的理由，搜索繼續(xù)回到v4,v2直至vl,此時由于vl的另一個鄰

接點未被訪問，則搜索又從vl到v3,再繼續(xù)進行下去由此，得到的頂點訪問序列為：

vlv2-'v4fv8fv5v3fv6-v7

顯然，這是一個遞歸的過程。為了在遍歷過程中便于區(qū)分頂點是否已被訪問，需附設訪

問標志數(shù)組visited[O:n-l],,其初值為FALSE,一旦某個頂點被訪問，則其相應的分量置

為TRUEo

從圖的某一點v出發(fā)，遞歸地進行深度優(yōu)先遍歷的過程如算法8.4所示。

voidDFS(GraphG,intv)

{/*從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G*/

visited[v]=TRUE;VisitFunc(v);/*訪問第v個頂點*/

for(w=FisrAdjVex(G,v);w;w=NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w);/*對v的尚未訪問的鄰接頂點w遞歸調(diào)用DFS*/

)

算法8.4

算法8.5和算法8.6給出了對以鄰接表為存儲結構的整個圖G進行深度優(yōu)先遍歷實現(xiàn)的

C語言描述。

voidDFSTraverseAL(ALGmph*G)

{/*深度優(yōu)先遍歷以鄰接表存儲的圖G*/

inti;

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

visited[i]=FALSE;/*標志向量初始化*/

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

if(!visited[i])DFSAL(G,i);/*vi未訪問過，從vi開始DFS搜索*/

}/*DFSTraveseAL*/

算法8.5

voidDFSAL(ALGraph*G,inti)

{/*以Vi為出發(fā)點對鄰接表存儲的圖G進行DFS搜索*/

EdgeNode*p;

printf("visitvertex:V%c\n”,G->adjlist[i].vertex);/*訪問頂點Vi*/

visited[i]=TRUE;/*標記Vi已訪問*/

p=G->adjlist[i].firstedge;/*取Vi邊表的頭指針*/

while(p)/*依次搜索Vi的鄰接點Vj,j=p->adjva*/

{if(!visited[p->adjvex])/*若Vj尚未訪問，則以Vj為出發(fā)點向縱深搜索*/

DFSAL(G,p->adjvex);

p=p->next;/*找Vi的下一個鄰接點*/

)

}/*DFSAL*/

算法8.6

分析上述算法，在遍歷時，對圖中每個頂點至多調(diào)用一次DFS函數(shù)，因為一旦某個頂

點被標志成已被訪問，就不再從它出發(fā)進行搜索。因此，遍歷圖的過程實質(zhì)上是對每個頂點

查找其鄰接點的過程。其耗費的時間則取決于所采用的存儲結構。當用二維數(shù)組表示鄰接矩

陣圖的存儲結構時，查找每個頂點的鄰接點所需時間為0(r),其中n為圖中頂點數(shù)。而當

以鄰接表作圖的存儲結構時，找鄰接點所需時間為0(e),其中e為無向圖中邊的數(shù)或有向圖

中弧的數(shù)。由此，當以鄰接表作存儲結構時，深度優(yōu)先搜索遍歷圖的時間復雜度為O(n+e)o

8.3.2廣度優(yōu)先搜索

廣度優(yōu)先搜索(Breadth_FirstSearch)遍歷類似于樹的按層次遍歷的過程。

假設從圖中某頂點v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問過和鄰接點，然

后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后

被訪問的頂點的鄰接點”被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此

時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直

至圖中所有頂點都被訪問到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程中以v為起始點，

由近至遠，依次訪問和v有路徑相通且路徑長度為1,2,…的頂點。

例如，對圖8.17所示無向圖G5進行廣度優(yōu)先搜索遍歷，首先訪問vl和vl的鄰接點

v2和v3,然后依次訪問v2的鄰接點v4和v5及v3的鄰接點v6和v7,最后訪問v4的鄰

接點v8。由于這些頂點的鄰接點均已被訪問，并且圖中所有頂點都被訪問，由些完成了圖

的遍歷。得到的頂點訪問序列為：

vl-v2-*v3-*v4fv5fv6fv7-*v8

和深度優(yōu)先搜索類似，在遍歷的過程中也需要一個訪問標志數(shù)組。并且，為了順次訪

問路徑長度為2、3、…的頂點，需附設隊列以存儲已被訪問的路徑長度為1、2、…的頂

點。

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

voidBFSTraverse(GraphG,Status(*Visit)(intv))

{/*按廣度優(yōu)先非遞歸遍歷圖Go使用輔助隊列Q和訪問標志數(shù)組visited*/

for(v=O;v<G,vexnum;++v)

visited[v]=FALSE

InitQueue(Q);/*置空的國債隊列Q*/

if(!visited[v])/*v尚未訪問*/

{EnQucue(Q,v);/*v入隊列*/

while(!QueueEmpty(Q))

{DeQueue(Q,u);/*隊頭元素出隊并置為u*/

visited[u]=TRUE;visit(u);/*訪問u*/

for(w=FistAdjVex(G,u);w;w=NextAdjVex(G,u,w))

if(!visited[w])EnQueue(Q,w);/*u的尚未訪問的鄰接頂點w入隊列Q*/

}/*BFSTraverse*/

算法8.7

算法8.8和算法8.9給出了對以鄰接矩陣為存儲結構的整個圖G進行深度優(yōu)先遍歷實現(xiàn)

的C語言描述。

voidBFSTraverseAL(MGraph*G)

{/*廣度優(yōu)先遍歷以鄰接矩陣存儲的圖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);/*vi未訪問過，從vi開始BFS搜索*/

}/*BFSTraverseAL*/

算法8.8

voidBFSM(MGraph*G,intk)

{/*以Vi為出發(fā)點，對鄰接矩陣存儲的圖G進行BFS搜索*/

inti,j；

CirQueueQ;

InitQueue(&Q);

printf(nvisitvertex:V%c\n*\G->vexs[k]);/*訪問原點Vk*/

visited[k]=TRUE;

EnQueue(&Q,k);/*原點Vk入隊列*/

while(!QueueEmpty(&Q))

{i=DeQueue(&Q);/*Vi出隊列*/

for(j=O;j<G->n;j++)/*依次搜索Vi的鄰接點Vj*/

if(G->edges[i]|j]==l&&!visited[j])/*若Vj未訪問*/

{printf("visitvertex:V%c\n",G->vexs[j]);/*訪問Vj*/

visited[j]=TRUE;

EnQueue(&Q,j);/*訪問過的Vj入隊列*/

算法8.9

分析上述算法，每個頂點至多進一次隊列。遍歷圖的過程實質(zhì)是通過邊或弧找鄰接點的

過程，因此廣度優(yōu)先搜索遍歷圖的時間復雜度和深度優(yōu)先搜索遍歷相同，兩者不同之處僅僅

在于對頂點訪問的順序不同。

8.4圖的連通性

判定一個圖的連通性是圖的一個應用問題，我們可以利用圖的遍歷算法來求解這一問

題。本節(jié)將重點討論無向圖的連通性、有向圖的連通性、由圖得到其生成樹或生成森林以及

連通圖中是否有關節(jié)點等幾個有關圖的連通性的問題。

8.4.1無向圖的連通性

在對無向圖進行遍歷時，對于連通圖，僅需從圖中任一頂點出發(fā)，進行深度優(yōu)先搜索或

廣度優(yōu)先搜索，便可訪問到圖中所有頂點。對非連通圖，則需從多個頂點出發(fā)進行搜索，而

每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為其各個連通分量中

的頂點集。例如，圖8.5(a)是一個非連通圖G3,按照圖8.18所示G3的鄰接表進行深度優(yōu)

先搜索遍歷，需由算法8.5調(diào)用兩次DFS(即分別從頂點A和D出發(fā))，得到的頂點訪問序

列分別為：

ABFECE

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

量,如圖8.5(b)所示。

因此，要想判定一個無向圖是否為連通圖，或有幾個連通分量，就可設一個計數(shù)變量

count,初始時取值為0,在算法8.5的第二個for循環(huán)中，每調(diào)用一次DFS,就給count增1?

這樣，當整個算法結束時，依據(jù)count的值，就可確定圖的連通性了。

序號

圖8.18G3的鄰接表

8.4.2有向圖的連通性

有向圖的連通性不同于無向圖的連通性，可分為弱連通、單側連通和強連通。這里僅就

有向圖的強連通性以及強連通分量的判定進行介紹。

深度優(yōu)先搜索是求有向圖的強連通分量的一個有效方法。假設以十字鏈表作有向圖的存

儲結構，則求強連通分量的步驟如下：

(1)在有向圖G上，從某個頂點出發(fā)沿以該頂點為尾的弧進行深度優(yōu)先搜索遍歷，并

按其所有鄰接點的搜索都完成(即退出DFS函數(shù))的順序將頂點排列起來。此時需對8.3.1中

的算法作如下兩點修改：(a)在進入DFSTraverseAL函數(shù)時首先進行計數(shù)變量的初始化，

即在入口處加上count=0的語句；(b)在退出函數(shù)之前將完成搜索的頂點號記錄在另一個

輔助數(shù)組finished[vexnum]中，即在函數(shù)DFSAL結束之前加上finished[++count]=v的語句。

(2)在有向圖G上，從最后完成搜索的頂點(即finished[vexnum-l]中的頂點)出發(fā)，

沿著以該頂點為頭的弧作逆向的深度搜索遍歷，若此次遍歷不能訪問到有向圖中所有頂點，

則從余下的頂點中最后完成搜索的那個頂點出發(fā)，繼續(xù)作逆向的深度優(yōu)先搜索遍歷，依次類

推，直至有向圖中所有頂點都被訪問到為止。此時調(diào)用DFSTraverseAL時需作如下修改：

函數(shù)中第二個循環(huán)語句的邊界條件應改為v從finished[vexnum-l]至finished[。]。

由此，每一次調(diào)用DFSAL作逆向深度優(yōu)先遍歷所訪問到的頂點集便是有向圖G中一個

強連通分量的頂點集。

例如圖8.14(a)所示的有向圖，假設從頂點vl出發(fā)作深度優(yōu)先搜索遍歷，得到finished

數(shù)組中的頂點號為(1,3,2,0)；則再從頂點vl出發(fā)作逆向的深度優(yōu)先搜索遍歷，得到兩個頂

點集(vl,v3,v4}^{v2},這就是該有向圖的兩個強連通分量的頂點集。

上述求強連通分量的第二步，其實質(zhì)為：

(1)構造一個有向圖Gr,設G=(V,{A}),則Gr=(Vr,{Ar})對于所有vvi,,vj>GA,必

有<vj,vi>GAr。即Gr中擁有和G方向相反的弧；

(2)在有向圖Gr上，從頂點finished]vexnum-1]出發(fā)作深度優(yōu)先遍歷?？梢宰C明，在

Gr上所得深度優(yōu)先生成森林中每一棵樹的頂點集即為G的強連通分量的頂點集。

顯然，利用遍歷求強連通分量的時間復雜度亦和遍歷相同。

8.4.3生成樹和生成森林

在這一小節(jié)里，我們將給出通過對圖的遍歷，得到圖的生成樹或生成森林的算法。

設E(G)為連通圖G中所有邊的集合，則從圖中任一頂點出發(fā)遍歷圖時，必定將E(G)

分成兩個集合T(G)和B(G),其中T(G)是遍歷圖過程中歷經(jīng)的邊的集合；B(G)是剩余的邊的

集合。顯然，T(G)和圖G中所有頂點一起構成連通圖G的極小連通子圖。按照8.1.2節(jié)的定

義，它是連通圖的一棵生成樹，并且由深度優(yōu)先搜索得到的為深度優(yōu)先生成樹；由廣度優(yōu)先

搜索得到的為廣度優(yōu)先生成樹。例如，圖8.17(a)和(b)所示分別為連通圖G5的深度優(yōu)先生成

樹和廣度優(yōu)先生成樹。圖中虛線為集合B(G)中的邊，實線為集合T(G)中的邊。

(a)G5的深度優(yōu)先生成樹(b)G5的廣度優(yōu)先生成樹

圖8.19由圖&17G5得到的生成樹

(a)一個非連通圖無向圖G6(b)G6的深度優(yōu)先生成樹林

圖8.20非連通圖G6及其生成樹林

對于非連通圖，通過這樣的遍歷，將得到的是生成森林。例如，圖8.20(b)所示為圖

8.20(a)的深度優(yōu)先生成森林，它由三棵深度優(yōu)先生成樹組成。

假設以孩子兄弟鏈表作生成森林的存儲結構，則算法8.10生成非連通圖的深度優(yōu)先生

成森林，其中DFSTree函數(shù)如算法8.11所示。顯然，算法8.10的時間復雜度和遍歷相同。

voidDESForest(GraphG,CSTree*T)

{/*建立無向圖G的深度優(yōu)先生成森林的孩子兄弟鏈表T*/

T=NULL;

for(v=0;v<Gvexnum;++v)

if(!visited[v]=FALSE;

for(v=0;v<G.vexnum;++v)

if(!visited[v])/*頂點v為新的生成樹的根結點*/

{p=(CSTree)malloc(sixeof(CSNode));/*分配根結點*/

p={GetVex(Gv).NULL,NULL};/*給根結點賦值*/

if(!T)

(*T)=p;/*T是第一棵生成樹的根*/

elseq->nextsibling=p;/*前一棵的根的兄弟是其它生成樹的根*/

q=p;/*q指示當前生成樹的根*/

DFSTree(G,v,&p);/*建立以p為根的生成樹*/

)

算法8.10

voidDFSTree(GraphG,intv,CSTree*T)

{/*從第v個頂點出發(fā)深度優(yōu)先遍歷圖G,建立以*T為根的生成樹*/

visited[v]=TRUE;

first=TRUE;

for(w=FirstAdjVex(G,v);w;w=NexlAdjVex(G,v,w))

if(!visited[w])

{p=(CSTree)malloc(sizeof)CSNode));/*分配孩子結點*/

*p={GetVex(G,w),NULL,NULL};

if(first)/*w是v的第一個未被訪問的鄰接頂點，作為根的左孩子結點*/

{T->lchild=p;

first=FALSE;

)

else{/*w是v的其它未被訪問的鄰接頂點，作為上一鄰接頂點的右兄弟*/

q->nextsibling=p;

)

q=p；

DFSTree(Qw,&q);/*從第w個頂點出發(fā)深度優(yōu)先遍歷圖G,建立生成子樹*q*/

}

)

算法8.11

8.4.4關節(jié)點和重連通分量

假若在刪去頂點V以及和V相關聯(lián)的各邊之后，將圖的一個連通分量分割成兩個或兩

個以上的連通分量，則稱頂點v為該圖的一個關節(jié)點(articulationpoint)。一個沒有關節(jié)點的

連通圖稱為重連通圖(biconnectedgr叩h)。在重連通圖上，任意一對頂點之間至少存在兩條

路徑，則在刪去某個頂點以及依附于該頂點的各邊時也不破壞圖的連通性。若在連通圖上至

少刪去k個頂點才能破壞圖的連通性，則稱此圖的連通度為k。關節(jié)點和重連通圖在實際中

較多應用。顯然，一個表示通信網(wǎng)絡的圖的連通度越高，其系統(tǒng)越可靠，無論是哪一個站點

出現(xiàn)故障或遭到外界破壞，都不影響系統(tǒng)的正常工作；又如，一個航空網(wǎng)若是重連通的，則

當某條航線因天氣等某種原因關閉時，旅客仍可從別的航線繞道而行；再如，若將大規(guī)模的

集成電路的關鍵線路設計成重連通的話，則在某些元件失效的情況下，整個片子的功能不受

影響，反之，在戰(zhàn)爭中，若要摧毀敵方的運輸線，僅需破壞其運輸網(wǎng)中的關節(jié)點即可。

例如，圖8.21(a)中圖G7是連通圖，但不是重連通圖。圖中有四個關節(jié)點A、B和G。

若刪去頂點B以及所有依附頂點B的邊，G7就被分割成三個連通分量{A、C、F、L、M、

J}、{G、H、I、K}和{D、E}。類似地，若刪去頂點A或D或G以及所依附于它們的邊，

則G7被分割成兩個連通分量，由此，關節(jié)點亦稱為割點。

(a)一個連通圖無向圖G7(b)G7的深度優(yōu)先生成樹

圖8.21無向連通圖G7及其生成樹

利用深度優(yōu)先搜索便可求得圖的關節(jié)點，并由此可判別圖是否是重連通的。

圖&21(b)所示為從頂點A出發(fā)深優(yōu)先生成樹，圖中實線表示樹邊，虛線表示回邊(即

不在生成樹上的邊)。對樹中任一頂點v而言，其孩子結點為在它之后搜索到的鄰接點，而

其雙親結點和由回邊連接的祖先結點是在它之前搜索到的鄰接點。由深度優(yōu)先生成樹可得出

兩類關節(jié)點的特性：

(1)若生成樹的根有兩棵或兩棵以上的子樹，則此根頂點必為關節(jié)點。因為圖中不存

在聯(lián)結不同子樹中頂點的邊，因此，若刪去根頂點，生成樹便變成生成森林。如圖8.21(b)中

的頂點A?

(2)若生成樹中某個非葉子頂點V,其某棵子樹的根和子樹中的其它結點均沒有指向v

的祖先的回邊，則v為關節(jié)點。因為，若刪去v,則其子樹和圖的其它部分被分割開來。如

圖8.21(b)中的頂點B和Go

若對圖Graph=(V,{Edge))重新定義遍歷時的訪問函數(shù)visited,并引入一個新的函數(shù)

low,則由一次深度優(yōu)先遍歷便可求得連通圖中存在的所有關節(jié)點。

定義visited[v]為深度優(yōu)先搜索遍歷連通圖時訪問頂點v的次序號；定義：

w是v在DFS生成樹上的孩子結點；

low(v)=MinJvivited[v]Jow[w],visited[k]k是v在DFS生成樹上由回邊聯(lián)結的祖先結點;

(v,w)eEdgc;

(v,k)GEdge,

若對于某個頂點v,存在孩子結點w且low[w]工visited[v],則該頂點v必為關節(jié)點。因為當

w是v的孩子結點時，lowfw]工visiled[v],表明w及其子孫均無指向v的祖先的回邊。

由定義可知，visited,]值即為v在深度優(yōu)先生成樹的前序序列的序號，只需將DFS函

數(shù)中頭兩個語句改為visiled[vO]=++coum(在DFSTraverse中設初值count=l)即可；low[v]

可由后序遍歷深度優(yōu)先生成樹求得，而v在后序序列中的次序和遍歷時退出DFS函數(shù)的次

序相同，由此修改深度優(yōu)先搜索遍歷的算法便可得到求關節(jié)點的算法(見算法8.12和算法

8.13)o

voidFindArticul(ALGraphG)

{/*連通圖G以鄰接表作存儲結構,查找并輸出G上全部關節(jié)點*/

count=l;/*全局變量count用于對訪問計數(shù)*/

visited[O]=l;/*設定鄰接表上。號頂點為生成樹的根*/

for(i=1;i<Gvexnum;++i)/*其余頂點尚未訪問*/

visited[i]=O;

p=G.adjlist[O].first;

v=p->adjvex;

DFSArticul(g,v);/*從頂點v出發(fā)深度優(yōu)先查找關節(jié)點*/

if(count<Gvexnum)/*生成樹的根至少有兩棵子樹*/

{printf(O,G.adjlist[O].vertex);/*根是關節(jié)點，輸出*/

while(p->next)

{p=p->next;

v=p->adjvex;

if(visited[v]==O)DFSArticul(g,v);

}/*FindArticul*/

算法8.12

voidDFSArticul(ALGraphQintvO)

/*從頂點vO出發(fā)深度優(yōu)先遍歷圖G,查找并輸出關節(jié)點*/

{visited[vO]=min=++count;/*v0是第count個訪問的頂點*/

for(p=G.adjlist[v01.firstedge;p;p=p->next;)/*對vO的每個鄰接點檢查*/

{w=p->adjvex;/*w為vO的鄰接點*/

if(visited[w]==O)/*若w未曾訪問，則w為vO的孩子*/

{DFSArticul(G,w);/*返回前求得low[w]*/

if(low[w]<min)min=low[w];

if(low[w]>=visited[vO])printf(vO,Gadjlist[vO].vertex);/*輸出關節(jié)點*/

}

elseif(visited[w]<min)min=visited[w];/*w已訪問，w是vO在生成樹上的祖先*/

)

low[vO]=min;

)

算法8.13

例如，圖G7中各頂點計算所得visited和low的函數(shù)值如下所列:

i0123456789101112

Gadjlist[i].vertexABCDEFGHIJKLM

visited[i]15121011138694723

low[i]1115515582511

求得low值的順序13987612352141110

其中J是第一個求得low值的頂點，由于存在回邊(J,L),則low[J]=Min{visited[J]>

visited[]}=2。順便提一句，上述算法中將指向雙親的樹邊也看成是回邊，由于不影響關節(jié)

點的判別，因此，為使算法簡明起見，在算法中沒有區(qū)別之。

由于上述算法的過程就是一個遍歷的過程，因此，求關節(jié)點的時間復雜度仍為O(n+e)。

8.5最小生成樹

8.5.1最小生成樹的基本概念

由生成樹的定義可知，無向連通圖的生成樹不是唯一的。連通圖的一次遍歷所經(jīng)過的邊

的集合及圖中所有頂點的集合就構成了該圖的一棵生成樹，對連通圖的不同遍歷，就可能得

到不同的生成樹。圖8.22(a)、(b)和(c)所示的均為圖8.17的無向連通圖的生成樹。

圖8.22無向連通圖G5的三棵生成樹

可以證明，對于有n個頂點的無向連通圖，無論其生成樹的形態(tài)如何，所有生成樹中都

有且僅有n—l條邊。

如果無向連通圖是一個網(wǎng)，那么，它的所有生成樹中必有一棵邊的權值總和最小的生成

樹，我們稱這棵生成樹為最小生成樹，簡稱為最小生成樹。

最小生成樹的概念可以應用到許多實際問題中。例如有這樣一個問題：以盡可能抵的總

造價建造城市間的通訊網(wǎng)絡，把十個城市聯(lián)系在一起。在這十個城市中，任意兩個城市之間

都可以建造通訊線路，通訊線路的造價依據(jù)城市間的距離不同而有不同的造價，可以構造一

個通訊線路造價網(wǎng)絡，在網(wǎng)絡中，每個頂點表示城市，頂點之間的邊表示城市之間可構造通

訊線路，每條邊的權值表示該條通訊線路的造價，要想使總的造價最低，實際上