圖的遍歷概念1、 圖的遍歷和樹的遍歷類似，圖的遍歷也是從某個(gè)頂點(diǎn)出發(fā)，沿著某條搜索路徑對圖中每個(gè)頂點(diǎn)各做一次且僅做一次訪問。它是許多圖的算法的基礎(chǔ)。深度優(yōu)先遍歷和廣度優(yōu)先遍歷是最為重要的兩種遍歷圖的方法。它們對無向圖和有向圖均適用。注意：以下假定遍歷過程中訪問頂點(diǎn)的操作是簡單地輸出頂點(diǎn)。2、 布爾向量visited[0..n-1]的設(shè)置圖中任一頂點(diǎn)都可能和其它頂點(diǎn)相鄰接。在訪問了某頂點(diǎn)之后，又可能順著某條回路又回到了該頂點(diǎn)。為了避免重復(fù)訪問同一個(gè)頂點(diǎn)，必須記住每個(gè)已訪問的頂點(diǎn)。為此，可設(shè)一布爾向量visited[0..n-1]，其初值為假，一旦訪問了頂點(diǎn)Vi之后，便將visited[i]置為真。深度優(yōu)先遍歷（Depth-FirstTraversal）圖的深度優(yōu)先遍歷的遞歸定義假設(shè)給定圖G的初態(tài)是所有頂點(diǎn)均未曾訪問過。在G中任選一頂點(diǎn)v為初始出發(fā)點(diǎn)（源點(diǎn)），則深度優(yōu)先遍歷可定義如下：首先訪問出發(fā)點(diǎn)v，并將其標(biāo)記為已訪問過；然后依次從v出發(fā)搜索v的每個(gè)鄰接點(diǎn)嘰若可未曾訪問過，則以w為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先遍歷，直至圖中所有和源點(diǎn)v有路徑相通的頂點(diǎn)（亦稱為從源點(diǎn)可達(dá)的頂點(diǎn)）均已被訪問為止。若此時(shí)圖中仍有未訪問的頂點(diǎn)，則另選一個(gè)尚未訪問的頂點(diǎn)作為新的源點(diǎn)重復(fù)上述過程，直至圖中所有頂點(diǎn)均已被訪問為止。圖的深度優(yōu)先遍歷類似于樹的前序遍歷。采用的搜索方法的特點(diǎn)是盡可能先對縱深方向進(jìn)行搜索。這種搜索方法稱為深度優(yōu)先搜索（Depth-FirstSearch）0相應(yīng)地，用此方法遍歷圖就很自然地稱之為圖的深度優(yōu)先遍歷。2、 深度優(yōu)先搜索的過程設(shè)x是當(dāng)前被訪問頂點(diǎn)，在對x做過訪問標(biāo)記后，選擇一條從x出發(fā)的未檢測過的邊（x，y）。若發(fā)現(xiàn)頂點(diǎn)y已訪問過，則重新選擇另一條Mx出發(fā)的未檢測過的邊，否則沿邊（x，y）到達(dá)未曾訪問過的y，對y訪問并將其標(biāo)記為已訪問過；然后從y開始搜索，直到搜索完從y出發(fā)的所有路徑，即訪問完所有從y出發(fā)可達(dá)的頂點(diǎn)之后，才回溯到頂點(diǎn)x，并且再選擇一條從x出發(fā)的未檢測過的邊。上述過程直至龐出發(fā)的所有邊都已檢測過為止。此時(shí)，若x不是源點(diǎn)，則回溯到在x之前被訪問過的頂點(diǎn)；否則圖中所有和源點(diǎn)有路徑相通的頂點(diǎn)（即從源點(diǎn)可達(dá)的所有頂點(diǎn)）都已被訪問過，若圖G是連通圖，則遍歷過程結(jié)束，否則繼續(xù)選擇一個(gè)尚未被訪問的頂點(diǎn)作為新源點(diǎn)，進(jìn)行新的搜索過程。3、深度優(yōu)先遍歷的遞歸算法（1）深度優(yōu)先遍歷算法typedefenum{FALSE，TRUE}Boolean；//FALSE為0，TRUE為1Booleanvisited[MaxVertexNum]；〃訪問標(biāo)志向量是全局量voidDFSTraverse（ALGraph*G）{〃深度優(yōu)先遍歷以鄰接表表示的圖G，而以鄰接矩陣表示G時(shí)，算法完全與此相同inti；for(i=0;i<G->n;i++)visited[i]=FALSE；〃標(biāo)志向量初始化for(i=0;i<G->n；i++)if(!visited[i])//vi未訪問過DFS(G,i)；〃以vi為源點(diǎn)開始DFS搜索}//DFSTraverse鄰接表表示的深度優(yōu)先搜索算法voidDFS(ALGraph*G，inti){〃以vi為出發(fā)點(diǎn)對鄰接表表示的圖G進(jìn)行深度優(yōu)先搜索EdgeNode*p；printf("visitvertex：%c”,G->adjlist[i].vertex)；〃訪問頂點(diǎn)vivisited[i]=TRUE；〃標(biāo)記vi已訪問p=G->adjlist[i].firstedge；〃取vi邊表的頭指針while(p){//依次搜索vi的鄰接點(diǎn)vj,這里j=p->adjvexif(!visited[p->adjvex])//若vi尚未被訪問DFS(G,p->adjvex);//則以Vj為出發(fā)點(diǎn)向縱深搜索p=p->next；〃找vi的下一鄰接點(diǎn)}}//DFS鄰接矩陣表示的深度優(yōu)先搜索算法voidDFSM(MGraph*G,inti){〃以vi為出發(fā)點(diǎn)對鄰接矩陣表示的圖G進(jìn)行DFS搜索，設(shè)鄰接矩陣是0,l矩陣intj；printf("visitvertex：%c",G->vexs[i])；〃訪問頂點(diǎn)vivisited[i]=TRUE；for(j=0；j<G->n；j++)//依次搜索vi的鄰接點(diǎn)if(G->edges[i][j]==1&&!visited[j])DFSM(G,j)//(vi,vj)EE，且vj未訪問過，故vj為新出發(fā)點(diǎn)}//DFSM注意：遍歷操作不會修改圖G的內(nèi)容，故上述算法中可將G定義為ALGraph或MGraph類型的參數(shù)，而不一定要定義為ALGraph和MGraph的指針類型。但基于效率上的考慮，選擇指針類型的參數(shù)為宜。4、深度優(yōu)先遍歷序列對圖進(jìn)行深度優(yōu)先遍歷時(shí)，按訪問頂點(diǎn)的先后次序得到的頂點(diǎn)序列稱為該圖的深度優(yōu)先遍歷序列，或簡稱為DFS序列。一個(gè)圖的DFS序列不一定惟一當(dāng)從某頂點(diǎn)x出發(fā)搜索時(shí)，若x的鄰接點(diǎn)有多個(gè)尚未訪問過，則我們可任選一個(gè)訪問之。源點(diǎn)和存儲結(jié)構(gòu)的內(nèi)容均已確定的圖的DFS序列惟一①鄰接矩陣表示的圖確定源點(diǎn)后，DFS序列惟一DFSM算法中，當(dāng)從vi出發(fā)搜索時(shí)，是在鄰接矩陣的第i行上從左至右選擇下一個(gè)未曾訪問過的鄰接點(diǎn)作為新的出發(fā)點(diǎn)，若這樣的鄰接點(diǎn)多于一個(gè)，則選中的總是序號較小的那一個(gè)?！纠繉B通圖G7用鄰接矩陣表示時(shí)，以v0為初始出發(fā)點(diǎn)的DFS遍歷過程如下圖（a）所示，具體算法的執(zhí)行過程【參見動畫演示】。DFS序列是v0，v1，v2,v5,v4,v6,v3,v7②只有給出了鄰接表的內(nèi)容及初始出發(fā)點(diǎn)，才能惟一確定其DFS序列鄰接表作為給定圖的存儲結(jié)構(gòu)時(shí)，其表示不惟一。因?yàn)猷徑颖砩线叡砝锏泥徑狱c(diǎn)域的內(nèi)容與建表時(shí)的輸入次序相關(guān)。因此，只有給出了鄰接表的內(nèi)容及初始出發(fā)點(diǎn)，才能惟一確定其DFS序列?！纠窟B通圖G7用鄰接表表示時(shí)，以v0為初始出發(fā)點(diǎn)的DFS算法的執(zhí)行過程和DFS序列【參見動畫演示】（3）棧在深度優(yōu)先遍歷算法中的作用深度優(yōu)先遍歷過程中，后訪問的頂點(diǎn)其鄰接點(diǎn)被先訪問，故在遞歸調(diào)用過程中使用棧（系統(tǒng)運(yùn)行時(shí)刻棧）來保存已訪問的頂點(diǎn)。5、算法分析對于具有n個(gè)頂點(diǎn)和e條邊的無向圖或有向圖，遍歷算法DFSTraverse對圖中每頂點(diǎn)至多調(diào)用一次DFS或DFSM。從DFSTraverse中調(diào)用DFS（或DFSM）及DFS（或DFSM）內(nèi)部遞歸調(diào)用自己的總次數(shù)為n。當(dāng)訪問某頂點(diǎn)vi時(shí)，DFS（或DFSM）的時(shí)間主要耗費(fèi)在從該頂點(diǎn)出發(fā)搜索它的所有鄰接點(diǎn)上。用鄰接矩陣