大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第六章：圖-第三節(jié)-圖的遍歷

第三節(jié)圖的遍歷

圖的遍歷：從某個(gè)頂點(diǎn)出發(fā)，沿著某條搜索路徑對(duì)圖中每個(gè)頂點(diǎn)做

且僅做一次訪問(wèn)。圖的遍歷最常用的是深度優(yōu)先搜索遍歷和廣度優(yōu)先

搜索遍歷兩種方法。

一、深度優(yōu)先搜索遍歷

1、深度優(yōu)先搜索遍歷思想：

深度優(yōu)先搜索(DepthFirstSearch,DFS)遍歷類(lèi)似于樹(shù)的前序(先

根)遍歷。假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)都未曾訪問(wèn)過(guò)，則可從圖G中

任選一頂點(diǎn)V為初始出發(fā)點(diǎn)，首先訪問(wèn)出發(fā)點(diǎn)V,并將其標(biāo)記為已訪

問(wèn)過(guò)；然后依次從V出發(fā)搜索V的每個(gè)鄰接點(diǎn)W,若W未曾訪問(wèn)

過(guò)，則以w作為新的出發(fā)點(diǎn)出發(fā)，繼續(xù)進(jìn)行深度優(yōu)先遍歷，直到圖中

所有和V有路徑相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中仍有頂點(diǎn)未被訪

問(wèn)，則另選一個(gè)未曾訪問(wèn)的頂點(diǎn)作為起點(diǎn)，重復(fù)上述過(guò)程，直到圖中

所有頂點(diǎn)都被訪問(wèn)到為止。

從Vo開(kāi)始的深度優(yōu)先搜索序列：V。，V1,V2,V5,V4,V6,V3,

V7,V8o

從V8開(kāi)始的深度優(yōu)先搜索序列：V8,V4,Vo,V1,V2,V5,V3,

V6,V7o

2、以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)的深度優(yōu)先搜索遍歷算法

intvisited[20];

voidDFS(MGraphG,inti,intn)

{〃從頂點(diǎn)Vi出發(fā)，深度優(yōu)先搜索遍歷圖G(鄰接矩陣結(jié)構(gòu))

intj;

printf("V%d^",i);〃假定訪問(wèn)頂點(diǎn)vi以輸

出該頂點(diǎn)的序號(hào)代之

visited[i]=l;〃標(biāo)記vi已訪問(wèn)過(guò)

for(j=0;j<n;j++)〃依次搜索vi的每個(gè)鄰

接點(diǎn)

if(G.arcs[i][j]==l&&!visited[j])

DFS(G,j,n);〃若(Vi,Vj)e(G),且Vj

未被訪問(wèn)過(guò)，則從開(kāi)始遞歸調(diào)用

)

該算法的時(shí)間復(fù)雜度為O(n2)

3、以鄰接表為存儲(chǔ)結(jié)構(gòu)的深度優(yōu)先搜索遍歷算法

intvisited[20];〃全局量數(shù)組，用以標(biāo)記某個(gè)頂點(diǎn)是否被訪問(wèn)過(guò)

voidDFSI(ALGraphG,inti)

{〃從頂點(diǎn)Vi出發(fā)，深度優(yōu)先搜索遍歷圖G(鄰接表結(jié)構(gòu))

EdgeNode*p;intj;

printf("V%d^",i);〃假定訪問(wèn)頂點(diǎn)vi以

輸出該頂點(diǎn)的序號(hào)代之

visited[i]=l;〃標(biāo)記vi已訪問(wèn)過(guò)

p=G[i].link;〃取Vi鄰接表的表頭

指針

while(p!=NuLL)〃依次搜索vi的每個(gè)

鄰接點(diǎn)

{j=p->adjvex;//]為vi的一個(gè)鄰接

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

if(!visited[)])

DFSI(GJ);〃若(vi,vj)GE(G),且

vj未被訪問(wèn)過(guò)，則從開(kāi)始遞歸調(diào)用

p=p->next;〃使P指向vi的下

一個(gè)鄰接點(diǎn)

}//End-while

)

該算法的時(shí)間復(fù)雜度為O(n+e)o

二、廣度優(yōu)先搜索遍歷

1、廣度優(yōu)先搜索遍歷思想

廣度優(yōu)先搜索(BFS)遍歷類(lèi)似于樹(shù)的按層次遍歷。其基本思想是：首

先訪問(wèn)出發(fā)點(diǎn)Vi,接著依次訪問(wèn)Vi的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)Vil,

Vi2，…，Vit,并均標(biāo)記為已訪問(wèn)過(guò),然后再按照Vil,Vi2，…，Vit

的次序，訪問(wèn)每一個(gè)頂點(diǎn)的所有未曾訪問(wèn)過(guò)的頂點(diǎn)并均標(biāo)記為已訪問(wèn)

過(guò)，依次類(lèi)推，直到圖中所有和初始出發(fā)點(diǎn)Vi有路徑相通的頂點(diǎn)都被

訪問(wèn)過(guò)為止。

【例】

從Vo開(kāi)始的廣度優(yōu)先搜索序列：Vo,V1,V3,V4,V2,V6,V8,

V5,V7o

從V8開(kāi)始的廣度優(yōu)先搜索序列：V8,V4,Vo,Vl,V6,V3,V2,

v7,v5o

2、以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)的廣度優(yōu)先搜索遍歷算法

intvisited[20];

voidBFS(MG、phG,inti,intn)

