另一種叫做廣度優(yōu)先搜索法課件

8.1圖的基本概念第8章圖8.2圖的存儲結(jié)構(gòu)8.3圖的遍歷8.4生成樹和最小生成樹8.5最短路徑8.6拓?fù)渑判?.7AOE網(wǎng)與關(guān)鍵路徑本章小結(jié)8.1圖的基本概念第8章圖8.2圖的存儲結(jié)構(gòu)8.8.1圖的基本概念8.1.1圖的定義

圖（Graph）G由兩個集合V（vertex）和E（Edge）組成，記為G=(V，E)，其中V是頂點(diǎn)的有限集合，記為V(G)，E是連接V中兩個不同頂點(diǎn)（頂點(diǎn)對）的邊的有限集合，記為E(G)。

和離散數(shù)學(xué)中采用的方法相同，通過頂點(diǎn)集和邊集來表示一個圖的邏輯結(jié)構(gòu)，實際上就是二元組表示。8.1圖的基本概念和離散數(shù)學(xué)中采用的方法相同，通過頂

在圖G中，如果代表邊的頂點(diǎn)對是無序的，則稱G為無向圖，無向圖中代表邊的無序頂點(diǎn)對通常用圓括號括起來，用以表示一條無向邊。如果表示邊的頂點(diǎn)對是有序的，則稱G為有向圖，在有向圖中代表邊的頂點(diǎn)對通常用尖括號括起來。

說明：對于n個頂點(diǎn)的圖，對每個頂點(diǎn)連續(xù)編號，即頂點(diǎn)的編號為0－n-1。通過編號唯一確定一個頂點(diǎn)。在圖G中，如果代表邊的頂點(diǎn)對是無序的，則稱G為無8.1.2圖的基本術(shù)語

1.端點(diǎn)和鄰接點(diǎn)

在一個無向圖中，若存在一條邊(i，j)，則稱頂點(diǎn)i和頂點(diǎn)j為此邊的兩個端點(diǎn)，并稱它們互為鄰接點(diǎn)。

在一個有向圖中，若存在一條邊<i，j>，則稱此邊是頂點(diǎn)i的一條出邊，同時也是頂點(diǎn)j的一條入邊；稱頂點(diǎn)i和頂點(diǎn)j分別為此邊的起始端點(diǎn)（簡稱為起點(diǎn)）和終止端點(diǎn)（簡稱終點(diǎn)）；稱頂點(diǎn)i

和頂點(diǎn)j

互為鄰接點(diǎn)。13024(a)13024(b)8.1.2圖的基本術(shù)語13024(a)13024(b)2.頂點(diǎn)的度、入度和出度

在無向圖中，頂點(diǎn)所具有的邊的數(shù)目稱為該頂點(diǎn)的度。在有向圖中，以頂點(diǎn)i為終點(diǎn)的入邊的數(shù)目，稱為該頂點(diǎn)的入度。以頂點(diǎn)i為始點(diǎn)的出邊的數(shù)目，稱為該頂點(diǎn)的出度。一個頂點(diǎn)的入度與出度的和為該頂點(diǎn)的度。若一個圖中有n個頂點(diǎn)和e條邊，每個頂點(diǎn)的度為di（1≤i≤n），則有：13024(a)13024(b)2.頂點(diǎn)的度、入度和出度13024(a)13024(b

例．一個無向連通圖中有16條邊，所有頂點(diǎn)的度均小于5，度為4的頂點(diǎn)有3個，度為3的頂點(diǎn)有4個，度為2的頂點(diǎn)有2個，則該圖有

個頂點(diǎn)。A.10 B.11 C.12 D.13解：設(shè)該圖有n個頂點(diǎn)，圖中度為i的頂點(diǎn)數(shù)為ni（0≤i≤4），顯然n0=0，n=3+4+2+n1+n0=9+n1，而度之和=4×3+3×4+2×2+n1=28+n1，而度之和=2e=32，所以有28+n1=32，得n1=4，n=9+n1=13。本題答案為D。例．一個無向連通圖中有16條邊，所有頂點(diǎn)的度均小于5，度為3.完全圖

若無向圖中的每兩個頂點(diǎn)之間都存在著一條邊，有向圖中的每兩個頂點(diǎn)之間都存在著方向相反的兩條邊，則稱此圖為完全圖。顯然，完全無向圖包含有條邊，完全有向圖包含有n(n-1)條邊。例如，圖(a)所示的圖是一個具有4個頂點(diǎn)的完全無向圖，共有6條邊。圖(b)所示的圖是一個具有4個頂點(diǎn)的完全有向圖，共有12條邊。

(b)10231023(a)3.完全圖(b)10231023(a)4.稠密圖、稀疏圖

當(dāng)一個圖接近完全圖時，則稱為稠密圖。相反，當(dāng)一個圖含有較少的邊數(shù)（即當(dāng)e<<n(n-1)）時，則稱為稀疏圖。

5.子圖

設(shè)有兩個圖G=(V，E)和G’=(V’，E’)，若V’是V的子集，即V’V，且E’是E的子集，即E’E，則稱G’是G的子圖。例如圖(b)是圖(a)的子圖，而圖(c)不是圖(a)的子圖。(a)1302413024(b)13024(c)注意：G中V的子集和E的子集并不一定構(gòu)成G的子圖。4.稠密圖、稀疏圖(a)1302413024(b)1306.路徑和路徑長度

在一個圖G=(V，E)中，從頂點(diǎn)i到頂點(diǎn)j的一條路徑是一個頂點(diǎn)序列(i,i1,i2,…,im,j)，若此圖G是無向圖，則邊(i,i1)，(i1,i2)，…，(im-1,im)，(im,j)屬于E(G)；若此圖是有向圖，則<i,i1>，<i1,i2>，…，<im-1,im>，<im,j>屬于E(G)。

路徑長度是指一條路徑上經(jīng)過的邊的數(shù)目。若一條路徑上除開始點(diǎn)和結(jié)束點(diǎn)可以相同外，其余頂點(diǎn)均不相同，則稱此路徑為簡單路徑。例如，有圖中，(0，2，1)就是一條簡單路徑，其長度為2。10236.路徑和路徑長度10237.回路或環(huán)

若一條路徑上的開始點(diǎn)與結(jié)束點(diǎn)為同一個頂點(diǎn)，則此路徑被稱為回路或環(huán)。開始點(diǎn)與結(jié)束點(diǎn)相同的簡單路徑被稱為簡單回路或簡單環(huán)。例如，右圖中，(0，2，1，0)就是一條簡單回路，其長度為3。10237.回路或環(huán)10238.連通、連通圖和連通分量

在無向圖G中，若從頂點(diǎn)i到頂點(diǎn)j有路徑，則稱頂點(diǎn)i和j是連通的。若圖G中任意兩個頂點(diǎn)都連通，則稱G為連通圖，否則稱為非連通圖。無向圖G中的極大連通子圖稱為G的連通分量。顯然，任何連通圖的連通分量只有一個，即本身，而非連通圖有多個連通分量。1023102(b)(a)38.連通、連通圖和連通分量1023102(b)(a)9.強(qiáng)連通圖和強(qiáng)連通分量

在有向圖G中，若從頂點(diǎn)i到頂點(diǎn)j有路徑，則稱從頂點(diǎn)i到j(luò)是連通的。

若圖G中的任意兩個頂點(diǎn)i和j都連通，即從頂點(diǎn)i到j(luò)和從頂點(diǎn)j到i都存在路徑，則稱圖G是強(qiáng)連通圖。有向圖G中的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。顯然，強(qiáng)連通圖只有一個強(qiáng)連通分量，即本身，非強(qiáng)連通圖有多個強(qiáng)連通分量。1023(b)(a)10239.強(qiáng)連通圖和強(qiáng)連通分量1023(b)(a)102310.權(quán)和網(wǎng)

圖中每一條邊都可以附有一個對應(yīng)的數(shù)值，這種與邊相關(guān)的數(shù)值稱為權(quán)。權(quán)可以表示從一個頂點(diǎn)到另一個頂點(diǎn)的距離或花費(fèi)的代價。邊上帶有權(quán)的圖稱為帶權(quán)圖，也稱作網(wǎng)。10.權(quán)和網(wǎng)

例8.1

有n個頂點(diǎn)的有向強(qiáng)連通圖最多需要多少條邊？最少需要多少條邊？

解：有n個頂點(diǎn)的有向強(qiáng)連通圖最多有n(n-1)條邊（構(gòu)成一個有向完全圖的情況）；最少有n條邊（n個頂點(diǎn)依次首尾相接構(gòu)成一個環(huán)的情況）。

012n-2n-1…例8.1有n個頂點(diǎn)的有向強(qiáng)連通圖最多需要多8.2圖的存儲結(jié)構(gòu)

8.2.1鄰接矩陣存儲方法

鄰接矩陣是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V，E)是具有n（n＞0）個頂點(diǎn)的圖，頂點(diǎn)的順序依次為0～n-1，則G的鄰接矩陣A是n階方陣，其定義如下：（1）如果G是無向圖，則：

