掌握圖的兩種遍歷算法深度優(yōu)先搜索和廣度優(yōu)先搜索算.doc

《掌握圖的兩種遍歷算法深度優(yōu)先搜索和廣度優(yōu)先搜索算.doc》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。

1、第五章圖第十七講圖的遍歷1．掌握圖的兩種遍歷算法：深度優(yōu)先搜索和廣度優(yōu)先搜索算法，2．求解連通性問題的方法。?教學(xué)重點：圖的兩種遍歷算法：深度優(yōu)先搜索和廣度優(yōu)先搜索算法?教學(xué)難點：圖的兩種遍歷算法：深度優(yōu)先搜索和廣度優(yōu)先搜索算法?授課內(nèi)容5.3圖的遍歷和樹的遍歷類似，在此，我們希望從圖中某一頂點出發(fā)訪遍圖中其余頂點，且使每一個頂點僅被訪問一次。這一過程就叫做圖的遍歷(TraversingGraph)。圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關(guān)鍵路徑等算法的基礎(chǔ)。然而，圖的遍歷要比樹的遍歷復(fù)雜得多。因為圖的任一

2、頂點都可能和其余的頂點相鄰接。所以在訪問了某個頂點之后，可能沿著某條路徑搜索之后，又回到該頂點上。[例如]圖7.1(b)中的G2，由于圖中存在回路，因此在訪問了v1,v2,v3,v4之后，沿著邊(v4,v1)又可訪問到v1。為了避免同一頂點被訪問多次，在遍歷圖的過程中，必須記下每個已訪問過的頂點。為此，我們可以設(shè)一個輔助數(shù)組visited[0..n-1]，它的初始值置為“假”或者零，一旦訪問了頂點vi，便置visited[i]為“真”或者為被訪問時的次序號。???通常有兩條遍歷圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。

3、它們對無向圖和有向圖都適用。5.3.1深度優(yōu)先搜索深度優(yōu)先搜索(Depth-FirstSearch)遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。其基本思想如下：假定以圖中某個頂點vi為出發(fā)點，首先訪問出發(fā)點，然后選擇一個vi的未訪問過的鄰接點vj，以vj為新的出發(fā)點繼續(xù)進行深度優(yōu)先搜索，直至圖中所有頂點都被訪問過。顯然，這是一個遞歸的搜索過程?，F(xiàn)以圖5-3-1第五章圖中G為例說明深度優(yōu)先搜索過程。假定v0是出發(fā)點，首先訪問v0。因v0有兩個鄰接點v1、v2均末被訪問過，可以選擇v1作為新的出發(fā)點，訪問v1之后，再

4、找v1的末訪問過的鄰接點。同v1鄰接的有v0、v3和v4，其中v0已被訪問過，而v3、v4尚未被訪問過，可以選擇v3作為新的出發(fā)點。重復(fù)上述搜索過程，繼續(xù)依次訪問v7、v4。訪問v4之后，由于與v4相鄰的頂點均已被訪問過，搜索退回到v7。由于v7、v3和v1都是沒有末被訪問的鄰接點，所以搜索過程連續(xù)地從v7退回到v3，再退回v1，最后退回到v0。這時再選擇v0的末被訪問過的鄰接點v2，繼續(xù)往下搜索，依次訪問v2、v5和v6，止此圖中全部頂點均被訪問過。遍歷過程見圖5-3-1（b），得到的頂點的訪問序列為：v0→v1

5、→v3→v7→v4→v2→v5→v7。（a）無向圖G(b)G的深度優(yōu)先搜索過程圖5-3-1深度優(yōu)先搜索遍歷過程示例因為深度優(yōu)先搜索遍歷是遞歸定義的，故容易寫出其遞歸算法。下面的算法5.3是以鄰接矩陣作為圖的存儲結(jié)構(gòu)下的深度優(yōu)先搜索遍歷算法；算法5.4是以鄰接表作為圖的存儲結(jié)構(gòu)下的深度優(yōu)先搜索遍歷算法。算法5.3intvisited[NAX_VEX]={0};voidDfs_m(Mgraph*G,inti){/*從第i個頂點出發(fā)深度優(yōu)先遍歷圖G，G以鄰接矩陣表示*/printf("%3c",G->vexs[i]);v

6、isited[i]=1;for(j=0;jarcs[i][j]==1)&&(!visited[j]))Dfs_m(G,j);}/*Dfs_m*/算法5.4intvisited[VEX_NUM]={0};voidDfs_L(ALgraphG,inti){/*從第i個頂點出發(fā)深度優(yōu)先遍歷圖G，G以鄰接表表示*/printf("%3c",G[i].data);visited[i]=1;p=G[i].firstarc;while(p!=NULL){if(visited[p->adjv

7、ex]==0)Dfs_L(G,p->adjvex);p=p->nextarc;第五章圖}}/*dfs_L*/分析上述算法得知，遍歷圖的過程實質(zhì)上是對每個頂點搜索其鄰接點的過程。其耗費的時間取決于所采用的存儲結(jié)構(gòu)。假設(shè)圖有>n個頂點，那么，當用鄰接矩陣表示圖時，搜索一個頂點的所有鄰接點需花費的時間為>O(n)，則從>n個頂點出發(fā)搜索的時間應(yīng)為>O(n2)，所以算法>5.1的時間復(fù)雜度是>O(n2)；如果使用鄰接表來表示圖時，需花費時間為>O（n+e)，其中>e為無向圖中邊的數(shù)目或有向圖中弧的數(shù)目。算法>5.4的時間復(fù)

8、雜度為>O（n+e)。5.3.2廣度優(yōu)先搜索連通圖的廣度優(yōu)先搜索(Breadth_FirstSearch)遍歷圖類似于樹的按層次遍歷。其基本思想是：首先訪問圖中某指定的起始點Vi并將其標記為已訪問過，然后由Vi出發(fā)訪問與它相鄰接的所有頂點Vj、Vk……，并均標記為已訪問過，然后再按照Vj、Vk……的次序，訪問每一個頂點的所有未被訪問過的鄰接頂點，并均標記為已