欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析

程序员文章站 2022-07-14 14:14:09
...

图的遍历是指从图中某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次，且仅访问一次。图的遍历常见算法有BFS和DFS。

文章目录

（一）深度优先搜索DFS

1、基本思路

    DFS 用于找所有解的问题，它的空间效率高，但是找到的不一定是最优解，必须记录并完成整个搜索，故一般情况下，深搜需要非常高效的剪枝。DFS类似于树的先序遍历，搜索策略为尽可能“深”的搜索一个图。首先访问图中某一起始顶点v,然后由v出发，访问与v邻接且未被访问的任一顶点w1,再访问与w1邻接且未被访问的任意顶点w2,…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，知道图中所有顶点均被访问过为止。程序伪代码如下：

bool visited[MAX_VERTEX_NUM];//访问标记数组
void DFSTraverse(Graph G){
	//对图G进行深度优先遍历，访问函数为visit()
	for(v=0;v<G.vexnum,++v){//本代码中是从v=0开始遍历
		if(!visited[v])
			DFS(G,v);
	}
}
void DFS(Graph G,int v){
	//从顶点v出发，采用递归思想，深度优先遍历图G
	visit(v);
	visited[v]=true;
	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
		if(!visited[w]){//w为u的尚未访问的邻接顶点
			DFS(G,w);
		}
}
2、图示

可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析

3、算法性能分析

   DFS算法是一个递归算法，需要借助一个递归工作栈，故它的空间复杂度为O(|V|)。遍历图的过程实质上是对每个顶点查找其邻接点的过程，其耗费的时间取决于所采用的存储结构。当以邻接矩阵表示时，查找每个顶点的邻接点所需时间为O(|V|)，故总的时间复杂度为O(|V*V|)。当以邻接表表示时，查找所有顶点的邻接点所需时间为O(|E|)，访问顶点所需时间为O(|V|)，此时，总的时间复杂度为O(|V|+|E|)。

4、深度优先遍历的非递归写法

在深度优先搜索的非递归算法中使用一个栈S，用来记忆下一步可能访问的顶点，同时使用了一个访问标记数组visited[i]，在visited[i]中记忆第i个顶点是否在站内或者曾经在栈内。若是，以后他不能再进栈。图采用邻接表方式，伪代码如下所示：

void DFS_Non_Rc(AGraph& G,int v){
	//从顶点v开始进行深度优先搜索，一次遍历一个连通分量的所有顶点
	int w;//顶点序号
	InitStack(S);//初始化栈S
	for(i=0;i<G.vexnum;i++)
		visited[i]=false;//初始化visited[]
	Push(S,v);
	visited[v]=true;//v入栈，并置visited[v]
	while(!IsEmpty(S)){
		k=Pop(S);//出栈
		visit（k）;//先访问，再将其子结点入栈
		for(w=FirstNeighbor(G,k);w>=0;w=NextNeighbor(G,k,w))
			if(!visited[w]){//未进过栈的顶点进栈
				Push(S,w);
				visited[w]=true;//作标记，以免再次入栈	
		 }//end if
	}//end while
}

（二）广度优先遍历BFS

1、基本思想

    BFS 常用于找单一的最短路线，它的特点是 “搜到就是最优解”，类似于二叉树的层序遍历算法，它的基本思想是：首先访问起始顶点v，接着由v出发，依次访问v的各个未访问过的邻接顶点w1,w2,w3,…wi，然后再依次访问w1,w2,…,wi的所有未被访问过的邻接顶点…依次类推，直到图中所有顶点都被访问过为止。类似的思想还将应用于Dijkstra单源最短路径算法和Prim最小生成树算法。其实现借助于一个辅助队列。伪代码如下所示：

bool visited[MAX_BERTEX_NUM];//访问标记数组
void BFSTraverse(Graph G){
	//对图G进行广度优先遍历，设访问函数为visit()
	for(i=0;i<G.vexnum,++i)
		visited[i]=FALSE;
	InitQueue(Q);
	for(i=0;i<G.vexnum;++i)//从0号顶点开始遍历
		if(!visited[i])
			BFS(G,i);//vi未访问过，从vi开始BFS
}
void BFS(Graph G,int v){
	//从顶点v出发，广度优先遍历图G，算法借助一个辅助队列Q
	visit(v);//访问初始顶点v
	visited[v]=true;
	Enqueue(Q,v);//顶点v入队列
	while(!isEmpty(Q)){
		DeQueue(Q,v);//顶点v出队列
		for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
		//检测v所有邻接点
		if(!visited[w]){//w为v的尚未访问的邻接顶点
			visit(w);//访问顶点w
			visited[w]=true;//对w做已访问标记
			EnQueue(Q,w);//顶点w入队列
		}
	}
}
2、图示