A[i][j]=1：若(i,j)∈E(G)0:其他（2）如果G是有向圖，則：

A[i][j]=1：若<i,j>∈E(G)0:其他8.2圖的存儲結(jié)構(gòu)8.2.1鄰接矩陣存儲方法（3）如果G是帶權(quán)無向圖，則：

A[i][j]=wij

：若i≠j且(i,j)∈E(G)0：i=j∞：其他（4）如果G是帶權(quán)有向圖，則：

A[i][j]=wij

：若i≠j且<i,j>∈E(G)0：i=j∞：其他注意：帶權(quán)圖和不帶權(quán)圖表示的元素類型不同。帶權(quán)圖（不論有向還是無向圖）A[i][j]用double表示，不帶權(quán)圖（不論有向還是無向圖）A[i][j]用int表示。（3）如果G是帶權(quán)無向圖，則：注意：帶權(quán)圖和不帶權(quán)圖表示的元1320413204A1＝0123401234A2＝0123401234對稱不對稱1320413204A1＝0123思考題：

（1）對于有n個頂點(diǎn)e條邊的無向圖，鄰接矩陣表示時有多少個元素，多少個非0元素？（2）對于有n個頂點(diǎn)e條邊的有向圖，鄰接矩陣表示時有多少個元素，多少個非0元素？思考題：鄰接矩陣的特點(diǎn)如下：

（1）圖的鄰接矩陣表示是唯一的。（2）無向圖的鄰接矩陣一定是一個對稱矩陣。因此，按照壓縮存儲的思想，在具體存放鄰接矩陣時只需存放上（或下）三角形陣的元素即可。（3）不帶權(quán)的有向圖的鄰接矩陣一般來說是一個稀疏矩陣，因此，當(dāng)圖的頂點(diǎn)較多時，可以采用三元組表的方法存儲鄰接矩陣。（4）對于無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數(shù)正好是第i個頂點(diǎn)的度。鄰接矩陣的特點(diǎn)如下：

（5）對于有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非∞元素）的個數(shù)正好是第i個頂點(diǎn)的出度（或入度）。（6）用鄰接矩陣方法存儲圖，很容易確定圖中任意兩個頂點(diǎn)之間是否有邊相連。但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進(jìn)行檢測，所花費(fèi)的時間代價很大。這是用鄰接矩陣存儲圖的局限性。（5）對于有向圖，鄰接矩陣的第i行（或第i列鄰接矩陣的數(shù)據(jù)類型定義如下：#defineMAXV<最大頂點(diǎn)個數(shù)> typedefstruct{intno; //頂點(diǎn)編號

InfoTypeinfo; //頂點(diǎn)其他信息}VertexType; //頂點(diǎn)類型typedefstruct //圖的定義{intedges[MAXV][MAXV]; //鄰接矩陣

intn，e; //頂點(diǎn)數(shù)，弧數(shù)

VertexTypevexs[MAXV]; //存放頂點(diǎn)信息}MGraph; //圖的鄰接矩陣表示類型鄰接矩陣的數(shù)據(jù)類型定義如下：8.2.2鄰接表存儲方法

