一、圖的深度優(yōu)先概述

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

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

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

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

1. 首先從一個(gè)未走到過的頂點(diǎn)作為起始頂點(diǎn)，比如1號(hào)頂點(diǎn)作為起點(diǎn)。
2. 沿1號(hào)頂點(diǎn)的邊去嘗試訪問其它未走到過的頂點(diǎn)，首先發(fā)現(xiàn)2號(hào)頂點(diǎn)還沒有走到過，于是來到了2號(hào)頂點(diǎn)。
3. 再以2號(hào)頂點(diǎn)作為出發(fā)點(diǎn)繼續(xù)嘗試訪問其它未走到過的頂點(diǎn)，這樣又來到了4號(hào)頂點(diǎn)。
4. 再以4號(hào)頂點(diǎn)作為出發(fā)點(diǎn)繼續(xù)嘗試訪問其它未走到過的頂點(diǎn)。
5. 但是，此時(shí)沿4號(hào)頂點(diǎn)的邊，已經(jīng)不能訪問到其它未走到過的頂點(diǎn)了，所以需要返回到2號(hào)頂點(diǎn)。
6. 返回到2號(hào)頂點(diǎn)后，發(fā)現(xiàn)沿2號(hào)頂點(diǎn)的邊也不能再訪問到其它未走到過的頂點(diǎn)。此時(shí)又會(huì)來到3號(hào)頂點(diǎn)（2->1->3），再以3號(hào)頂點(diǎn)作為出發(fā)點(diǎn)繼續(xù)訪問其它未走到過的頂點(diǎn)，于是又來到了5號(hào)頂點(diǎn)。
7. 至此，所有頂點(diǎn)我們都走到過了，遍歷結(jié)束。

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

1. 首先以一個(gè)未被訪問過的頂點(diǎn)作為起始頂點(diǎn)，沿當(dāng)前頂點(diǎn)的邊走到未訪問過的頂點(diǎn)；
2. 當(dāng)沒有未訪問過的頂點(diǎn)時(shí)，則回到上一個(gè)頂點(diǎn)，繼續(xù)試探別的頂點(diǎn)，直到所有的頂點(diǎn)都被訪問過。

在此我想用一句話來形容 “一路走到頭，不撞墻不回頭”。

二、實(shí)現(xiàn)

顯而易見，深度優(yōu)先搜索遍歷是沿著圖的某一條分支遍歷直到末端，然后回溯，再沿著另一條進(jìn)行同樣的遍歷，直到所有的頂點(diǎn)都被訪問過為止。

那么問題來了，該如何實(shí)現(xiàn)這一過程呢？

首先，我們來解決如何存儲(chǔ)一個(gè)圖的問題。最常用的方法是使用一個(gè)二維數(shù)組e來存儲(chǔ)，如下：

上圖二維數(shù)組中第 i 行第 j 列表示的就是頂點(diǎn) i 到頂點(diǎn) j 是否有邊。1 表示有邊，∞ 表示沒有邊，0 表示自己到自己（i=j）。這種存儲(chǔ)圖的方法稱為圖的鄰接矩陣存儲(chǔ)法。

同時(shí)我們發(fā)現(xiàn)：這個(gè)二維數(shù)組是沿著主對(duì)角線對(duì)稱的，因此上面這個(gè)圖是無向圖。無向圖指的是圖的邊沒有方向，例如邊1-5表示，1號(hào)頂點(diǎn)可以到5號(hào)頂點(diǎn)，5號(hào)頂點(diǎn)也可以到達(dá)1號(hào)頂點(diǎn)。

void dfs(int cur)//cur是當(dāng)前所在的頂點(diǎn)編號(hào) { printf('%d ',cur); sum++; //每訪問一個(gè)頂點(diǎn)sum就加1 if(sum==n) return; //所有的頂點(diǎn)都已經(jīng)訪問過則直接退出 for(i=1;i<=n;i++)>//從1號(hào)頂點(diǎn)到n號(hào)頂點(diǎn)依次嘗試，看哪些頂點(diǎn)與當(dāng)前頂點(diǎn)cur有邊相連 { //判斷當(dāng)前頂點(diǎn)cur到頂點(diǎn)i是否有邊，并判斷頂點(diǎn)i是否已訪問過 if(e[cur][i]==1 && book[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 用來記錄哪些頂點(diǎn)已經(jīng)訪問過，變量 sum 用來記錄已經(jīng)訪問過多少個(gè)頂點(diǎn)，變量 n 存儲(chǔ)的是圖的頂點(diǎn)的總個(gè)數(shù)。完整代碼如下：

#includeint book[101],sum,n,e[101][101];void dfs(int cur)//cur是當(dāng)前所在的頂點(diǎn)編號(hào) { int i; printf('%d ',cur); sum++; //每訪問一個(gè)頂點(diǎn)sum就加1 if(sum==n) return; //所有的頂點(diǎn)都已經(jīng)訪問過則直接退出 for(i=1;i<=n;i++)>//從1號(hào)頂點(diǎn)到n號(hào)頂點(diǎn)依次嘗試，看哪些頂點(diǎn)與當(dāng)前頂點(diǎn)cur有邊相連 { //判斷當(dāng)前頂點(diǎn)cur到頂點(diǎn)i是否有邊，并判斷頂點(diǎn)i是否已訪問過 if(e[cur][i]==1 && book[i]==0) { book[i]==1; //標(biāo)記頂點(diǎn)i已經(jīng)訪問過 dfs(i); //從頂點(diǎn)i再出發(fā)繼續(xù)遍歷 } } return; } int main() { int i,j,m,a,b; scanf('%d %d',&n,&m); for(i=1;i<=n;i++)>//初始化二維矩陣 for(j=1;j<>) if(i == j) e[i][j]=0; else e[i][j]=99999999; //在這里假設(shè)99999999為正無窮 //讀入頂點(diǎn)之間的邊 for(i=1;i<>) { scanf('%d %d',&a,&b); e[a][b] = 1; e[b][a] = 1;//這里是無向圖，所以需要將e[b][a]也賦為1 } //從1號(hào)頂點(diǎn)出發(fā) book[1]=1; //標(biāo)記1號(hào)頂點(diǎn)已被訪問 dfs(1); //從1號(hào)頂點(diǎn)開始遍歷 getchar();getchar(); return 0; }