可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析

3、算法性能分析

   无论是使用邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q,n个顶点均需入队一次，在最坏的情况下，空间复杂度为O(|V|)。
   当采用邻接表存储方式时，每个顶点均需搜索一次（或入队一次），故时间复杂度为O(|V|),在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为O(|E|)，算法总时间复杂度为O(|V|+|E|)。当采用邻接矩阵存储方式时，查找每个顶点的邻接表所需时间为O(|V|)，故算法总时间复杂度为O(|V|^2)。

4、应用—BFS算法求解非带权图单源最短路径问题
void BFS_MIN_Distance(Graph G,int u){
	//d[i]表示从u到i结点的最短路径
	for(i=0;i<G.vexunm;i++)
		d[i]=∞;//初始化路径长度
		visited[u]=true;
		d[u]=0;
		EnQueue(Q,u);
		while(!isEmpty(Q)){
		DeQueue(Q,u);//队头元素u出队
		for(w=FirstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w))
			if(!visited[w]){
			//w为u尚未访问的邻接顶点
			visited[w]=true;
			d[w]=d[u]+1;//路径长度+1
			EnQueue(Q,w);//顶点w入队
		}//if
	}//while
}

（三）经典算法题目分析

1.Red and Black

There is a rectangular room, covered with square tiles. Each tile is colored either red or black. A man is standing on a black tile. From a tile, he can move to one of four adjacent tiles. But he can’t move on red tiles, he can move only on black tiles.
Write a program to count the number of black tiles which he can reach by repeating the moves described above.

  • Input:

The input consists of multiple data sets. A data set starts with a line containing two positive integers W and H; W and H are the numbers of tiles in the x- and y- directions, respectively. W and H are not more than 20.
There are H more lines in the data set, each of which includes W characters. Each character represents the color of a tile as follows.
‘.’ - a black tile
‘#’ - a red tile
‘@’ - a man on a black tile(appears exactly once in a data set)
The end of the input is indicated by a line consisting of two zeros.

  • Output:

For each data set, your program should output a line which contains the number of tiles he can reach from the initial tile (including itself).

  • SampleInput:

6 9
…#.
…#
…
…
…
…
…
#@…#
.#…#.
11 9
.#…
.#.#######.
.#.#…#.
.#.#.###.#.
.#.#…@#.#.
.#.#####.#.
.#…#.
.#########.
…
11 6
…#…#…#…
…#…#…#…
…#…#…###
…#…#…#@.
…#…#…#…
…#…#…#…
7 7
…#.#…
…#.#…
###.###
…@…
###.###
…#.#…
…#.#…
0 0

  • Sample Output

45
59
6
13

题目大意：题意：给你一张图，图上有黑色，红色两种方块，人只能走黑色块，问你
人最多能走多少个黑色块
输入：
w、h代表图的宽度高度，再给出图
@代表人的位置，#代表红色，.代表黑色

可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析
该题主要是用bfs/dfs求最优路径，属于暴力搜索，上图是分别使用dfs和bfs算法走的路径示意图，下面是两种方法代码

/**
		使用DFS算法进行搜索最优
*/
#include <iostream>
#include<cstring>
#include<algorithm> 
using namespace std;
int vis[25][25];//标记是否走过 
char map[25][25];//走的图 
int to[4][2]={0,1,0,-1,1,0,-1,0};//相邻位置
int ans;//记录结果
int w,h;
void dfs(int x,int y){
	if(vis[x][y]) return ;//已经访问过，则不访问 
	if(map[x][y]=='#') return;//若为#则不访问
	vis[x][y]=1;//标记已访问
	ans++;//步数+1
	for(int i=0;i<4;i++){
		int xx=x+to[i][0];
		int yy=y+to[i][1];
		if(!vis[xx][yy]&&map[xx][yy]!='#'){//未访问或者不为'#'
		//在范围内 
			if(xx>=1&&xx<=h&&yy>=1&&yy<=w){
				dfs(xx,yy);
			}
		}
	} 
	
} 
int main(int argc, char** argv) {
	int x,y;
	while(~scanf("%d%d",&w,&h)&&w+h){
		ans=0;
		memset(vis,0,sizeof(vis));
		for(int i=1;i<=h;i++){
			scanf("%s",map[i]+1);
			for(int j=1;j<=w;j++){
				if(map[i][j]=='@'){
					x=i;
					y=j;
				}
			}
		}
		dfs(x,y);
		printf("%d\n",ans);
	} 
	return 0;
}