圖的鄰接表存儲方法是一種順序分配與鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲方法。在鄰接表中，對圖中每個頂點(diǎn)建立一個單鏈表，第i個單鏈表中的節(jié)點(diǎn)表示依附于頂點(diǎn)i的邊（對有向圖是以頂點(diǎn)i為尾的邊）。每個單鏈表上附設(shè)一個表頭節(jié)點(diǎn)。邊表節(jié)點(diǎn)表頭節(jié)點(diǎn)adjvexnextarcinfodatafirstarc8.2.2鄰接表存儲方法adjvexnextarcinftypedefstructANode{intadjvex; //該邊的終點(diǎn)編號

structANode*nextarc; //指向下一條邊的指針

InfoTypeinfo; //該邊的相關(guān)信息}ArcNode; //邊表節(jié)點(diǎn)類型typedefstructVnode{Vertexdata; //頂點(diǎn)信息

ArcNode*firstarc; //指向第一條邊}VNode; //鄰接表頭節(jié)點(diǎn)類型typedefVNodeAdjList[MAXV]; //AdjList是鄰接表類型typedefstruct{AdjListadjlist; //鄰接表

intn,e; //圖中頂點(diǎn)數(shù)n和邊數(shù)e}ALGraph; //完整的圖鄰接表類型typedefstructANode

其中，表節(jié)點(diǎn)由三個域組成，adjvex指示與頂點(diǎn)i鄰接的點(diǎn)在圖中的位置，nextarc指示下一條邊或弧的節(jié)點(diǎn)，info存儲與邊或弧相關(guān)的信息，如權(quán)值等。表頭節(jié)點(diǎn)由兩個域組成，data存儲頂點(diǎn)i的名稱或其他信息，firstarc指向鏈表中第一個節(jié)點(diǎn)。其中，表節(jié)點(diǎn)由三個域組成，adjvex指示與1320413204datafirstarcadjvexnext表頭節(jié)點(diǎn)邊表節(jié)點(diǎn)1320413204datafirstarcadjve思考題：

（1）對于有n個頂點(diǎn)e條邊的無向圖，鄰接表表示時有多少個表頭節(jié)點(diǎn)，多少個表節(jié)點(diǎn)？（2）對于有n個頂點(diǎn)e條邊的有向圖，鄰接表表示時有多少個表頭節(jié)點(diǎn)，多少個表節(jié)點(diǎn)？思考題：鄰接表的特點(diǎn)如下：

（1）鄰接表表示不唯一。這是因為在每個頂點(diǎn)對應(yīng)的單鏈表中，各邊節(jié)點(diǎn)的鏈接次序可以是任意的，取決于建立鄰接表的算法以及邊的輸入次序。（2）對于有n個頂點(diǎn)和e條邊的無向圖，其鄰接表有n個頂點(diǎn)節(jié)點(diǎn)和2e個邊節(jié)點(diǎn)。顯然，在總的邊數(shù)小于n(n-1)/2的情況下，鄰接表比鄰接矩陣要節(jié)省空間。（3）對于無向圖，鄰接表的頂點(diǎn)i對應(yīng)的第i個鏈表的邊節(jié)點(diǎn)數(shù)目正好是頂點(diǎn)i的度。（4）對于有向圖，鄰接表的頂點(diǎn)i對應(yīng)的第i個鏈表的邊節(jié)點(diǎn)數(shù)目僅僅是頂點(diǎn)i的出度。其入度為鄰接表中所有adjvex域值為i的邊節(jié)點(diǎn)數(shù)目。鄰接表的特點(diǎn)如下：

例8.2

給定一個具有n個節(jié)點(diǎn)的無向圖的鄰接矩陣和鄰接表。（1）設(shè)計一個將鄰接矩陣轉(zhuǎn)換為鄰接表的算法；（2）設(shè)計一個將鄰接表轉(zhuǎn)換為鄰接矩陣的算法；（3）分析上述兩個算法的時間復(fù)雜度。解：（1）在鄰接矩陣上查找值不為0的元素，找到這樣的元素后創(chuàng)建一個表節(jié)點(diǎn)并在鄰接表對應(yīng)的單鏈表中采用前插法插入該節(jié)點(diǎn)。算法如下：例8.2給定一個具有n個節(jié)點(diǎn)的無向圖的鄰接矩voidMatToList(MGraphg，ALGraph*&G)//將鄰接矩陣g轉(zhuǎn)換成鄰接表G{inti，j，n=g.eexnum;ArcNode*p; //n為頂點(diǎn)數(shù)

G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<n;i++)//給所有頭節(jié)點(diǎn)的指針域置初值

G->adjlist[i].firstarc=NULL;for(i=0;i<n;i++) //檢查鄰接矩陣中每個元素

