理解数据结构——图的DFS和BFS

理解数据结构——图的DFS和BFS

在图算法和搜索算法中，dfs和bfs是常见的两种遍历方式。且二者常常千变万化，出现于各类题型，如最短路径、树形dp中，那么我们该如何理解这两种算法思想呢。 1.DFS 深度优先搜索 顾名思义，即当我们对某个树or图进行搜索时，一条道走到黑，“不撞南墙不回头”。dfs总是沿着某个最深的方向来进行搜索，直到无路可走。 假设有下面这么一个树形结构（此处用树型结构，是为了初学者更好地理解这一过程。而且树也可看做一种特殊的有向无环图，应用到图中也是如此）， 那么，运用dfs对进行搜索的顺序是什么样的呢： ABECFGHD 很明显，即从每一 个顶点开始，访问其含有边的节点，直至没有通路；当没有通路后，便回溯到上一层顶点，继续访问没有访问过的节点。 请注意这个回溯，这是dfs中的一个关键。为了便于理解，先上相关代码： 首先先定义一个图，此处依旧是用大家（本蒟蒻）最喜闻乐见的邻接矩阵来表示图及其连通性：

const int MaxVnum=100;//顶点最大个数 
typedef char VexType;//顶点的数据类型 
typedef int EdgeType;//顶点的边权；若不带权值则用0和1表示其连通性 
typedef struct {
          
   
	VexType Vex[MaxVnum];//顶点信息 
	EdgeType Edge[MaxVnum][MaxVnum];//邻接矩阵 
	int vexnum,edgenum; //顶点数和边数 
}Gragh;

然后来看一下dfs的代码

void dfs(Gragh G,int v){
          
   //假设已经创建了一个图的邻接矩阵G ，v是开始访问的顶点 
	int w;//w是邻接点 
	cout<<G.vexnum[v]<<"	";
	for(w=0;w<G.edgenum;w++){
          
   //遍历所有顶点
	     visist[v]=true;//访问过了标记为真 
	     if(G.Edge[v][w]&&!visist[w]) dfs(G,w);//邻接且未被访问过，则递归访问其邻接点
    }
}

前面提到了回溯，注意一下visist[]这个数组，其作用正是用来记录是否访问过，并作为回溯的依据。即回溯之后，又从哪里继续开始 以上便是dfs的基本思路，接下来我们来bfs。 2.BFS 广度优先搜索 如果说dfs是走迷宫，一条道走到黑，那么BFS可以理解为： 你突然发现钱掉了，你该怎么找——肯定是从离自己目前最近的范围内开始寻找，之后慢慢扩大到自己所经过的地方啊！ 这便是BFS的实现思路——从最近地方开始，范围慢慢扩大 我们仍然以之前的那棵树距离，那么我们的遍历是怎样的呢： ABCDEFGH 即我们对于每一个顶点，总是先从它的邻接顶点开始访问，直至把其邻接点都访问了，再递归地访问邻接顶点的顶点。 相比起dfs的实现过程，bfs稍稍复杂了一点：需要借助一个数据结构——队列（Queue）来实现。 先来看代码，图的表示方法仍然沿用邻接矩阵 （此处用到了C++中的queue模板，C语言的话还需自己造轮子哈）

void bfs(Gragh G,int v){
          
   
	int u,v;
	queue<int>Q;
	cout<<G.vexnum[v]<<"	";
	visist[v]=true;
	Q.push(v);//顶点v入队
	while(Q.empty()){
          
   //如果队列不空 
	u=Q.front();//队列的头元素出列赋给u
	Q.pop();//队列头元素出队
	for(w=0;w<G.edgenum;w++){
          
   
		if(G.Edge[u][w]&&!visist[w]){
          
   //u，w邻接且w未被访问过 
		cout<<G.Vex[w]<<"	";
		visist[v]=true;
		Q.push(w);//领接点加入队列
		} 
	} 
	} 
}