/**
		使用BFS算法进行搜索最优
*/
 #include<iostream>
 #include<algorithm>
 #include<cstring>
 #include<queue>
 using namespace std;
 int vis[25][25];
 char map[25][25];
 int to[4][2]={0,1,0,-1,1,0,-1,0};//相邻位置
 int ans;
 int w,h;
 struct node{
 	int x,y;
 };
 //
 queue<node> q;//需要用到队列 
 void bfs(int sx,int sy){
 	//若队列不为空，则出队 ，为了保证队此时为空 
 	while(!q.empty()){
 		q.pop();
	 }
	 node a;
	 a.x=sx;
	 a.y=sy;
	 //入队 
	 q.push(a);
	 //置为已经访问过 
	 vis[sx][sy]=1;
	 ans++;//步数++ 
	 while(!q.empty()){
	 	//取队首元素
		 node cur=q.front();
		 q.pop();//出队 
		 //在四个方向逐层进行搜索 
		 for(int i=0;i<4;i++){
		 	int xx=cur.x+to[i][0];
		 	int yy=cur.y+to[i][1];
		 	//若超出了范围，则跳过 
		 	if(xx<1||yy<1||xx>h||yy>w){
		 		continue;
			 }
			 //若已经访问过 
			if(vis[xx][yy]){
				continue;
			}
			//若为'#'代表此路不通 
			if(map[xx][yy]=='#'){
			  continue; 
			}
			vis[xx][yy]=1;
			ans++;
			node b;
			b.x=xx;
			b.y=yy;
			q.push(b);
		 } 
	 }
 } 
 int main(){
 	int x,y;
 	while(~scanf("%d%d",&w,&h)&&w+h){
 		ans=0;
 		memset(vis,0,sizeof(vis));
 		for(int i=1;i<=h;i++){
 			//+1跳过'\0' 
 			scanf("%s",map[i]+1);
 			//printf("%s\n",map[i]+1); 
 			for(int j=1;j<=w;j++){
 				//获得初始位置 
 				if(map[i][j]=='@'){
 					x=i;
 					y=j;
				 }
			 }
		 }
		 bfs(x,y);
		 printf("%d\n",ans);
	 }
 	return 0;
 }
2、最优配餐问题
  • 题目描述

栋栋最近开了一家餐饮连锁店，提供外卖服务。随着连锁店越来越多，怎么合理的给客户送餐成为了一个急需解决的问题。
    栋栋的连锁店所在的区域可以看成是一个n×n的方格图（如下图所示），方格的格点上的位置上可能包含栋栋的分店（绿色标注）或者客户（蓝色标注），有一些格点是不能经过的（红色标注）。
   方格图中的线表示可以行走的道路，相邻两个格点的距离为1。栋栋要送餐必须走可以行走的道路，而且不能经过红色标注的点。
   送餐的主要成本体现在路上所花的时间，每一份餐每走一个单位的距离需要花费1块钱。每个客户的需求都可以由栋栋的任意分店配送，每个分店没有配送总量的限制。
   现在你得到了栋栋的客户的需求，请问在最优的送餐方式下，送这些餐需要花费多大的成本。

可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析

  • 输入格式

输入的第一行包含四个整数n, m, k, d，分别表示方格图的大小、栋栋的分店数量、客户的数量，以及不能经过的点的数量。
    接下来m行，每行两个整数xi, yi，表示栋栋的一个分店在方格图中的横坐标和纵坐标。
    接下来k行，每行三个整数xi, yi, ci，分别表示每个客户在方格图中的横坐标、纵坐标和订餐的量。（注意，可能有多个客户在方格图中的同一个位置）
    接下来d行，每行两个整数，分别表示每个不能经过的点的横坐标和纵坐标。

  • 输出格式