for(j=n-1;j>=0;j--)if(g.edges[i][j]!=0) {p=(ArcNode*)malloc(sizeof(ArcNode));

//創(chuàng)建節(jié)點(diǎn)*p p->adjvex=j; p->nextarc=G->adjlist[i].firstarc;

//將*p鏈到鏈表頭

G->adjlist[i].firstarc=p; }G->n=n;G->e=g.e;}voidMatToList(MGraphg，ALGrap

（2）在鄰接表上查找相鄰節(jié)點(diǎn)，找到后修改相應(yīng)鄰接矩陣元素的值。算法如下：

voidListToMat(ALGraph*G，MGraph&g){inti，j，n=G->n;ArcNode*p;for(i=0;i<n;i++){p=G->adjlist[i].firstarc;while(p!=NULL) {g.edges[i][p->adjvex]=1; p=p->nextarc; }}g.n=n;g.e=G->e;}（2）在鄰接表上查找相鄰節(jié)點(diǎn)，找到后修改相應(yīng)鄰接矩陣

（3）算法1的時間復(fù)雜度均為O(n2)。算法2的時間復(fù)雜度為O(n+e)，其中e為圖的邊數(shù)。（3）算法1的時間復(fù)雜度均為O(n2)。圖的鄰接矩陣的操作利用鄰接矩陣定義的數(shù)據(jù)結(jié)構(gòu)，可以方便地實現(xiàn)圖的各種操作。(1)圖的創(chuàng)建AdjGraph*Create_Graph(MGraph*G){printf(“請輸入圖的種類標(biāo)志：”);scanf(“%d”,&G->kind);G->vexnum=0;/*初始化頂點(diǎn)個數(shù)*/return(G);}圖的鄰接矩陣的操作(2)圖的頂點(diǎn)定位圖的頂點(diǎn)定位操作實際上是確定一個頂點(diǎn)在vexs數(shù)組中的位置(下標(biāo))，其過程完全等同于在順序存儲的線性表中查找一個數(shù)據(jù)元素。算法實現(xiàn)：intLocateVex(MGraph*G,VexType*vp){intk;for(k=0;k<G->vexnum;k++)if(G->vexs[k]==*vp)return(k);return(-1);/*圖中無此頂點(diǎn)*/

}(2)圖的頂點(diǎn)定位(3)向圖中增加頂點(diǎn)向圖中增加一個頂點(diǎn)的操作，類似在順序存儲的線性表的末尾增加一個數(shù)據(jù)元素。算法實現(xiàn)：intAddVertex(MGraph*G,VexType*vp){intk,j;if(G->vexnum>=MAX_VEX){printf(“VertexOverflow!\n”);return(-1);}if(LocateVex(G,vp)!=-1){printf(“Vertexhasexisted!\n”);return(-1);}k=G->vexnum;G->vexs[G->vexnum++]=*vp;(3)向圖中增加頂點(diǎn)if(G->kind==DG||G->kind==AG)for(j=0;j<G->vexnum;j++)G->adj[j][k].ArcVal=G->adj[k][j].ArcVal=0;

/*是不帶權(quán)的有向圖或無向圖*/elsefor(j=0;j<G->vexnum;j++){G->adj[j][k].ArcVal=INFINITY;G->adj[k][j].ArcVal=INFINITY;

/*是帶權(quán)的有向圖或無向圖*/}return(k);}if(G->kind==DG||G->kind==AG)(4)向圖中增加一條弧根據(jù)給定的弧或邊所依附的頂點(diǎn)，修改鄰接矩陣中所對應(yīng)的數(shù)組元素。算法實現(xiàn)：intAddArc(MGraph*G,ArcType*arc){intk,j;k=LocateVex(G,&arc->vex1);j=LocateVex(G,&arc->vex1);if(k==-1||j==-1){printf(“Arc’sVertexdonotexisted!\n”);return(-1);}(4)向圖中增加一條弧if(G->kind==DG||G->kind==WDG){G->adj[k][j].ArcVal=arc->ArcVal;G->adj[k][j].ArcInfo=arc->ArcInfo;

/*是有向圖或帶權(quán)的有向圖*/}else{G->adj[k][j].ArcVal=arc->ArcVal;G->adj[j][k].ArcVal=arc->ArcVal;G->adj[k][j].ArcInfo=arc->ArcInfo;G->adj[j][k].ArcInfo=arc->ArcInfo;

/*是無向圖或帶權(quán)的無向圖,需對稱賦值*/}return(1);}if(G->kind==DG||G->kind==WDG)利用鄰接鏈表存儲結(jié)構(gòu)描述，可方便地實現(xiàn)圖的基本操作。(1)圖的創(chuàng)建ALGraph*Create_Graph(ALGraph*G){printf(“請輸入圖的種類標(biāo)志：”);scanf(“%d”,&G->kind);G->vexnum=0;/*初始化頂點(diǎn)個數(shù)*/return(G);}利用鄰接鏈表存儲結(jié)構(gòu)描述，可方便地實現(xiàn)圖的基本操作(2)圖的頂點(diǎn)定位圖的頂點(diǎn)定位實際上是確定一個頂點(diǎn)在AdjList數(shù)組中的某個元素的data域內(nèi)容。算法實現(xiàn)：intLocateVex(ALGraph*G,VexType*vp){intk;for(k=0;k<G->vexnum;k++)if(G->AdjList[k].data==*vp)return(k);return(-1);/*圖中無此頂點(diǎn)*/}(2)圖的頂點(diǎn)定位(3)向圖中增加頂點(diǎn)向圖中增加一個頂點(diǎn)的操作，在AdjList數(shù)組的末尾增加一個數(shù)據(jù)元素。算法實現(xiàn)：intAddVertex(ALGraph*G,VexType*vp){intk,j;if(G->vexnum>=MAX_VEX){printf(“VertexOverflow!\n”);return(-1);}if(LocateVex(G,vp)!=-1){printf(“Vertexhasexisted!\n”);return(-1);}G->AdjList[G->vexnum].data=*vp;(3)向圖中增加頂點(diǎn)G->AdjList[G->vexnum].degree=0;G->AdjList[G->vexnum].firstarc=NULL;k=++G->vexnum;return(k);}(4)向圖中增加一條弧根據(jù)給定的弧或邊所依附的頂點(diǎn)，修改單鏈表：無向圖修改兩個單鏈表；有向圖修改一個單鏈表。算法實現(xiàn)：intAddArc(ALGraph*G,ArcType*arc){intk,j;LinkNode*p,*q;G->AdjList[G->vexnum].degree=0k=LocateVex(G,&arc->vex1);j=LocateVex(G,&arc->vex2);if(k==-1||j==-1){printf(“Arc’sVertexdonotexisted!\n”);return(-1);}p=(LinkNode*)malloc(sizeof(LinkNode));p->adjvex=arc->vex1;p->info=arc->info;p->nextarc=NULL;/*邊的起始表結(jié)點(diǎn)賦值*/q=(LinkNode*)malloc(sizeof(LinkNode));q->adjvex=arc->vex2;q->info=arc->info;q->nextarc=NULL;/*邊的末尾表結(jié)點(diǎn)賦值*/k=LocateVex(G,&arc->vex1);if(G->kind==AG||G->kind==WAG){q->nextarc=G->adjlist[k].firstarc;G->adjlist[k].firstarc=q;p->nextarc=G->adjlist[j].firstarc;G->adjlist[j].firstarc=p;}/*是無向圖,用頭插入法插入到兩個單鏈表*/else/*建立有向圖的鄰接鏈表,用頭插入法*/{q->nextarc=G->adjlist[k].firstarc;G->adjlist[k].firstarc=q;/*建立正鄰接鏈表用*///q->nextarc=G->adjlist[j].firstarc;//G->adjlist[j].firstarc=q;/*建立逆鄰接鏈表用*/}return(1);}if(G->kind==AG||G->kind==WAG)十字鏈表法十字鏈表(OrthogonalList)是有向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)，是將有向圖的正鄰接表和逆鄰接表結(jié)合起來得到的一種鏈表。在這種結(jié)構(gòu)中，每條弧的弧頭結(jié)點(diǎn)和弧尾結(jié)點(diǎn)都存放在鏈表中，并將弧結(jié)點(diǎn)分別組織到以弧尾結(jié)點(diǎn)為頭(頂點(diǎn))結(jié)點(diǎn)和以弧頭結(jié)點(diǎn)為頭(頂點(diǎn))結(jié)點(diǎn)的鏈表中。這種結(jié)構(gòu)的結(jié)點(diǎn)邏輯結(jié)構(gòu)如圖7-12所示?；〗Y(jié)點(diǎn)tailvexheadvexinfohlinktlink頂點(diǎn)結(jié)點(diǎn)Datafirstinfirstout圖7-12十字鏈表結(jié)點(diǎn)結(jié)構(gòu)十字鏈表法十字鏈表(OrthogonalLi◆

data域：存儲和頂點(diǎn)相關(guān)的信息；◆指針域firstin：指向以該頂點(diǎn)為弧頭的第一條弧所對應(yīng)的弧結(jié)點(diǎn)；◆指針域firstout：指向以該頂點(diǎn)為弧尾的第一條弧所對應(yīng)的弧結(jié)點(diǎn)；◆尾域tailvex：指示弧尾頂點(diǎn)在圖中的位置；◆頭域headvex：指示弧頭頂點(diǎn)在圖中的位置；◆指針域hlink：指向弧頭相同的下一條?。弧糁羔樣騮link：指向弧尾相同的下一條?。弧鬒nfo域：指向該弧的相關(guān)信息；◆data域：存儲和頂點(diǎn)相關(guān)的信息；結(jié)點(diǎn)類型定義#defineINFINITYMAX_VAL/*最大值∞*/#defineMAX_VEX30//最大頂點(diǎn)數(shù)typedefstructArcNode{inttailvex,headvex;//尾結(jié)點(diǎn)和頭結(jié)點(diǎn)在圖中的位置InfoTypeinfo;//與弧相關(guān)的信息,如權(quán)值structArcNode*hlink,*tlink;}ArcNode;/*弧結(jié)點(diǎn)類型定義*/typedefstructVexNode{VexTypedata;//頂點(diǎn)信息ArcNode*firstin,*firstout;}VexNode;/*頂點(diǎn)結(jié)點(diǎn)類型定義*/結(jié)點(diǎn)類型定義typedefstruct{intvexnum;VexNodexlist[MAX_VEX];}OLGraph;/*圖的類型定義*/

下圖所示是一個有向圖及其十字鏈表(略去了表結(jié)點(diǎn)的info域)。從這種存儲結(jié)構(gòu)圖可以看出，從一個頂點(diǎn)結(jié)點(diǎn)的firstout出發(fā)，沿表結(jié)點(diǎn)的tlink指針構(gòu)成了正鄰接表的鏈表結(jié)構(gòu)，而從一個頂點(diǎn)結(jié)點(diǎn)的firstin出發(fā)，沿表結(jié)點(diǎn)的hlink指針構(gòu)成了逆鄰接表的鏈表結(jié)構(gòu)。typedefstructV0V1V2V30102∧2023∧∧30∧31∧32∧∧0213V0V1∧V2V3有向圖的十字鏈表結(jié)構(gòu)V0V1V2V30102∧2023鄰接多重表鄰接多重表(AdjacencyMultilist)是無向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。鄰接表是無向圖的一種有效的存儲結(jié)構(gòu)，在無向圖的鄰接表中，一條邊(v,w)的兩個表結(jié)點(diǎn)分別初選在以v和w為頭結(jié)點(diǎn)的鏈表中，很容易求得頂點(diǎn)和邊的信息，但在涉及到邊的操作會帶來不便。鄰接多重表的結(jié)構(gòu)和十字鏈表類似，每條邊用一個結(jié)點(diǎn)表示；鄰接多重表中的頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)與鄰接表中的完全相同，而表結(jié)點(diǎn)包括六個域如圖7-14所示。datafirstedge頂點(diǎn)結(jié)點(diǎn)圖7-14鄰接多重表的結(jié)點(diǎn)結(jié)構(gòu)表結(jié)點(diǎn)markivexjvexinfoilinkjlink鄰接多重表鄰接多重表(AdjacencyMu◆

Data域：存儲和頂點(diǎn)相關(guān)的信息；◆

指針域firstedge：指向依附于該頂點(diǎn)的第一條邊所對應(yīng)的表結(jié)點(diǎn)；◆

標(biāo)志域mark：用以標(biāo)識該條邊是否被訪問過；◆

ivex和jvex域：分別保存該邊所依附的兩個頂點(diǎn)在圖中的位置；◆

info域：保存該邊的相關(guān)信息；◆

指針域ilink：指向下一條依附于頂點(diǎn)ivex的邊；◆

指針域jlink：指向下一條依附于頂點(diǎn)jvex的邊；◆Data域：存儲和頂點(diǎn)相關(guān)的信息；結(jié)點(diǎn)類型定義#defineINFINITYMAX_VAL/*最大值∞*/#defineMAX_VEX30/*最大頂點(diǎn)數(shù)*/typedefemnu{unvisited,visited}Visitting;typedefstructEdgeNode{Visittingmark;//訪問標(biāo)記intivex,jvex;//該邊依附的兩個結(jié)點(diǎn)在圖中的位置InfoTypeinfo;//與邊相關(guān)的信息,如權(quán)值structEdgeNode*ilink,*jlink;//分別指向依附于這兩個頂點(diǎn)的下一條邊}EdgeNode;/*弧邊結(jié)點(diǎn)類型定義*/結(jié)點(diǎn)類型定義typedefstructVexNode{VexTypedata;//頂點(diǎn)信息ArcNode*firsedge;//指向依附于該頂點(diǎn)的第一條邊}VexNode;/*頂點(diǎn)結(jié)點(diǎn)類型定義*/typedefstruct{intvexnum;VexNodemullist[MAX_VEX];}AMGraph;

下圖所示是一個無向圖及其鄰接多重表。typedefstructVexNode鄰接多重表與鄰接表的區(qū)別：

后者的同一條邊用兩個表結(jié)點(diǎn)表示，而前者只用一個表結(jié)點(diǎn)表示；除標(biāo)志域外，鄰接多重表與鄰接表表達(dá)的信息是相同的，因此，操作的實現(xiàn)也基本相似。圖7-15無向圖及其多重鄰接鏈表v1v2v3v4v1v2v3v40123

01

02∧

21∧

23

0∧3∧鄰接多重表與鄰接表的區(qū)別：圖7-15無向圖及其多重鄰接鏈圖的邊表存儲結(jié)構(gòu)在某些應(yīng)用中，有時主要考察圖中各個邊的權(quán)值以及所依附的兩個頂點(diǎn)，即圖的結(jié)構(gòu)主要由邊來表示，稱為邊表存儲結(jié)構(gòu)。在邊表結(jié)構(gòu)中，邊采用順序存儲，每個邊元素由三部分組成：邊所依附的兩個頂點(diǎn)和邊的權(quán)值；圖的頂點(diǎn)用另一個順序結(jié)構(gòu)的頂點(diǎn)表存儲。如圖所示。邊表存儲結(jié)構(gòu)的形式描述如下：#defineINFINITYMAX_VAL/*最大值∞*/#defineMAX_VEX30/*最大頂點(diǎn)數(shù)*/#defineMAX_EDGE100/*最大邊數(shù)*/圖的邊表存儲結(jié)構(gòu)在某些應(yīng)用中，有時主要考察圖中typedefstructENode{intivex,jvex;/*邊所依附的兩個頂點(diǎn)*/WeightTypeweight;/*邊的權(quán)值*/}ENode;/*邊表元素類型定義*/typedefstruct{intvexnum,edgenum;/*頂點(diǎn)數(shù)和邊數(shù)*/VexTypevexlist[MAX_VEX];/*頂點(diǎn)表*/ENodeedgelist[MAX_EDGE];/*邊表*/

}ELGraph;

typedefstructENode無向圖的邊表表示v0v2v4v3v16742398頂點(diǎn)表v0v1v2v3v401234邊表132149238243344027016無向圖的邊表表示v0v2v4v3v16742398頂點(diǎn)表v08.3圖的遍歷8.3.1圖的遍歷的概念

從給定圖中任意指定的頂點(diǎn)（稱為初始點(diǎn)）出發(fā)，按照某種搜索方法沿著圖的邊訪問圖中的所有頂點(diǎn)，使每個頂點(diǎn)僅被訪問一次，這個過程稱為圖的遍歷。如果給定圖是連通的無向圖或者是強(qiáng)連通的有向圖，則遍歷過程一次就能完成，并可按訪問的先后順序得到由該圖所有頂點(diǎn)組成的一個序列。根據(jù)搜索方法的不同，圖的遍歷方法有兩種：一種叫做深度優(yōu)先搜索法（DFS）；另一種叫做廣度優(yōu)先搜索法（BFS）。8.3圖的遍歷深度優(yōu)先搜索遍歷的過程是：（1）從圖中某個初始頂點(diǎn)v出發(fā)，首先訪問初始頂點(diǎn)v。（2）選擇一個與頂點(diǎn)v相鄰且沒被訪問過的頂點(diǎn)w為初始頂點(diǎn)，再從w出發(fā)進(jìn)行深度優(yōu)先搜索，直到圖中與當(dāng)前頂點(diǎn)v鄰接的所有頂點(diǎn)都被訪問過為止。8.3.2深度優(yōu)先搜索遍歷

以鄰接表為存儲結(jié)構(gòu)的深度優(yōu)先搜索遍歷算法如下（其中，v是初始頂點(diǎn)編號，visited[]是一個全局?jǐn)?shù)組，初始時所有元素均為0表示所有頂點(diǎn)尚未訪問過）：體現(xiàn)出后進(jìn)先出的特點(diǎn)：用?；蜻f歸方式實現(xiàn)。vw…深度優(yōu)先搜索遍歷的過程是：8.3.2深度優(yōu)先搜索遍歷voidDFS(ALGraph*G，intv){ArcNode*p;intw;visited[v]=1; //置已訪問標(biāo)記

printf("%d"，v); //輸出被訪問頂點(diǎn)的編號

p=G->adjlist[v].firstarc; //p指向頂點(diǎn)v的第一條邊的邊頭節(jié)點(diǎn)

while(p!=NULL){w=p->adjvex; if(visited[w]==0)

DFS(G，w); //若w頂點(diǎn)未訪問，遞歸訪問它

p=p->nextarc; //p指向頂點(diǎn)v的下一條邊的邊頭節(jié)點(diǎn)

}}思考題：為什么visited數(shù)組需要設(shè)置為全局變量？voidDFS(ALGraph*G，intv)思考另一種叫做廣度優(yōu)先搜索法課件DFS序列：21034DFS序列：21034思考題：用棧求解迷宮問題，有DFS算法有什么關(guān)聯(lián)？思考題：廣度優(yōu)先搜索遍歷的過程是：（1）訪問初始點(diǎn)v，接著訪問v的所有未被訪問過的鄰接點(diǎn)v1，v2，…，vt。（2）按照v1，v2，…，vt的次序，訪問每一個頂點(diǎn)的所有未被訪問過的鄰接點(diǎn)。（3）依次類推，直到圖中所有和初始點(diǎn)v有路徑相通的頂點(diǎn)都被訪問過為止。體現(xiàn)先進(jìn)先出的特點(diǎn)，用隊列實現(xiàn)。

