第二十一講圖的遍歷

第七章圖濱州學(xué)院計(jì)算機(jī)科學(xué)技術(shù)系圖的遍歷

從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問一次的過程。

遇到的問題：圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。

為避免重復(fù)訪問，可設(shè)一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔助數(shù)組visited[],它的初始狀態(tài)為0，在圖遍歷過程中，一旦某一個(gè)頂點(diǎn)i被訪問，就修改

visited[i]為1，防止它被多次訪問。

從圖中某個(gè)頂點(diǎn)V0出發(fā)，訪問此頂點(diǎn)，然后選擇一個(gè)與V0鄰接且未被訪問的頂點(diǎn)W為初始頂點(diǎn)，再從W出發(fā)進(jìn)行深度優(yōu)先搜索,

直至圖中所有頂點(diǎn)都被訪問到。一、深度優(yōu)先搜索遍歷連通圖的深度優(yōu)先搜索遍歷深度優(yōu)先搜索DFS(DepthFirstSearch)深度優(yōu)先搜索的示例深度優(yōu)先搜索過程深度優(yōu)先生成樹DFS在訪問圖中某一起始頂點(diǎn)v后，由v出發(fā)，訪問它的任一鄰接頂點(diǎn)w1；再從w1出發(fā)，訪問與w1鄰接但還沒有訪問過的頂點(diǎn)w2；然后再從w2出發(fā)，進(jìn)行類似的訪問，…如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn)u為止。接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有，則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。1.深度優(yōu)先搜索遍歷連通圖的過程類似于樹的先根遍歷；為每個(gè)頂點(diǎn)設(shè)立一個(gè)“訪問標(biāo)志visited[w]”。2.如何判別V的鄰接點(diǎn)是否被訪問？voidDFSTraverse(GraphG,Status(*Visit)(intv)

){//對(duì)圖

G作深度優(yōu)先遍歷

VisitFunc=Visit；for(v=0;v<G.vexnum;++v)visited[v]=false;//訪問標(biāo)志數(shù)組初始化

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

//對(duì)尚未訪問的頂點(diǎn)調(diào)用DFS

if(!visited[v])

DFS(G,v);}Bolean

visited[MAX];Status(*VisitFunc)(intv);voidDFS(GraphG,intv){

//從第v個(gè)頂點(diǎn)出發(fā)，深度優(yōu)先搜索遍歷圖

Gvisited[v]=true;VisitFunc(v);for(w=FirstAdjVex(G,v);w>=0;w=NextAdjVex(G,v,w))

if(!visited[w])DFS(G,w);

//對(duì)v的尚未訪問的鄰接頂點(diǎn)w遞歸調(diào)用DFS}//DFS

首先將圖中每個(gè)頂點(diǎn)的訪問標(biāo)志設(shè)為FALSE,之后搜索圖中每個(gè)頂點(diǎn)，如果未被訪問，則以該頂點(diǎn)為起始點(diǎn)，進(jìn)行深度優(yōu)先搜索遍歷，否則繼續(xù)檢查下一頂點(diǎn)。非連通圖的深度優(yōu)先搜索遍歷abchdeifgFFFFFFFFFTTTTTTTTTachdifebgachifedbg訪問標(biāo)志:訪問次序:例如:012345678voidDFSTraverse(GraphG){//對(duì)圖G作深度優(yōu)先遍歷。for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//訪問標(biāo)志數(shù)組初始化for(v=0;v<G.vexnum;++v)

//對(duì)尚未訪問的頂點(diǎn)調(diào)用DFS

if(!visited[v])DFS(G,v);}算法分析設(shè)圖中有n個(gè)頂點(diǎn)，e條邊。如果用鄰接表表示圖，沿

firstout

鏈可以找到某個(gè)頂點(diǎn)v的所有鄰接頂點(diǎn)w。由于總共有2e個(gè)邊結(jié)點(diǎn)，所以掃描邊的時(shí)間為O(e)。而且對(duì)所有頂點(diǎn)遞歸訪問1次，所以遍歷圖的時(shí)間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個(gè)頂點(diǎn)的鄰接點(diǎn)所需的時(shí)間為O(n2)。二、廣度優(yōu)先搜索遍歷Vw1w8w3w7w6w2w5w4對(duì)連通圖，從起始點(diǎn)V到其余各頂點(diǎn)必定存在路徑。

其中，V->w1,V->w2,V->w8

的路徑長度為1；V->w7,V->w3,V->w5

的路徑長度為2；V->w6,V->w4

的路徑長度為3。w1Vw2w7w6w3w8w5w4

從圖中的某個(gè)頂點(diǎn)V出發(fā)，并在訪問V0之后依次訪問V0的各個(gè)未被訪問的鄰接點(diǎn)，之后按這些頂點(diǎn)被訪問的先后次序依次訪問它們的鄰接點(diǎn)，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問到。

若此時(shí)圖中尚有頂點(diǎn)未被訪問，則另選圖中一個(gè)未曾被訪問的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被訪問到為止。廣度優(yōu)先搜索BFS(BreadthFirstSearch

)廣度優(yōu)先搜索的示例

廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹

使用廣度優(yōu)先搜索在訪問了起始頂點(diǎn)v之后，由v出發(fā)，依次訪問v的各個(gè)未曾被訪問過的鄰接頂點(diǎn)w1,w2,…,wt，然后再順序訪問w1,w2,…,wt的所有還未被訪問過的鄰接頂點(diǎn)。再從這些訪問過的頂點(diǎn)出發(fā)，再訪問它們的所有還未被訪問過的鄰接點(diǎn)，…如此做下去，直到圖中所有頂點(diǎn)都被訪問到為止。

廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先搜索不是一個(gè)遞歸的過程，其算法也不是遞歸的。

為了實(shí)現(xiàn)逐層訪問，算法中使用了一個(gè)隊(duì)列，以記憶正在訪問的這一層和上一層的頂點(diǎn)，以便于向下一層訪問。

與深度優(yōu)先搜索過程一樣，為避免重復(fù)訪問，需要一個(gè)輔助數(shù)組visited[]，給被訪問過的頂點(diǎn)加標(biāo)記。

voidBFSTraverse(GraphG，status(*Visit)(intv){//廣度優(yōu)先搜索遍歷圖G

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

visited[v]=false;//初始化訪問標(biāo)志

InitQueue(Q);

//初始化隊(duì)列Q

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

if(!visited[v])

{//v尚未訪問

}}//BFSTraverse……EnQueue(Q,v);

//v入隊(duì)列while(!QueueEmpty(Q)){

DeQueue(Q,u);

//隊(duì)頭元素出隊(duì)為u并準(zhǔn)備訪問

Visited[u]=true;Visit(u);//訪問u

for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))if(!visited[w]){

EnQueue(Q,w);

//下一個(gè)要訪問的頂點(diǎn)w入隊(duì)列

}//if}//while算法分析如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為d0+d1+…+dn-1=O(e)，其中的di是頂點(diǎn)i的度。如果使用鄰接矩陣，則對(duì)于每一個(gè)被訪問過的頂點(diǎn)，循環(huán)要檢測矩陣中的n個(gè)元素，總的時(shí)間代價(jià)為O(n2