第C語言數(shù)據(jù)結(jié)構(gòu)與算法之圖的遍歷(一)目錄引入

深度優(yōu)先搜索代碼實(shí)現(xiàn)

完整代碼

引入

在數(shù)據(jù)結(jié)構(gòu)中常見的有深度優(yōu)先搜索和廣度優(yōu)先搜索。為什么叫深度和廣度呢？其實(shí)是針對(duì)圖的遍歷而言的，請(qǐng)看下面這個(gè)圖：

圖是由一些小圓點(diǎn)（稱為頂點(diǎn)）和連接這些點(diǎn)的直線（稱為邊）組成的。

例如上圖就是由5個(gè)頂點(diǎn)（編號(hào)為1,2,3,4,5）和5條邊（1-2,1-3,1-4,2-4）組成。

現(xiàn)在我們從1號(hào)頂點(diǎn)開始遍歷這個(gè)圖，遍歷就是把圖的每一個(gè)頂點(diǎn)都訪問一次。使用深度優(yōu)先搜索將會(huì)得到如下的結(jié)果。

圖中每個(gè)頂點(diǎn)旁邊的數(shù)表示這個(gè)頂點(diǎn)是第幾個(gè)被訪問到的，我們稱之為——時(shí)間戳

深度優(yōu)先搜索

使用深度優(yōu)先搜索來遍歷這個(gè)圖的過程：

首先從一個(gè)未走過的頂點(diǎn)作為起始頂點(diǎn)，比如以1號(hào)頂點(diǎn)作為起點(diǎn)。沿1號(hào)頂點(diǎn)的邊去嘗試其他它未走過的頂點(diǎn)，首先發(fā)現(xiàn)的是2號(hào)頂點(diǎn)還沒被走過，于是來到了2號(hào)頂點(diǎn)。

再以2號(hào)頂點(diǎn)作為出發(fā)點(diǎn)繼續(xù)嘗試訪問其他未走到過的頂點(diǎn)，這樣又來到了4號(hào)頂點(diǎn)。

再以4號(hào)頂點(diǎn)作為出發(fā)點(diǎn)繼續(xù)嘗試訪問其他未走過的頂點(diǎn)。但是，此時(shí)在4號(hào)頂點(diǎn)的周圍已經(jīng)沒有其他的頂點(diǎn)了，所以需要返回到2號(hào)頂點(diǎn)。返回到2號(hào)頂點(diǎn)后，發(fā)現(xiàn)沿2號(hào)頂點(diǎn)也不能在訪問到其他未走到的點(diǎn)了，此時(shí)又需要返回到1號(hào)頂點(diǎn)。

繼續(xù)以1號(hào)頂點(diǎn)嘗試訪問其他頂點(diǎn)，我們來到了3號(hào)點(diǎn)。以此類推，我們最后來到了5號(hào)點(diǎn)。到此，所以的頂點(diǎn)都走過了，遍歷結(jié)束

深度優(yōu)先搜索的主要思想是：

首先以一個(gè)未被訪問的頂點(diǎn)作為起始頂點(diǎn)，沿當(dāng)前頂點(diǎn)的邊走到未被訪問過的頂點(diǎn)

當(dāng)沒有未訪問過的頂點(diǎn)時(shí)，則回到上一個(gè)頂點(diǎn)，繼續(xù)試探訪問別的頂點(diǎn)，直到所有的頂點(diǎn)都被訪問過。

顯然，深度優(yōu)先搜索是沿著圖的某一條分支遍歷直至末端，然后回溯，再沿另一條實(shí)現(xiàn)相同的遍歷，直到所以的頂點(diǎn)都被訪問完為止。

代碼實(shí)現(xiàn)

上面的二維數(shù)組中第i行第j列就是表示頂點(diǎn)i到頂點(diǎn)j是否有邊。

1表示有邊，x表示沒有邊，0表示頂點(diǎn)自己到自己。

我們將這種方法稱為——

圖的鄰接矩陣儲(chǔ)存法。

細(xì)心的朋友可能會(huì)發(fā)現(xiàn)這張圖沿著對(duì)角線全部是0，因?yàn)樯厦孢@張圖是無向圖。

所謂無向圖就是指圖的邊沒有方向。例如邊1-5表示1號(hào)頂點(diǎn)可以到5號(hào)頂點(diǎn)，5號(hào)頂點(diǎn)也可以到1號(hào)頂點(diǎn)。

接下來就是解決怎么用深度優(yōu)先搜索來實(shí)現(xiàn)遍歷了：

voiddfs(intcur)//cur是當(dāng)前所在的頂點(diǎn)編號(hào)

printf("%d",cur);

sum++;//每訪問一個(gè)點(diǎn)就sum++

if(sum==n)return;//所有的頂點(diǎn)都訪問過了

for(i=1;ii++)//從1到n的頂點(diǎn)依次嘗試，看看有哪些頂點(diǎn)與當(dāng)前頂點(diǎn)cur有邊相連

//判斷當(dāng)前頂點(diǎn)cur到頂點(diǎn)i是否有邊，并判斷頂點(diǎn)i是否已被訪問過

if(e[cur][i]==1book[i]==0)

book[i]=1;//標(biāo)記頂點(diǎn)i已經(jīng)訪問過

dfs(i);//從頂點(diǎn)i出發(fā)繼續(xù)遍歷

return;

}

在上面的代碼中變量cur存儲(chǔ)的是當(dāng)前正在遍歷的點(diǎn)，二維數(shù)組e存儲(chǔ)的就是圖的邊（鄰接矩陣），數(shù)組book用來標(biāo)記哪些頂點(diǎn)已經(jīng)訪問過，變量sum用來記錄已經(jīng)訪問多少個(gè)頂點(diǎn)，變量你存儲(chǔ)的是圖的頂點(diǎn)總個(gè)數(shù)。

完整代碼

#includestdio.h

intbook[101],sum,n,e[101][101];

voiddfs(intcur)//cur是當(dāng)前所在的頂點(diǎn)編號(hào)

printf("%d",cur);

sum++;//每訪問一個(gè)點(diǎn)就sum++

if(sum==n)return;//所有的頂點(diǎn)都訪問過了

for(i=1;ii++)//從1到n的頂點(diǎn)依次嘗試，看看有哪些頂點(diǎn)與當(dāng)前頂點(diǎn)cur有邊相連

//判斷當(dāng)前頂點(diǎn)cur到頂點(diǎn)i是否有邊，并判斷頂點(diǎn)i是否已被訪問過

if(e[cur][i]==1book[i]==0)

book[i]=1;//標(biāo)記頂點(diǎn)i已經(jīng)訪問過

dfs(i);//從頂點(diǎn)i出發(fā)繼續(xù)遍歷

return;

intmain()

inti,j,m,a,b;

scanf("%d%d",n,

//初始化二維矩陣

for(i=1;ii++)

for(j=1;jj++)

if(i==j)e[i][j]=0;

elsee[i][j]=99999999;//我們假設(shè)99999999為x

//讀入頂點(diǎn)之間的邊

for(i=1;ii++)

scanf("%d%d",a,

e[a][b]=