以鄰接表為存儲結(jié)構(gòu)，用廣度優(yōu)先搜索遍歷圖時，需要使用一個隊列，以類似于按層次遍歷二叉樹遍歷圖。對應(yīng)的算法如下（其中，v是初始頂點(diǎn)編號）：8.3.3廣度優(yōu)先搜索遍歷廣度優(yōu)先搜索遍歷的過程是：體現(xiàn)先進(jìn)先出的特點(diǎn)，用隊列實現(xiàn)。voidBFS(ALGraph*G，intv){ArcNode*p;intw，i;intqueue[MAXV]，front=0，rear=0; //定義循環(huán)隊列

intvisited[MAXV];//定義存放節(jié)點(diǎn)的訪問標(biāo)志的數(shù)組

for(i=0;i<G->n;i++)visited[i]=0;//訪問標(biāo)志數(shù)組初始化

printf("%2d"，v); //輸出被訪問頂點(diǎn)的編號

visited[v]=1; //置已訪問標(biāo)記

rear=(rear+1)%MAXV;queue[rear]=v; //v進(jìn)隊思考題：為什么visited數(shù)組不需要設(shè)置為全局變量？voidBFS(ALGraph*G，intv)思考 while(front!=rear) //若隊列不空時循環(huán)

{front=(front+1)%MAXV; w=queue[front]; //出隊并賦給w p=G->adjlist[w].firstarc; //找w的第一個的鄰接點(diǎn)

while(p!=NULL) { if(visited[p->adjvex]==0) {printf(“%2d”，p->adjvex);//訪問之

visited[p->adjvex]=1; rear=(rear+1)%MAXV; //該頂點(diǎn)進(jìn)隊

queue[rear]=p->adjvex;}p=p->nextarc; //找下一個鄰接頂點(diǎn)

} } printf("\n");} while(front!=rear) /例如，以上圖的鄰接表為例調(diào)用BFS()函數(shù)，假設(shè)初始頂點(diǎn)編號v=2，給出調(diào)用BFS()的執(zhí)行過程。例如，以上圖的鄰接表為例調(diào)用BFS()函數(shù)，假設(shè)初始頂點(diǎn)編號BFS序列：21340BFS序列：21340思考題：用隊列求解迷宮問題，有BFS算法有什么關(guān)聯(lián)？思考題：8.3.4非連通圖的遍歷