输出一个整数，表示最优送餐方式下所需要花费的成本。

  • 样例输入

10 2 3 3
1 1
8 8
1 5 1
2 3 3
6 7 2
1 2
2 2
6 8

  • 样例输出

29

该题与上一道题的不同之处在于：上一道为单源求最优，本道题是多源（一至多个分店）求最优，使用BFS实现最佳

#include<iostream> 
#include<cstring>
#include<queue>
using namespace std;
 const int N=1000;
 const int TRUE=1;
 const int DIRECTSIZE=4;
 //定义方向结构体
 struct direct{
 	int drow,dcol;
	  
 }direct[DIRECTSIZE]={{-1,0},{1,0},{0,-1},{0,1}} ;
 int buyer[N+1][N+1];//存储顾客所在位置
 int visited[N+1][N+1];//标记是否访问过
 struct node{
 int row,col,step;
 node(){
 
 }
 //自家分店构造函数 
 node(int r,int c,int s){
 	row=r;
 	col=c;
 	step=s;
 } 
}; 
queue<node> q;
int count=0;//订餐点总数
long long ans=0; 
//多源点进行遍历 
 void bfs(int n){
 	node front,v;
 	while(!q.empty()){
 		//首先将队首出队,从第一家店开始搜索 
 		front=q.front();
 		q.pop();
 		for(int i=0;i<DIRECTSIZE;i++){
 			//移动一格
			 v.row=front.row+direct[i].drow;
			 v.col=front.col+direct[i].dcol;
			 //步数加1
			 v.step=front.step+1;
			 //若行列越界，则跳过
			 if(v.row<1||v.row>n||v.col<1||v.col>n) continue;
			 if(visited[v.row][v.col]) continue;
			 //如果是订餐点，则计算成本并且累加
			 if(buyer[v.row][v.col]>0){
			 	visited[v.row][v.col]=1;
			 	//点一个餐送一个人，有可能这些顾客在一个点 
			 	ans+=buyer[v.row][v.col]*v.step;
			 	//若已经遍历完所有买家，则return 
			 	if(--count==0){
			 		return ;
				 }
			 }
			 //向前继续搜索
			 visited[v.row][v.col]=1;
			 q.push(v);//将v加入队尾，表示已经访问过 
		 } 
    }
 	
 }
 /**
    	先将所有的餐厅信息（坐标以及步数）入队，
	 在遍历一个店铺之后就会将扩展的上右下左四个方向入队，
	 直到最后一个餐厅结束，就完成了所有店铺的扩展。
	以此类推，将每一个点都要遍历一下。每到达客户的地点，就会计算相应的费用。
 */ 
 int main(){
 	int m,k,d,x,y,c;
 	memset(buyer,0,sizeof(buyer));
 	memset(visited,0,sizeof(visited));
 	//输入数据
	 cin>>n>>m>>k>>d;
	 for(int i=1;i<=m;i++){
	 	cin>>x>>y;
	 	//将各个分店加入队列中
		 q.push(node(x,y,0)) ;
		 visited[x][y]=true;
	 }
	 for(int i=0;i<k;i++){
	 	cin>>x>>y;
	 	cin>>c;
	 	//统计客户所在地点数量（多个客户可能在同一地点） 
	 	if(buyer[x][y]==0){
	 		count++;//客户所在地点数量 
		 }
		 buyer[x][y]+=c;//统计某个地点的订单数量 
	 }
	 //将不能经过的坐标置为true 
	 for(int i=0;i<d;i++){
	 	cin>>x>>y;
	 	visited[x][y]=true;
	 } 
	 //广度优先搜索
	 bfs(n);
	 cout<<ans<<endl; 
 	return 0;
 }
