圖的深度優(yōu)先搜索/Depth-first search/C++
圖是一種常見的數(shù)據(jù)結(jié)構(gòu)，深度優(yōu)先和廣度優(yōu)先搜索都是常用的算法，這篇博文先介紹深度優(yōu)先搜索。
和往常一樣的，我會用樸實的語言來介紹它，所以只要認(rèn)真看一定能理解。開始會先介紹下圖的表示方法，如果已經(jīng)掌握了大可跳過。
圖的表示
要表示一個圖G(V,E)有兩種常見的表示方法，鄰接矩陣和鄰接表。這兩種方法可用于有向圖和無向圖。對于稀疏圖，常用鄰接表表示，
它占用的空間|E|要小于|V|*|V|。
鄰接表：
圖G(V,E)的鄰接表表示由一個包含V列表的數(shù)組Adj組成，其中的每個列表對應(yīng)于V中的一個頂點，對于v中的任意一個點u，靈界表Adj[u]
包含所有滿足條件(u,v)屬于E的點v，也就是Adj[u]中包含所有和u相鄰的點。
鄰接矩陣：
用一個矩陣表示，矩陣的橫向和縱向分別為圖中的點的有序排列，如果兩個點之間有邊相連對應(yīng)的矩陣中的元素就是1，反之就是0.
看下圖實例就能很好的理解~
對于一個無向圖，所有鄰接表的長度之和是2|E|，如果是有向圖為|E|（無向圖的每一條邊都被表示了兩遍）
它有潛在的不足之處，如果要判斷邊(u,v)是否存在，只能在表Adj[u]中搜索v。如果有則存在，沒有則不存在。
在圖G(V,E)的鄰接矩陣表示法中，假定個頂點按照某種任意的方式編號1,2,3、、|V|，那么G的鄰接矩陣就是一個
|V|*|V|的舉證A=(aij),它滿足：
它要占用|V|*|V|的空間，和邊的數(shù)量無關(guān)。
深度優(yōu)先搜索：
深度優(yōu)先搜索是盡可能深的搜索一個圖，對于一個新發(fā)現(xiàn)的節(jié)點，如果還有以此為起點還未探測到的邊，就沿此邊探測下去。
當(dāng)頂點v的所有邊都被探尋過后，搜索將回溯到發(fā)現(xiàn)頂點v的起始點的那些邊。這一過程一直進(jìn)行到一發(fā)現(xiàn)從原點可達(dá)的所有點為止。
如果還存在未發(fā)現(xiàn)的頂點，則選擇其中一個座位源頂點，重復(fù)上過程。
補(bǔ)充：
1、在這個過程中可以記錄每個點訪問的時間。
在訪問點的時候記錄下一個時間 t_start，當(dāng)這個點所有鄰居都被訪問的時候記錄時間 t_end.那么訪問的時間 t =t_end-t_start.
在算法中開始和結(jié)束的時間描述為d[u]和f[u].
2、在每一次深度優(yōu)先遍歷的時候都記錄下訪問節(jié)點的前驅(qū)節(jié)點，可以用一個數(shù)組 f[i] 來存放，當(dāng)完成遍歷的是，就可以利用 f[i] 里面的數(shù)據(jù)來得到深度遍歷的順序。它的逆序就是
這個圖的一個拓?fù)渑判颉?/p>
搜索過程中，可以通過對頂點著色來表示頂點的狀態(tài)，開始時每個頂點都是白色，搜索過程中被發(fā)先置為灰色，
結(jié)束時變?yōu)楹谏簿褪敲總€有其他鄰居可方位的時候。并且用d[u]和f[u]來記錄點開始方問和結(jié)束訪問的時間。
Vertices initially colored white
Then colored gray when discovered
Then black when finished
d[u]: discovery time, a counter indicating when vertex u is discovered.
f[u]: finishing time, a counter indicating when the processing of vertex u (and the processing of all its descendants ) is finished.
算法描述：
1-3行把所有點置為白的，第三行把每個節(jié)點的父節(jié)點設(shè)置為空。第四行讓時間計數(shù)為0。 5-7行一次檢索v中的頂點，如果是白色，
就調(diào)用DFS-VISIT訪問該節(jié)點。每次調(diào)用DFS-VISIT(u)時，u就成為深度優(yōu)先遍歷中的一顆樹根。
調(diào)用DFS-VISIT(u)是，開始u置為灰色，第二行讓time增值，第三行記錄u的訪問開始時間d[u]，4-7行檢查u的鄰居，如果存在沒有被
訪問的點，則深度優(yōu)先遍歷該點。第8行，因為訪問了u 的所有鄰居，u成了死節(jié)點，把u的顏色置為黑色，第9行記錄u的訪問結(jié)束時間。
深度優(yōu)先遍歷的過程可以用下圖表示：
深度優(yōu)先搜索的結(jié)果可能依賴于第DFS中5行中各個節(jié)點的訪問順序，也可能依賴于DFS-VISIT中的第4行中u的鄰居的訪問順序。
下面是c++實現(xiàn)：
View Code
/*
圖的深度優(yōu)先遍歷
出處：一條魚@博客園 http://www.rzrgm.cn/yanlingyin/
2011-12-26
*/
#include <stdlib.h>
#include <stdio.h>
struct node /* 圖頂點結(jié)構(gòu)定義 */
{
int vertex; /* 頂點數(shù)據(jù)信息 */
struct node *nextnode; /* 指下一頂點的指標(biāo) */
};
typedef struct node *graph; /* 圖形的結(jié)構(gòu)新型態(tài) */
struct node head[9]; /* 圖形頂點數(shù)組 */
int visited[9]; /* 遍歷標(biāo)記數(shù)組 */
/********************根據(jù)已有的信息建立鄰接表********************/
void creategraph(int node[20][2],int num)/*num指的是圖的邊數(shù)*/
{
graph newnode; /*指向新節(jié)點的指針定義*/
graph ptr;
int from; /* 邊的起點 */
int to; /* 邊的終點 */
int i;
for ( i = 0; i < num; i++ ) /* 讀取邊線信息，插入鄰接表*/
{
from = node[i][0]; /* 邊線的起點 */
to = node[i][1]; /* 邊線的終點 */
/* 建立新頂點 */
newnode = ( graph ) malloc(sizeof(struct node));
newnode->vertex = to; /* 建立頂點內(nèi)容 */
newnode->nextnode = NULL; /* 設(shè)定指標(biāo)初值 */
ptr = &(head[from]); /* 頂點位置 */
while ( ptr->nextnode != NULL ) /* 遍歷至鏈表尾 */
ptr = ptr->nextnode; /* 下一個頂點 */
ptr->nextnode = newnode; /* 插入節(jié)點 */
}
}
/********************** 圖的深度優(yōu)先搜尋法********************/
void dfs(int current)
{
graph ptr;
visited[current] = 1; /* 記錄已遍歷過 */
printf("vertex[%d]\n",current); /* 輸出遍歷頂點值 */
ptr = head[current].nextnode; /* 頂點位置 */
while ( ptr != NULL ) /* 遍歷至鏈表尾 */
{
if ( visited[ptr->vertex] == 0 ) /* 如過沒遍歷過 */
dfs(ptr->vertex); /* 遞回遍歷呼叫 */
ptr = ptr->nextnode; /* 下一個頂點 */
}
}
/****************************** 主程序******************************/
int main()
{
graph ptr;
int node[20][2] = { {1, 2}, {2, 1}, /* 邊線數(shù)組 */
{1, 3}, {3, 1},
{1, 4}, {4, 1},
{2, 5}, {5, 2},
{2, 6}, {6, 2},
{3, 7}, {7, 3},
{4, 7}, {4, 4},
{5, 8}, {8, 5},
{6, 7}, {7, 6},
{7, 8}, {8, 7} };
int i;
//clrscr();
for ( i = 1; i <= 8; i++ ) /* 頂點數(shù)組初始化 */
{
head[i].vertex = i; /* 設(shè)定頂點值 */
head[i].nextnode = NULL; /* 指針為空 */
visited[i] = 0; /* 設(shè)定遍歷初始標(biāo)志 */
}
creategraph(node,20); /* 建立鄰接表 */
printf("Content of the gragh's ADlist is:\n");
for ( i = 1; i <= 8; i++ )
{
printf("vertex%d ->",head[i].vertex); /* 頂點值 */
ptr = head[i].nextnode; /* 頂點位置 */
while ( ptr != NULL ) /* 遍歷至鏈表尾 */
{
printf(" %d ",ptr->vertex); /* 印出頂點內(nèi)容 */
ptr = ptr->nextnode; /* 下一個頂點 */
}
printf("\n"); /* 換行 */
}
printf("\nThe end of the dfs are:\n");
dfs(1); /* 打印輸出遍歷過程 */
printf("\n"); /* 換行 */
puts(" Press any key to quit...");
// getch();
}
以上代碼cfree5上編譯通過。
圖的深度優(yōu)先搜索可以用棧來實現(xiàn)，對某一層的點比如有A,B,C都把他們?nèi)霔＃看味及褩ｍ斣氐暮⒆尤霔＃?dāng)某個點沒有孩子的時候，
就回退到有孩子的節(jié)點，把它的孩子入棧，重復(fù)上過程，直到根節(jié)點的每一個孩子都入棧，最后的出棧順序就是深度優(yōu)先遍歷的順序。
相應(yīng)的，廣度優(yōu)先搜索利用隊列來實現(xiàn)，對于某一層的點A,B,C，把他們?nèi)腙犃校缓箨犃蓄^出隊列，對頭的孩子入隊列，如果A有孩子M,N
，那么A出隊列后隊列為：ＢＣＭＮ，下一步就是Ｂ出隊列，Ｂ的孩子入隊列、、、、最后出隊列的順序就是廣度優(yōu)先遍歷的順序。
下一篇將會介紹廣度優(yōu)先搜索算法~
參考資料：《Algorithms》
http://en.wikipedia.org/wiki/Depth-first_search
如有轉(zhuǎn)載請注明出處：http://www.rzrgm.cn/yanlingyin/
一條魚@博客園
2011-12-26
浙公網(wǎng)安備 33010602011771號