在http://www.cnblogs.com/yanlingyin/archive/2011/12/26/Depth-firstsearch.html 介绍了递归的深度搜索，写的比较好，最后我补充他的非递归方法。
图是一种常见的数据结构，深度优先和广度优先搜索都是常用的算法，这篇博文先介绍深度优先搜索。
和往常一样的，我会用朴实的语言来介绍它，所以只要认真看一定能理解。开始会先介绍下图的表示方法，如果已经掌握了大可跳过。
图的表示
要表示一个图G(V,E)有两种常见的表示方法，邻接矩阵和邻接表。这两种方法可用于有向图和无向图。对于稀疏图，常用邻接表表示，
它占用的空间|E|要小于|V|*|V|。
邻接表：
图G(V,E)的邻接表表示由一个包含V列表的数组Adj组成，其中的每个列表对应于V中的一个顶点，对于v中的任意一个点u，灵界表Adj[u]
包含所有满足条件(u,v)属于E的点v，也就是Adj[u]中包含所有和u相邻的点。
邻接矩阵：
用一个矩阵表示，矩阵的横向和纵向分别为图中的点的有序排列，如果两个点之间有边相连对应的矩阵中的元素就是1，反之就是0.
看下图实例就能很好的理解~
对于一个无向图，所有邻接表的长度之和是2|E|，如果是有向图为|E|（无向图的每一条边都被表示了两遍）
它有潜在的不足之处，如果要判断边(u,v)是否存在，只能在表Adj[u]中搜索v。如果有则存在，没有则不存在。
在图G(V,E)的邻接矩阵表示法中，假定个顶点按照某种任意的方式编号1,2,3、、|V|，那么G的邻接矩阵就是一个
|V|*|V|的举证A=(aij),它满足：
它要占用|V|*|V|的空间，和边的数量无关。
深度优先搜索：
深度优先搜索是尽可能深的搜索一个图，对于一个新发现的节点，如果还有以此为起点还未探测到的边，就沿此边探测下去。
当顶点v的所有边都被探寻过后，搜索将回溯到发现顶点v的起始点的那些边。这一过程一直进行到一发现从原点可达的所有点为止。
如果还存在未发现的顶点，则选择其中一个座位源顶点，重复上过程。
补充：
1、在这个过程中可以记录每个点访问的时间。
在访问点的时候记录下一个时间 t_start，当这个点所有邻居都被访问的时候记录时间 t_end.那么访问的时间 t =t_end-t_start.
在算法中开始和结束的时间描述为d[u]和f[u].
2、在每一次深度优先遍历的时候都记录下访问节点的前驱节点，可以用一个数组 f[i] 来存放，当完成遍历的是，就可以利用 f[i] 里面的数据来得到深度遍历的顺序。它的逆序就是
这个图的一个拓扑排序。
搜索过程中，可以通过对顶点着色来表示顶点的状态，开始时每个顶点都是白色，搜索过程中被发先置为灰色，
结束时变为黑色，也就是每个有其他邻居可方位的时候。并且用d[u]和f[u]来记录点开始方问和结束访问的时间。
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行把所有点置为白的，第三行把每个节点的父节点设置为空。第四行让时间计数为0。 5-7行一次检索v中的顶点，如果是白色，
就调用DFS-VISIT访问该节点。每次调用DFS-VISIT(u)时，u就成为深度优先遍历中的一颗树根。
调用DFS-VISIT(u)是，开始u置为灰色，第二行让time增值，第三行记录u的访问开始时间d[u]，4-7行检查u的邻居，如果存在没有被
访问的点，则深度优先遍历该点。第8行，因为访问了u 的所有邻居，u成了死节点，把u的颜色置为黑色，第9行记录u的访问结束时间。
深度优先遍历的过程可以用下图表示：
深度优先搜索的结果可能依赖于第DFS中5行中各个节点的访问顺序，也可能依赖于DFS-VISIT中的第4行中u的邻居的访问顺序。
下面是c++实现：
View Code
/*
图的深度优先遍历
出处：一条鱼@博客园
http://www.cnblogs.com/yanlingyin/
2011-12-26
*/
#include
#include
struct node /* 图顶点结构定义 */
{
int vertex; /* 顶点数据信息 */
struct node *nextnode; /* 指下一顶点的指标 */
};
typedef struct node *graph; /* 图形的结构新型态 */
struct node head[ 9]; /* 图形顶点数组 */
int visited[ 9]; /* 遍历标记数组 */
/* *根据已有的信息建立邻接表* */
void creategraph( int node[ 20][ 2], int num) /* num指的是图的边数 */
{
graph newnode; /* 指向新节点的指针定义 */
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; /* 建立顶点内容 */
newnode->nextnode = NULL; /* 设定指标初值 */
ptr = &(head[ from]); /* 顶点位置 */
while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */
ptr = ptr->nextnode; /* 下一个顶点 */
ptr->nextnode = newnode; /* 插入节点 */
}
}
/* * 图的深度优先搜寻法* */
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}, /* 边线数组 */
{ 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++ ) /* 顶点数组初始化 */
{
head[i].vertex = i; /* 设定顶点值 */
head[i].nextnode = NULL; /* 指针为空 */
visited[i] = 0; /* 设定遍历初始标志 */
}
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); /* 印出顶点内容 */
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上编译通过。
图的深度优先搜索可以用栈来实现，对某一层的点比如有A,B,C都把他们入栈，每次都把栈顶元素的孩子入栈，当某个点没有孩子的时候，
就回退到有孩子的节点，把它的孩子入栈，重复上过程，直到根节点的每一个孩子都入栈，最后的出栈顺序就是深度优先遍历的顺序。
相应的，广度优先搜索利用队列来实现，对于某一层的点A,B,C，把他们入队列，然后队列头出队列，对头的孩子入队列，如果A有孩子M,N
，那么A出队列后队列为：ＢＣＭＮ，下一步就是Ｂ出队列，Ｂ的孩子入队列、、、、最后出队列的顺序就是广度优先遍历的顺序。
下一篇将会介绍广度优先搜索算法~
非递归程序：
/* 图的深度优先遍历 出处：一条鱼@博客园 http://www.cnblogs.com/yanlingyin/ 2011-12-26 */ #include
#include
struct node /* 图顶点结构定义 */ { int vertex; /* 顶点数据信息 */ struct node *nextnode; /* 指下一顶点的指标 */ }; typedef struct node *graph; /* 图形的结构新型态 */ struct node head[9]; /* 图形顶点数组 */ int visited[9]; /* 遍历标记数组 */ /根据已有的信息建立邻接表/ void creategraph(int node[20][2],int num)/*num指的是图的边数*/ { graph newnode; /*指向新节点的指针定义*/ 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; /* 建立顶点内容 */ newnode->nextnode = NULL; /* 设定指标初值 */ ptr = &(head[from]); /* 顶点位置 */ while ( ptr->nextnode != NULL ) /* 遍历至链表尾 */ ptr = ptr->nextnode; /* 下一个顶点 */ ptr->nextnode = newnode; /* 插入节点 */ } } / 图的深度优先搜寻法/ void dfs(node head[9],int current){/*非递归深度优先遍历算法*/ node* p; node* stack[9]; int top=-1,vertex; printf("%d\n",current); visited[current] = 1; stack[++top] = head[current].nextnode; while(top > -1){ p = stack[top]; while(p != NULL){ vertex = p->vertex; if(visited[vertex] == 0){ printf("%d\n",vertex); visited[vertex] = 1; stack[++top] = head[vertex].nextnode; //printf("%dss\n",stack[top]->vertex); break; } p = p->nextnode; } if(p == NULL){ top--; } } } / 主程序/ int main() { graph ptr; int node[20][2] = { {1, 2}, {2, 1}, /* 边线数组 */ {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++ ) /* 顶点数组初始化 */ { head[i].vertex = i; /* 设定顶点值 */ head[i].nextnode = NULL; /* 指针为空 */ visited[i] = 0; /* 设定遍历初始标志 */ } 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); /* 印出顶点内容 */ ptr = ptr->nextnode; /* 下一个顶点 */ } printf("\n"); /* 换行 */ } printf("\nThe end of the dfs are:\n"); dfs(head,1); /* 打印输出遍历过程 */ printf("\n"); printf("\nThe end of the dfs are:\n"); /* 换行 */ // getch(); }
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/229490.html原文链接：https://javaforall.net
