|
本篇文章分为三部分，
第一部分介绍DFS的算法思想； 第二部分给出DFS两种数据结构的算法描述； 第三部分给出DFS基于两种图数据结构（邻接矩阵、邻接表）的C++代码实现
-----------------------------------------------------------------------------------------------------------------------------
第一部分
DFS 即深度优先搜索，是一个递归的过程， 有回退的过程。它的算法思想是：对一个无向连通图，在访问图中某一起始顶点 v 后，
从 v 点出发， 访问顶点 v 的某一个邻接顶点 w1 ；然后再从 w1 出发，访问与顶点 w1 相邻接但是还没有访问过的顶点，
依次进行下去，直至图中所有的顶点都已经被访问过为止。
深度优先搜索一个连通图之后，将会的到一个深度优先生成树，即它是一个无环连通图，而无环连通图本质上来说即为一棵树。
第二部分，DFS 基于两种图的数据结构的算法描述，在这里需要注意一点的就是，DFS可以通过递归来实现，
但是当数据量十分大的情况下，会将递归转换为通过非递归的方式来实现， DFS 非递归实现所基于的数据结构是 栈。
a. 基于邻接表的 递归DFS 算法思想描述：
假设有函数 DFS(v) , 这个函数可以实现以顶点 v 出发访问与它相邻接的所有顶点，
在算法的实现过程中，必须要有一个数组用来记录那些顶点已经被访问过了，
而哪些顶点还没有被访问过。
可以设定一个数组 visited[1..n] 如果 visited[i] = 0 代表顶点 i 还没有被访问过，
如果 visited[i] = 1 ,代表顶点 i 已经被访问过了。
在算法最开始的时候，对visited [1..n] 进行初始化，将其中所有的数值置为 0 。
DFS（ 顶点 p ) //要对顶点 p 展开深度优先搜索
{
visited[ p ] <- 1
pointer <- 顶点 p 的邻接链表指针
while ( pointer )
{
x <- pointer.to
/*to 代表的是顶点 p 所对应的邻接链表中记录的
与顶点 p 相邻接的 顶点的编号
*/
if ( !visited [x] )
/* 因为顶点编号 x 出现在 顶点 p 的邻接链表中
所以可知 顶点 x 与 顶点 p 一定是相邻接的 ，
如果 顶点 x 还没有被访问过的话，
那么接下来将对顶点 x 进行深度遍历，
即让顶点 x 作为下一个DFS的顶点
这个地方时进入递归操作之前，对相关数据进行预处理的地方
*/
DFS( x )
/*这个地方时从递归返回之后，
对数据进行相应的后续操作的地方，
很多的应用中都需要在递归调用之前和调用之后
进行相关数据的更新和重置操作
*/
}
}
b. 基于邻接矩阵的 递归DFS 算法思想描述：
假设有函数 DFS(v) , 这个函数可以实现以顶点 v 出发访问与它相邻接的所有顶点，
在算法的实现过程中，必须要有一个数组用来记录那些顶点已经被访问过了，
而哪些顶点还没有被访问过。
可以设定一个数组 visited[1..n] 如果 visited[i] = 0 代表顶点 i 还没有被访问过，
如果 visited[i] = 1 ,代表顶点 i 已经被访问过了。
在算法最开始的时候，对visited [1..n] 进行初始化，将其中所有的数值置为 0 。
同时，由于这种方法基于的是邻接矩阵，
所以还需要有一个二维数组来存放各个顶点之间边的情况。
可以设定一个二维数组 map[1..n][1..n]
如果顶点 u, v 之间存在边相连通的话， 则有 map[u][v] = map[v][u] = 1
如果没有变连接，则将其数值置为 0 。
DFS( 顶点 p ）//从顶点 p 开始进行深度优先搜索
{
visited[p] = 1 ; //代表顶点 i 已经被访问过了
for i<- 1 to n do
if !visited[i] && map[i][p]== 1
{
//顶点 i 和顶点 p 是邻接点并且顶点 i 还没有被访问过
//这个地方对应的是递归操作之前的预处理操作的
DFS( i )
//这个地方时递归操作之后的，后续处理的
}
}
第三部分
a. 邻接表的深度优先搜索代码实现
在这里需要说明的一点就是， 下面的数据结构定义顶点 struct vnode 的时候， 里面有两个属性字段， 一个是head1 ，另一个是 head2
其中head1代表的是顶点作为出度顶点而邻接的下一个顶点， 而head2 所对应的是以当前顶点为入度顶点而邻接的下一个顶点。
可以举一个例子来说明，如果有顶点 1->8 的话， 对于顶点1 来说， 顶点8 是它作为出度顶点所邻接的顶点； 而对于顶点 8 来说，
顶点 1 是作为它的入度顶点而存在的。
即 node1->head1 = node8 , 而 node8->head2 = node1 ; 这种表示方法，在本文所描述的代码中并没有任何的特点，
但是用于实际的计算来讲，是十分有用的。
#include <cstdio>
#include <string>
#define MAX 100
struct arcnode
{
int adjvex ;
arcnode *next ;
arcnode () {}
arcnode ( int adjvex) : adjvex( adjvex) ,next( NULL) {}
} ;
struct vnode
{
int id ;
arcnode *head1 ;
arcnode *head2 ;
vnode () {}
vnode ( int id ) : id(id ) , head1(NULL),head2(NULL) {}
};
struct Graph
{
vnode nodes[MAX] ;
int vexnum , arcnum ;
Graph(){}
Graph( int vexnum , int arcmum ) : vexnum(vexnum) ,arcnum( arcnum ) {}
void setGraph( int vex , int arc )
{
vexnum = vex ;
arcnum = arc ;
for ( int i = 0 ; i < vex ; i++ )
{
nodes[i].id = i ;
nodes[i].head1= nodes[i].head2= NULL ;
}
}
};
Graph graph;
int visited[MAX] ;
void createGraph()
{
arcnode *p ;
int vex, arc ;
int from , to ;
printf("vertex num , arc num \n") ;
scanf("%d%d" , &vex, &arc) ;
for ( int i = 0 ; i < vex ; i++ )
visited[i] = 0 ;
graph.setGraph( vex, arc ) ;
for ( int i = 0 ; i < arc ; i++ )
{
printf("from to \n") ;
scanf("%d%d", &from , &to ) ;
//set the from
p = new arcnode( to) ;
p->adjvex = to ;
p->next = graph.nodes[from].head1 ;
graph.nodes[from].head1= p ;
//set the to
p = new arcnode( from ) ;
p->adjvex = from ;
p->next = graph.nodes[to].head2 ;
graph.nodes[to].head2 = p ;
}
}
void DFS ( int i )
{
visited[i] = 1 ;
arcnode *p = graph.nodes[i].head1;
while ( p )
{
if ( !visited[p->adjvex ] )
{
printf("now we are at vertex %d and going to visit %d\n", i , p->adjvex );
DFS ( p->adjvex) ;
printf("now we are return from dfs %d\n", p->adjvex ) ;
}
p = p->next ;
}
}
int main ( void )
{
int start ;
createGraph() ;
printf("printf from where to start ? ") ;
scanf("%d", &start );
DFS ( start ) ;
system("pause") ;
return 0 ;
}
b. 邻接矩阵的深度优先搜索代码实现
#include <cstdio>
#include <string>
/**
dfs template
matrix
*/
#define MAX 100
int map[MAX][MAX] ,visited[MAX] ;
int path [MAX] , verNum , arcNum ;
void dfs ( int p )
{
visited[p] = 1 ;
for ( int i = 0 ; i < verNum ; i++ )
{
if ( map[i+1][p] == 1 && !visited[i+1] )
{
printf("we are going to visit vertex : %d\n", i+1) ;
dfs( i+1 ) ;
printf("this is after we visit vertex : %d\n" , i+1) ;
}
}
}
void createGraph()
{
int from , to ;
memset( map , -1 , sizeof( map ) ) ;
printf("vertex num , arc num \n") ;
scanf("%d%d" , &verNum , &arcNum) ;
for ( int i = 1 ; i <= verNum ; i++ )
visited[i] = 0 ; //0 means vertex i not visited
for ( int i = 0 ; i < arcNum ; i++ )
{
printf("insert from to \n") ;
scanf("%d%d", &from , &to) ;
map[from][to] = 1 ;
map[to][from] = 1 ;
}
}
int main ( void )
{
int n ;
createGraph() ;
printf("which vertex start ?\n") ;
scanf("%d", &n ) ;
dfs( n ) ;
system("pause") ;
return 0 ;
}
| 
转播