對于無向圖來說，若無向圖是連通圖，則一次遍歷能夠訪問到圖中的所有頂點(diǎn)；但若無向圖是非連通圖，則只能訪問到初始點(diǎn)所在連通分量中的所有頂點(diǎn)，其他連通分量中的頂點(diǎn)是不可能訪問到的。為此需要從其他每個連通分量中選擇初始點(diǎn)，分別進(jìn)行遍歷，才能夠訪問到圖中的所有頂點(diǎn)；8.3.4非連通圖的遍歷

對于有向圖來說，若從初始點(diǎn)到圖中的每個頂點(diǎn)都有路徑，則能夠訪問到圖中的所有頂點(diǎn)；否則不能訪問到所有頂點(diǎn)，為此同樣需要再選初始點(diǎn)，繼續(xù)進(jìn)行遍歷，直到圖中的所有頂點(diǎn)都被訪問過為止。對于有向圖來說，若從初始點(diǎn)到圖中的每個頂點(diǎn)都有采用深度優(yōu)先搜索遍歷非連通無向圖的算法如下：DFS1(ALGraph*G){

inti;for(i=0;i<G->n;i++)//遍歷所有未訪問過的頂點(diǎn)

if(visited[i]==0)

DFS(G，i);}采用深度優(yōu)先搜索遍歷非連通無向圖的算法如下：采用廣度優(yōu)先搜索遍歷非連通無向圖的算法如下：BFS1(ALGraph*G){inti;for(i=0;i<G->n;i++)//遍歷所有未訪問過的頂點(diǎn)

if(visited[i]==0)

BFS(G，i);}采用廣度優(yōu)先搜索遍歷非連通無向圖的算法如下：

例8.3

假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，判斷無向圖G是否連通。若連通則返回1；否則返回0。

解：采用遍歷方式判斷無向圖G是否連通。這里用深度優(yōu)先遍歷方法，先給visited[]數(shù)組（為全局變量）置初值0，然后從0頂點(diǎn)開始遍歷該圖。在一次遍歷之后，若所有頂點(diǎn)i的visited[i]均為1，則該圖是連通的；否則不連通。對應(yīng)的算法如下：例8.3假設(shè)圖G采用鄰接表存儲，設(shè)計一個算boolConnect(ALGraph*G)//判斷無向圖G的連通性{inti;boolflag=true;for(i=0;i<G->n;i++) //visited數(shù)組置初值

