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

第三節(jié)圖的遍歷圖的遍歷：從某個(gè)頂點(diǎn)出發(fā)，沿著某條搜索路徑對圖中每個(gè)頂點(diǎn)做且僅做一次訪問。圖的遍歷最常用的是深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷兩種方法。一、深度優(yōu)先搜索遍歷1、深度優(yōu)先搜索遍歷思想：深度優(yōu)先搜索(DepthFirstSearch，DFS)遍歷類似于樹的前序(先根)遍歷。假設(shè)初始狀態(tài)是圖中所有頂點(diǎn)都未曾訪問過，則可從圖G中任選一頂點(diǎn)V為初始出發(fā)點(diǎn)，首先訪問出發(fā)點(diǎn)V，并將其標(biāo)記為已訪問過；然后依次從V出發(fā)搜索V的每個(gè)鄰接點(diǎn)W，若W未曾訪問過，則以w作為新的出發(fā)點(diǎn)出發(fā)，繼續(xù)進(jìn)行深度優(yōu)先遍歷，直到圖中所有和V有路徑相通的頂點(diǎn)都被訪問到；若此時(shí)圖中仍有頂點(diǎn)未被訪問，則另選一個(gè)未曾訪問的頂點(diǎn)作為起點(diǎn)，重復(fù)上述過程，直到圖中所有頂點(diǎn)都被訪問到為止。【例】從V0開始的深度優(yōu)先搜索序列：V0，V1，V2，V5，V4，V6，V3，V7，V8。從V8開始的深度優(yōu)先搜索序列：V8，V4，V0，V1，V2，V5，V3，V6，V7。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)；//假定訪問頂點(diǎn)vi以輸出該頂點(diǎn)的序號(hào)代之visited[i]=1；//標(biāo)記vi已訪問過for(j=0；j<n；j++)//依次搜索vi的每個(gè)鄰接點(diǎn)if(G.arcs[i][j]==1&&!visited[j])DFS(G，j，n)；//若(Vi，Vj)∈(G)，且Vj未被訪問過，則從開始遞歸調(diào)用｝該算法的時(shí)間復(fù)雜度為O(n2)3、以鄰接表為存儲(chǔ)結(jié)構(gòu)的深度優(yōu)先搜索遍歷算法intvisited[20]；//全局量數(shù)組，用以標(biāo)記某個(gè)頂點(diǎn)是否被訪問過voidDFSl(ALGraphG，inti){//從頂點(diǎn)Vi出發(fā)，深度優(yōu)先搜索遍歷圖G(鄰接表結(jié)構(gòu))EdgeNode*p；intj；printf("V%d→"，i)；//假定訪問頂點(diǎn)vi以輸出該頂點(diǎn)的序號(hào)代之visited[i]=1；//標(biāo)記vi已訪問過p=G[i].1ink；//取Vi鄰接表的表頭指針while(p!=NuLL)//依次搜索vi的每個(gè)鄰接點(diǎn){j=p->adjvex；//j為vi的一個(gè)鄰接點(diǎn)序號(hào)if(!visited[j])DFSl(G，j)；//若(vi，vj)∈E(G)，且vj未被訪問過，則從開始遞歸調(diào)用p=p->next；//使p指向vi的下一個(gè)鄰接點(diǎn)｝//End-while｝該算法的時(shí)間復(fù)雜度為O(n+e)。二、廣度優(yōu)先搜索遍歷1、廣度優(yōu)先搜索遍歷思想廣度優(yōu)先搜索(BFS)遍歷類似于樹的按層次遍歷。其基本思想是：首先訪問出發(fā)點(diǎn)Vi，接著依次訪問Vi的所有未被訪問過的鄰接點(diǎn)Vi1，Vi2，…，Vit，并均標(biāo)記為已訪問過，然后再按照Vi1，Vi2，…，Vit的次序，訪問每一個(gè)頂點(diǎn)的所有未曾訪問過的頂點(diǎn)并均標(biāo)記為已訪問過，依次類推，直到圖中所有和初始出發(fā)點(diǎn)Vi有路徑相通的頂點(diǎn)都被訪問過為止。【例】從V0開始的廣度優(yōu)先搜索序列：V0，V1，V3，V4，V2，V6，V8，V5，V7。從V8開始的廣度優(yōu)先搜索序列：V8，V4，V0，V1，V6，V3，V2，V7，V5。2、以鄰接矩陣為存儲(chǔ)結(jié)構(gòu)的廣度優(yōu)先搜索遍歷算法intvisited[20]；voidBFS(MGraphG，inti，intn){//從頂點(diǎn)Vi出發(fā)，廣度優(yōu)先搜索遍歷圖G(鄰接矩陣結(jié)構(gòu))cirQueueQ；//定義一個(gè)隊(duì)列intk，j；InitQueue(&Q)；//初始化隊(duì)列printf("v%d→"，i)//假定訪問頂點(diǎn)vi用輸出該頂點(diǎn)的序號(hào)代之visited[i]=1；//標(biāo)記Vi已訪問過EnQueue(&Q，i)；//將已訪問的頂點(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]==1&&!visited[j]){printf("V%d→"，j)；//訪問未曾訪問過的頂點(diǎn)vjvisited[j]=1；//標(biāo)記Vi已訪問過EnQueue(&Q，j)；//頂點(diǎn)序號(hào)j入隊(duì)}//End_if}//End_for}//End_while}該算法的時(shí)間復(fù)雜度為O(n2)3、以鄰接表為存儲(chǔ)結(jié)構(gòu)的廣度優(yōu)先搜索遍歷算法VoidBFSl(ALGraphG，inti，intn){//從頂點(diǎn)Vi出發(fā)，廣度優(yōu)先搜索遍歷圖GCirQueueQ；//定義一個(gè)隊(duì)列指針intj，k；InitQueue(&Q)；//初始化隊(duì)列EdgeNode*p；intvisited[20]；printf("v%d→"，i);//假定訪問頂點(diǎn)vi以輸出該頂點(diǎn)的序號(hào)代之visited[i]=1;//標(biāo)記vi已訪問過EnQueue(&Q，i);//將已訪問的頂點(diǎn)序號(hào)i入隊(duì)while(!QueueEmpty(&Q))//循環(huán)處理vi的每個(gè)鄰接點(diǎn){k=DeQueue(&Q)；//刪除隊(duì)頭元素p=G[k].1ink;//取vk鄰接表的表頭指針while(p!=NULL)//依次搜索vk的每一個(gè)可能的鄰接點(diǎn){j=p->adjvex；//Vj為Vk的一個(gè)鄰接點(diǎn)if(!visited[j])//若vj未被訪問過{printf("V%d→"，j)；//訪問未曾訪問過的頂點(diǎn)vjvisited[j]=1;//標(biāo)記vj已訪問過EnQueue(&Q，j);//頂點(diǎn)序號(hào)j入隊(duì)}//End-ifp=p->next；//使p指向Vk鄰接表的下一個(gè)鄰接點(diǎn)}//End_while}//End_while}該算法的時(shí)間復(fù)雜度為O(n+e)。注意：由于圖G=（V，E）中頂點(diǎn)集合V與邊的集合E中元素的排列是任意的，在采用鄰接表存儲(chǔ)以后，如果存放頂點(diǎn)結(jié)點(diǎn)的先后順序不同，或者邊結(jié)點(diǎn)的鏈接次序不同，在按照某種方式遍歷圖時(shí)，將會(huì)影響到頂點(diǎn)被訪問的先后順序，即經(jīng)過遍歷得到的遍歷序列有可能不同。即使存儲(chǔ)結(jié)構(gòu)確定，如果指定的出發(fā)頂點(diǎn)不同，遍歷結(jié)果也會(huì)不同。當(dāng)然，對于某種已經(jīng)確定的存儲(chǔ)結(jié)構(gòu)與指定的出發(fā)頂點(diǎn)，按照某種遍歷方法得到的遍歷結(jié)果應(yīng)該是唯一的。【真題選解】（例題?單選題）在下圖中，從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先遍歷可得到的序列是()A．1234567B．1426375C．1425367D．1246537隱藏答案【答案】B【解析】從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先遍歷：先訪問1，然后可以訪問2，接下來不可能訪問3，（所以選項(xiàng)A錯(cuò)誤），可以訪問4，接下來可以5，不可能訪問6，（所以選項(xiàng)D錯(cuò)誤）。先訪問1，然后可以訪問4，再訪問2，接下來可以6，不可能訪問5，（所以選項(xiàng)C錯(cuò)誤）。選項(xiàng)B：1426375是從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先遍歷可得到的序列。（例題?單選題）已知含6個(gè)頂點(diǎn)(V0，V1，V2，V3，V4，V5)的無向圖的鄰接矩陣如圖所示，則從頂點(diǎn)V0出發(fā)進(jìn)行深度優(yōu)先遍歷可能得到的頂點(diǎn)訪問序列為()A．(V0，V1，V2，V5，V4，V3)B．(V0，V1，V2，V3，V4，V5)C．(V0，V1，V5，V2，V3，V4)D．(V0，V1，V4，V5，V2，V3)隱藏答案【答案】A【解析】根據(jù)