3、CCF201604-4 游戏
  • 问题描述

 小明在玩一个电脑游戏，游戏在一个n×m的方格图上进行，小明控制的角色开始的时候站在第一行第一列，目标是前往第n行第m列。
 方格图上有一些方格是始终安全的，有一些在一段时间是危险的，如果小明控制的角色到达一个方格的时候方格是危险的，则小明输掉了游戏，如果小明的角色到达了第n行第m列，则小明过关。第一行第一列和第n行第m列永远都是安全的。
 每个单位时间，小明的角色必须向上下左右四个方向相邻的方格中的一个移动一格。
 经过很多次尝试，小明掌握了方格图的安全和危险的规律：每一个方格出现危险的时间一定是连续的。并且，小明还掌握了每个方格在哪段时间是危险的。
 现在，小明想知道，自己最快经过几个时间单位可以达到第n行第m列过关。

  • 输入格式

  输入的第一行包含三个整数n, m, t，用一个空格分隔，表示方格图的行数n、列数m，以及方格图中有危险的方格数量。
  接下来t行，每行4个整数r, c, a, b，表示第r行第c列的方格在第a个时刻到第b个时刻之间是危险的，包括a和b。游戏开始时的时刻为0。输入数据保证r和c不同时为1，而且当r为n时c不为m。一个方格只有一段时间是危险的（或者说不会出现两行拥有相同的r和c）。

  • 输出格式

输出一个整数，表示小明最快经过几个时间单位可以过关。输入数据保证小明一定可以过关。

  • 样例输入

3 3 3
2 1 1 1
1 3 2 10
2 2 2 10

  • 样例输出

6

  • 样例说明

   第2行第1列时刻1是危险的，因此第一步必须走到第1行第2列。
　　第二步可以走到第1行第1列，第三步走到第2行第1列，后面经过第3行第1列、第3行第2列到达第3行第3列。

  • 评测用例规模与约定

  前30%的评测用例满足：0 < n, m ≤ 10，0 ≤ t < 99。
  所有评测用例满足：0 < n, m ≤ 100，0 ≤ t < 9999，1 ≤ r ≤ n，1 ≤ c ≤ m，0 ≤ a ≤ b ≤ 100。

  • 问题分析
    本题需要一个三维的标志来避免重复搜索。除了行列坐标外，需要考虑时间问题，故将其设置为三维数组。因为一些格在某个时间范围是危险的，不可进入，但是这个时间范围之外，是可以随意进入的。所以有时候需要在一些地方踱步，等过了这段时间再前行，就不能简单地限制为进入过的格不能再进入。 
#include<iostream> 
#include<cstring>
#include<queue>
using namespace std;
const int N=100;
const int DIRECTSIZE=4;
struct direct{
	int drow,dcol;
	
}direct[DIRECTSIZE]={{-1,0},{1,0},{0,-1},{0,1}};
//需要定义个三维数组，第三维存储在这个时间是否可以通过
int visited[N+1][N+1][300+1];
struct node{
	int row,col;
	int level;
}; 
int bfs(int n,int m){
	
	node start,front,v;
	//从第一行第一列开始走 
	start.row=1;
	start.col=1;
	start.level=0;
	queue<node> q;
	q.push(start);
	while(!q.empty()){
		front=q.front();
		q.pop();
	    //设置出口 
		//到达终点则结束
		if(front.row==n&&front.col==m) return front.level; 
		for(int i=0;i<DIRECTSIZE;i++){
			//四个方向各向前走一步
			v.row=front.row+direct[i].drow;
			v.col=front.col+direct[i].dcol;
			v.level=front.level+1;
			//行界越界则跳过
			if(v.row<1||v.row>n||v.col<1||v.col>m){
				continue;
			}
			//已经访问过的点无法再次访问
			if(visited[v.row][v.col][v.level]) continue;
			//向前搜索：标记v点为已经访问过，v点加入队列中
			visited[v.row][v.col][v.level]=1;
			q.push(v); 
		} 
	}
	return 0;
}
int main(){
	int n,m,t,r,c,a,b;
	memset(visited,0,sizeof(visited));
	cin>>n>>m>>t;
	for(int i=1;i<=t;i++){
		cin>>r>>c>>a>>b;
		//设置方格危险时间，使之那些时间不可进入
		for(int j=a;j<=b;j++){
			visited[r][c][j]=1;
		}
		
	}
	int ans=bfs(n,m);
	cout<<ans<<endl; 
	return 0;
}

（四）参考文献

【1】2018年数据结构考研复习指导. 王道论坛组编.
【2】https://www.cnblogs.com/kungfupanda/p/11248014.html
【3】https://vjudge.net/problem/POJ-1979
【4】参考视频 https://www.bilibili.com/video/av78091226?from=search&seid=16502200292163627678
【5】https://blog.csdn.net/tigerisland45/article/details/54934916

相关标签： 算法题目

上一篇： 第七周练习（J）

下一篇： 机器学习-随机森林(Random Forest)

推荐阅读