visited[i]=0;DFS(G,0);//調(diào)用前面的中DSF算法,從頂點(diǎn)0開始深度優(yōu)先遍歷

for(i=0;i<G->n;i++) if(visited[i]==0) {flag=false; break; }returnflag;}boolConnect(ALGraph*G)//判斷無例8.4

假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，判斷頂點(diǎn)u到v是否有簡單路徑。

基于深度優(yōu)先遍歷算法的應(yīng)用

解：從頂點(diǎn)u開始進(jìn)行深度優(yōu)先搜索，當(dāng)搜索到頂點(diǎn)v時表明從頂點(diǎn)u到頂點(diǎn)v有路徑，即：uu1u2v…用形參has（調(diào)用時其初值置為false）表示頂點(diǎn)uv是否有路徑。8.3.5圖遍歷的應(yīng)用例8.4假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，判斷頂intvisited[MAXV]={0}; //全局變量voidisPath(ALGraph*G,intu,intv,bool&flag)//flag表示uv是否有路徑，初始時flag=false{

intw;ArcNode*p;visited[u]=1;p=G->adjlist[u].firstarc;//p指向u的第一條邊

while(p!=NULL){w=p->adjvex; //w為u的鄰接頂點(diǎn)

if(w==v){flag=true;return;}

elseif(visited[w]==0)//若頂點(diǎn)未標(biāo)記訪問，則遞歸訪問之

isPath(G,w,v,has);

//從頂點(diǎn)w出發(fā)繼續(xù)查找

p=p->nextarc //找u的下一個鄰接頂點(diǎn)

}}intvisited[MAXV]={0}; //全局變量

例8.5假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法輸出圖G中從頂點(diǎn)u到v的一條簡單路徑（假設(shè)圖G中從頂點(diǎn)u到v至少有一條簡單路徑）。解：采用深度優(yōu)先遍歷的方法。為此在深度優(yōu)先遍歷算法的基礎(chǔ)上增加v、path和d三個形參，其中path存放頂點(diǎn)u到v的路徑，d表示path中的路徑長度，其初值為-1。當(dāng)從頂點(diǎn)u遍歷到頂點(diǎn)v后，輸出path并返回。例8.5假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法輸出圖G中voidFindaPath(AGraph*G,intu,intv,intpath[],intd){

//d表示path中的路徑長度，初始為-1intw,i;ArcNode*p;visited[u]=1;d++;path[d]=u; //路徑長度d增1，頂點(diǎn)u加入到路徑中

if(u==v) //找到一條路徑后輸出并返回

{printf("一條簡單路徑為:"); for(i=0;i<=d;i++)printf("%d",path[i); printf("\n"); return;//找到一條路徑后返回

}p=G->adjlist[u].firstarc;//p指向頂點(diǎn)u的第一個相鄰點(diǎn)

while(p!=NULL){w=p->adjvex; //相鄰點(diǎn)的編號為w if(visited[w]==0) FindaPath(G,w,v,path,d); p=p->nextarc;//p指向頂點(diǎn)u的下一個相鄰點(diǎn)

}}voidFindaPath(AGraph*G,intu例8.6

假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，輸出圖G中從頂點(diǎn)u到v的所有簡單路徑。

解：所謂簡單路徑是指路徑上的頂點(diǎn)不重復(fù)。利用回溯的深度優(yōu)先搜索方法。從頂點(diǎn)u開始進(jìn)行深度優(yōu)先搜索，在搜索過程中，需要把當(dāng)前的搜索線路記錄下來。為此設(shè)立一個數(shù)組path保存走過的路徑，用d記錄走過的路徑長度。若當(dāng)前掃描到的頂點(diǎn)u等于v時，表示找到了一條路徑，則輸出路徑path。對應(yīng)的算法如下：uu1v…path,dpath,d例8.6假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，輸出圖voidPathAll(ALGraph*G,intu,intv,intpath[],intd)//d是到當(dāng)前為止已走過的路徑長度，調(diào)用時初值為-1{

intw，i;ArcNode*p;visited[u]=1;d++; //路徑長度增1

path[d]=u; //將當(dāng)前頂點(diǎn)添加到路徑中

if(u==v&&d>1) //輸出一條路徑

{printf("");for(i=0;i<=d;i++)printf("%d"，path[i]); printf("\n");}p=G->adjlist[u].firstarc;

//p指向u的第一條邊

while(p!=NULL){w=p->adjvex;

//w為u的鄰接頂點(diǎn)

if(visited[w]==0)

//若頂點(diǎn)未標(biāo)記訪問，則遞歸訪問之

PathAll(G,w,v,path,d);p=p->nextarc

//找u的下一個鄰接頂點(diǎn)

}visited[u]=0;

//恢復(fù)環(huán)境}為什么？？？voidPathAll(ALGraph*G,intu,voidmain(){intpath[MAXV],u=1,v=4,i,j;MGraphg;ALGraph*G;g.n=5;g.e=6;intA[MAXV][MAXV]={{0,1,0,1,0}，{1,0,1,0,0}，

{0,1,0,1,1}，{1,0,1,0,1}，{0,0,1,1,0}};for(i=0;i<g.n;i++) //建立圖的鄰接矩陣

for(j=0;j<g.n;j++) g.edges[i][j]=A[i][j];MatToList(g，G);for(i=0;i<g.n;i++)visited[i]=0;printf("圖G:\n");DispAdj(G); //輸出鄰接表

printf("從%d到%d的所有路徑:\n"，u，v);

PathAll(G，u，v，path，-1);printf("\n");}voidmain()圖G:0:131:022:1343:0244:23從1到4的所有路徑:124123410341032413240程序執(zhí)行結(jié)果如下：圖G:13240程序執(zhí)行結(jié)果如下：

例8.7

假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，輸出圖G中從頂點(diǎn)u到v的長度為l的所有簡單路徑。

解：所謂簡單路徑是指路徑上的頂點(diǎn)不重復(fù)。利用回溯的深度優(yōu)先搜索方法。從頂點(diǎn)u開始，進(jìn)行深度優(yōu)先搜索，在搜索過程中，需要把當(dāng)前的搜索線路記錄下來。為此設(shè)立一個數(shù)組path保存走過的路徑，用d記錄走過的路徑長度。若當(dāng)前掃描到的頂點(diǎn)u等于v且路徑長度為l時，表示找到了一條路徑，則輸出路徑path。對應(yīng)的算法如下：例8.7假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，輸出另一種叫做廣度優(yōu)先搜索法課件voidPathAll(ALGraph*G,intu,intv,intl,intpath[],intd)//d是到當(dāng)前為止已走過的路徑長度，調(diào)用時初值為-1{

intw，i;ArcNode*p;visited[u]=1;d++; //路徑長度增1

path[d]=u; //將當(dāng)前頂點(diǎn)添加到路徑中

if(u==v&&d==l) //輸出一條路徑