{〃從頂點(diǎn)Vi出發(fā)，廣度優(yōu)先搜索遍歷圖G(鄰接矩陣結(jié)構(gòu))

cirQueueQ;〃定義一個(gè)

隊(duì)歹I」

intk,j;

InitQueue(&Q);〃初始化隊(duì)

printf("v%d->",i)〃假定訪問(wèn)頂

點(diǎn)vi用輸出該頂點(diǎn)的序號(hào)代之

visited[i]=l;〃標(biāo)記Vi已訪

問(wèn)過(guò)

EnQueue(&Q,i);〃將已訪問(wèn)的頂

點(diǎn)序號(hào)i入隊(duì)

while(!QueueEmpty(&Q))〃當(dāng)隊(duì)列非空

時(shí)，循環(huán)處理vi的每個(gè)鄰接點(diǎn)

{k=DeQueue(&Q);〃刪除隊(duì)頭元

素

for(j=0;j<n;j++)〃依次搜索Vk

的每一個(gè)可能的

{if(G.arcs[k][j]==l&&!visited[j])

{printf("V%l,j);〃訪問(wèn)未曾訪問(wèn)

過(guò)的頂點(diǎn)vj

visited[j]=l;〃標(biāo)記Vi已訪問(wèn)

過(guò)

EnQueue(&Q,j);〃頂點(diǎn)序號(hào)j入隊(duì)

}//Endjf

}//End_for

}//End_while

)

該算法的時(shí)間復(fù)雜度為0(n2)

3、以鄰接表為存儲(chǔ)結(jié)構(gòu)的廣度優(yōu)先搜索遍歷算法

VoidBFSI(ALGraphG,inti,intn)

{〃從頂點(diǎn)Vi出發(fā)，廣度優(yōu)先搜索遍歷圖G

CirQueueQ;〃定義一個(gè)隊(duì)列指針

intj,k;

InitQueue(&Q);〃初始化隊(duì)列

EdgeNode*p;

intvisited[20];

printf("v%d-*",i);〃假定訪問(wèn)頂點(diǎn)vi以輸出

該頂點(diǎn)的序號(hào)代之

visited[i]=l;〃標(biāo)記vi已訪問(wèn)過(guò)

EnQueue(&Q,i);〃將已訪問(wèn)的頂點(diǎn)序號(hào)i入

隊(duì)

while(!QueueEmpty(&Q))〃循環(huán)處理vi的每個(gè)鄰

接點(diǎn)

{k=DeQueue(&Q);〃刪除隊(duì)頭元素

p=G[k].link;〃取vk鄰接表的表頭指針

while(p!=NULL)〃依次搜索vk的每一個(gè)可能的

鄰接點(diǎn)

{j=p->adjvex;//Vj為Vk的一個(gè)鄰接點(diǎn)

if(!visited。])〃若vj未被訪問(wèn)過(guò)

{printf("V%d^",j);〃訪問(wèn)未曾訪問(wèn)過(guò)的頂點(diǎn)vj

visited[j]=1;〃標(biāo)記vj已訪問(wèn)過(guò)

EnQueue(&Q,j);/?點(diǎn)序號(hào)j入隊(duì)

}//End-if

p=p->next;〃使p指向Vk鄰接表的下一個(gè)

鄰接點(diǎn)

}//End_while

}//End_while

)

該算法的時(shí)間復(fù)雜度為

O(n+e)o

注意：由于圖G=(V,E)中頂點(diǎn)集合V與邊的集合E中元素的排

列是任意的，在采用鄰接表存儲(chǔ)以后，如果存放頂點(diǎn)結(jié)點(diǎn)的先后順序

不同，或者邊結(jié)點(diǎn)的鏈接次序不同，在按照某種方式遍歷圖時(shí)，將會(huì)

影響到頂點(diǎn)被訪問(wèn)的先后JII頁(yè)序,即經(jīng)過(guò)遍歷得到的遍歷序列有可能不

同。即使存儲(chǔ)結(jié)構(gòu)確定，如果指定的出發(fā)頂點(diǎn)不同，遍歷結(jié)果也會(huì)不

同。當(dāng)然，對(duì)于某種已經(jīng)確定的存儲(chǔ)結(jié)構(gòu)與指定的出發(fā)頂點(diǎn)，按照某

種遍歷方法得到的遍歷結(jié)果應(yīng)該是唯一的。

【真題選解】

(例題?單選題)在下圖中，從頂點(diǎn)1

出發(fā)進(jìn)行深度優(yōu)先遍歷可得到的序列是

0

A.1234567

B.1426375

C.1425367

D.1246537

隱藏答案

【答案】B

【解析】從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先遍歷：先訪問(wèn)1,然后可以訪

問(wèn)2,接下來(lái)不可能訪問(wèn)3,（所以選項(xiàng)A錯(cuò)誤），可以訪問(wèn)4,接下

來(lái)可以5,不可能訪問(wèn)6,（所以選項(xiàng)D錯(cuò)誤）。先訪問(wèn)1,然后可

以訪問(wèn)4,再訪問(wèn)2,接下來(lái)可以6,不可能訪問(wèn)5,（所以選項(xiàng)C錯(cuò)

誤）。選項(xiàng)B:1426375是從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先遍歷可得

到的序列。

012345

（例題?單選題）已知含6個(gè)頂點(diǎn)（VO,VI,。國(guó)。011000

1工1101100

）的無(wú)向圖的鄰接矩陣如圖所11QQ01

V2,V3,V4,V5"13010000

4*4000QQ1

示，則從頂點(diǎn)V0出發(fā)進(jìn)行深度優(yōu)先遍歷可能得5國(guó)5001QI0

到的頂點(diǎn)訪問(wèn)序列為（）

A.（VO,VI,V2,V5,V4,V3）

B.（