圖的兩種圖的遍歷方法

1、5.3 圖的遍歷 和樹的遍歷類似，在此，我們希望從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個頂點(diǎn)僅被訪問一次。這一過程就叫做圖的遍歷(TraversingGraph)。圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。然而，圖的遍歷要比樹的遍歷復(fù)雜得多。因為圖的任一頂點(diǎn)都可能和其余的頂點(diǎn)相鄰接。所以在訪問了某個頂點(diǎn)之后，可能沿著某條路徑搜索之后，又回到該頂點(diǎn)上。例如圖7.1(b)中的G2，由于圖中存在回路，因此在訪問了v1,v2,v3,v4之后，沿著邊(v4 , v1)又可訪問到v1。為了避免同一頂點(diǎn)被訪問多次，在遍歷圖的過程中，必須記下每個已訪問過的頂點(diǎn)。為此，我們可以設(shè)

2、一個輔助數(shù)組visited0.n-1，它的初始值置為“假”或者零，一旦訪問了頂點(diǎn)vi，便置visitedi為“真”或者為被訪問時的次序號。    通常有兩條遍歷圖的路徑：深度優(yōu)先搜索和廣度優(yōu)先搜索。它們對無向圖和有向圖都適用。5.3.1 深度優(yōu)先搜索 深度優(yōu)先搜索(Depth-First Search)遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。其基本思想如下：假定以圖中某個頂點(diǎn)vi為出發(fā)點(diǎn)，首先訪問出發(fā)點(diǎn)，然后選擇一個vi的未訪問過的鄰接點(diǎn)vj，以vj為新的出發(fā)點(diǎn)繼續(xù)進(jìn)行深度優(yōu)先搜索，直至圖中所有頂點(diǎn)都被訪問過。顯然，這是一個遞歸的搜索過程。 現(xiàn)以圖5-3-1

3、中G為例說明深度優(yōu)先搜索過程。假定v0是出發(fā)點(diǎn)，首先訪問v0。因v0有兩個鄰接點(diǎn)v1、v2均末被訪問過，可以選擇v1作為新的出發(fā)點(diǎn)，訪問v1之后，再找v1的末訪問過的鄰接點(diǎn)。同v1鄰接的有v0、v3和v4，其中v0已被訪問過，而v3、v4尚未被訪問過，可以選擇v3作為新的出發(fā)點(diǎn)。重復(fù)上述搜索過程，繼續(xù)依次訪問v7、v4 。訪問v4之后，由于與v4相鄰的頂點(diǎn)均已被訪問過，搜索退回到v7。由于v7、v3和v1都是沒有末被訪問的鄰接點(diǎn)，所以搜索過程連續(xù)地從v7退回到v3，再退回v1，最后退回到v0。這時再選擇v0的末被訪問過的鄰接點(diǎn)v2，繼續(xù)往下搜索，依次訪問v2、v5和v6，止此圖中全部頂點(diǎn)均被訪

4、問過。遍歷過程見圖5-3-1（b），得到的頂點(diǎn)的訪問序列為：v0 v1 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.3int visitedNAX_VEX=0;void Dfs_m( Mgraph *G,int i)/* 從第i個頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，G以鄰接矩陣表示*/printf("%3c",G-&g

5、t;vexsi);visitedi=1;for (j=0;j<VEX_NUM;j+)if(G->arcsij=1)&& (!visitedj)Dfs_m(G,j); /*Dfs_m */算法5.4int visitedVEX_NUM=0;void Dfs_L(ALgraph G,int i)/* 從第i個頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G，G以鄰接表表示 */printf("%3c",Gi.data);visitedi=1;p=Gi.firstarc;while (p!=NULL) if(visitedp->adjvex=0)Dfs_L(G,p-&g

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

7、的廣度優(yōu)先搜索(Breadth_FirstSearch)遍歷圖類似于樹的按層次遍歷。其基本思想是：首先訪問圖中某指定的起始點(diǎn)Vi并將其標(biāo)記為已訪問過，然后由Vi出發(fā)訪問與它相鄰接的所有頂點(diǎn)Vj、 Vk，并均標(biāo)記為已訪問過，然后再按照Vj、Vk的次序，訪問每一個頂點(diǎn)的所有未被訪問過的鄰接頂點(diǎn)，并均標(biāo)記為已訪問過，下一步再從這些頂點(diǎn)出發(fā)訪問與它們相鄰接的尚未被訪問的頂點(diǎn)，如此做下去，直到所有的頂點(diǎn)均被訪問過為止。    在廣度優(yōu)先搜索中，若對頂點(diǎn)V1的訪問先于頂點(diǎn)V2的訪問，則對V1鄰接頂點(diǎn)的訪問也先于V2鄰接頂點(diǎn)的訪問。就是說廣度優(yōu)先搜索中對鄰接點(diǎn)的尋找具

8、有“先進(jìn)先出”的特性。因此，為了保證訪問頂點(diǎn)的這種先后關(guān)系，需借助一個隊列暫存那些剛訪問過的頂點(diǎn)。 例如，下面以圖5-3-1種G為例說明廣度優(yōu)先搜索的過程。假設(shè)從起點(diǎn)v0出發(fā)，那么首先訪問vo和行動兩個未訪問的鄰接點(diǎn)v1和v2；然后依次訪問v1的鄰接點(diǎn)v3和v4以及v2的鄰接點(diǎn)v5和v6；最后訪問v3的未曾訪問的鄰接點(diǎn)v7。此圖中所有頂點(diǎn)均已被訪問過，由此完成了圖的遍歷。遍歷過程見圖5-3-2，得到的頂點(diǎn)訪問序列為： v0v1v2v3v4v5v6v7在廣度優(yōu)先搜索中，若頂點(diǎn)v在頂點(diǎn)u之前訪問，則v的鄰接點(diǎn)也將在u的鄰接點(diǎn)之前訪問。由此，可采用對列qu來暫存那些剛訪問過并且可能還有未訪問的鄰接點(diǎn)的頂點(diǎn)。v0V1V3V7V4V2V5V6    圖532 廣度優(yōu)先搜索遍歷過程 算法5.5 int visitedVEX_NUM=0; void Bfs(Mgraph G,int k) int qu20,f=0,r=0; printf(“%3c”,G.vexsk); visitedk=1; r+;qur=k; while (r!=f) f+;i=quf;for(j=p;j<VEX_NUM;j+) if(G->arcsij=1&&(!visitecj) printf(“%3c”,G.vexsj); visitedj=