{printf("");for(i=0;i<=d;i++)printf("%d"，path[i]); printf("\n");}p=G->adjlist[u].firstarc;

//p指向u的第一條弧的弧頭節(jié)點(diǎn)

while(p!=NULL){w=p->adjvex;

//w為u的鄰接頂點(diǎn)

if(visited[w]==0)

//若頂點(diǎn)未標(biāo)記訪問，則遞歸訪問之

PathAll(G,w,v,l,path,d);p=p->nextarc

//找u的下一個鄰接頂點(diǎn)

}visited[u]=0;

//恢復(fù)環(huán)境}為什么？？？voidPathAll(ALGraph*G,intu,voidmain(){intpath[MAXV],u=1,v=4,d=3,i,j;MGraphg;ALGraph*G;g.n=5;g.e=6;intA[MAXV][MAXV]={{0,1,0,1,0}，{1,0,1,0,0}，

{0,1,0,1,1}，{1,0,1,0,1}，{0,0,1,1,0}}; for(i=0;i<g.n;i++) //建立圖的鄰接矩陣

for(j=0;j<g.n;j++) g.edges[i][j]=A[i][j];MatToList(g，G);for(i=0;i<g.n;i++)visited[i]=0;printf("圖G:\n");DispAdj(G); //輸出鄰接表

printf("從%d到%d的所有長度為%d路徑:\n"，u，v，d);

PathAll(G，u，v，d，path，-1);printf("\n");}voidmain()圖G:0:131:022:1343:0244:23從1到4的所有長度為3路徑:1034123413240程序執(zhí)行結(jié)果如下：圖G:13240程序執(zhí)行結(jié)果如下：基本DFS的過程（從頂點(diǎn)u出發(fā)）：DFS(G,u)DFS(G,u1)DFS(G,u2)…DFS的過程（從頂點(diǎn)u出發(fā)到頂點(diǎn)v）：DFS(G,u,v)DFS(G,u1,v)DFS(G,u2,v)…DFS(G,v,v)總結(jié)基本DFS的過程（從頂點(diǎn)u出發(fā)）：DFS(G,u)DFS(G找從頂點(diǎn)u出發(fā)到頂點(diǎn)v的路徑過程：DFS(G,u,v,path,d)u加入path,d++DFS(G,u1,v,path,d)u1加入path,d++DFS(G,u2,v,path,d)……ui加入path,d++DFS(G,v,v,path,d)輸出path找從頂點(diǎn)u出發(fā)到頂點(diǎn)v的路徑過程：DFS(G,u,v,pat找從頂點(diǎn)u出發(fā)到頂點(diǎn)v的長度為l的路徑過程：DFS(G,u,v,l,path,d)u加入path,d++DFS(G,u1,v,l,path,d)u1加入path,d++DFS(G,u2,v,l,path,d)……ui加入path,d++DFS(G,v,v,l,path,d)輸出pathd=l找從頂點(diǎn)u出發(fā)到頂點(diǎn)v的長度為l的路徑過程：DFS(G,u,

例8.8

假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，求圖中通過某頂點(diǎn)k的所有簡單回路（若存在）。并輸出如下圖所示的有向圖的鄰接表和通過頂點(diǎn)0的所有回路。01423例8.8假設(shè)圖G采用鄰接表存儲，設(shè)計一個算法，求intvisited[MAXV]； //全局變量voidDFSPath(ALGraph*G,intu,intv,intpath[],intd)//d是到當(dāng)前為止已走過的路徑長度，調(diào)用時初值為-1{intw，i;ArcNode*p;visited[u]=1;d++;path[d]=u;p=G->adjlist[u].firstarc; //p指向頂點(diǎn)u的第一條邊

while(p!=NULL){w=p->adjvex; //w為頂點(diǎn)u的相鄰點(diǎn)

if(w==v&&d>0) //找到一個回路，輸出之

{printf(""); for(i=0;i<=d;i++) printf("%d"，path[i]); printf("%d\n"，v);}if(visited[w]==0) //w未訪問，則遞歸訪問之

DFSPath(G,w,v,path,d);p=p->nextarc; //找u的下一個鄰接頂點(diǎn)

}visited[u]=0; //恢復(fù)環(huán)境：使該頂點(diǎn)可重新使用}intvisited[MAXV]； //全局變量voidFindCyclePath(ALGraph*G，intk)//輸出經(jīng)過頂點(diǎn)k的所有回路{intpath[MAXV];printf("經(jīng)過頂點(diǎn)%d的所有回路\n"，k);DFSPath(G，k，k，path，-1);}voidFindCyclePath(ALGraph*G，用圖搜索方法求解迷宮問題鄰接表如下：∧(0,0)……

(1,1)(1,2)

(2,1)∧

(1,2)(1,1)

(1,3)∧……∧(5,5)用圖搜索方法求解迷宮問題鄰接表如下：∧(0,0)……(//以下定義鄰接表類型typedefstructANode //邊的節(jié)點(diǎn)結(jié)構(gòu)類型{inti,j; //該邊的終點(diǎn)位置(i,j)structANode*nextarc; //指向下一條邊的指針}ArcNode;typedefstructVnode //鄰接表頭節(jié)點(diǎn)的類型{ArcNode*firstarc; //指向第一條邊}VNode;typedefstruct{VNodeadjlist[M+2][N+2]; //鄰接表頭節(jié)點(diǎn)數(shù)組}ALGraph; //圖的鄰接表類型typedefstruct{inti; //當(dāng)前方塊的行號

intj; //當(dāng)前方塊的列號}Box;typedefstruct{Boxdata[MaxSize];intlength; //路徑長度}PathType; //定義路徑類型intvisited[M+2][N+2]={0};intcount=0; //總的路徑數(shù)//以下定義鄰接表類型voidCreateList(ALGraph*&G,intmg[][N+2])//建立迷宮數(shù)組對應(yīng)的鄰接表G{inti,j,i1,j1,di;ArcNode*p;G=(ALGraph*)malloc(sizeof(ALGraph));for(i=0;i<M+2;i++) //給鄰接表中所有頭節(jié)點(diǎn)的指針域置初值

for(j=0;j<N+2;j++) G->adjlist[i][j].firstarc=NULL;for(i=1;i<=M;i++) //檢查mg中每個元素

for(j=1;j<=N;j++) if(mg[i][j]==0) {di=0; while(di<4) //找(i,j)方塊的四周可走方塊

{switch(di) { case0:i1=i-1;j1=j;break; case1:i1=i;j1=j+1;break; case2:i1=i+1;j1=j;break; case3:i1=i,j1=j-1;break; }voidCreateList(ALGraph*&G,in if(mg[i1][j1]==0) //(i1,j1)為可走方塊

{p=(ArcNode*)malloc(sizeof(ArcNode)); //創(chuàng)建一個節(jié)點(diǎn)*p p->i=i1;p->j=j1; p