第二十一講圖的遍歷

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

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

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

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

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

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

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

){//對圖

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

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

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

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

if(!visited[v])

DFS(G,v);}Bolean

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

//從第v個頂點出發(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);

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

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

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

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

firstout

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

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

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

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

的路徑長度為3。w1Vw2w7w6w3w8w5w4

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

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

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

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

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

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

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

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

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

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

visited[v]=false;//初始化訪問標志

InitQueue(Q);

//初始化隊列Q

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

if(!visited[v])

{//v尚未訪問

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

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

DeQueue(Q,u);

//隊頭元素出隊為u并準備訪問

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

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

EnQueue(Q,w);

//下一個要訪問的頂點w入隊列

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