DFS深度优先搜索与BFS广度优先搜索

1、二者区别

DFS会先搜到最深，然后退一下在深搜，再退再搜。

BFS会一层一层的搜

两者比较

DFS只用存一条路上的点，储存空间与高度有关，BFS存一层的点。

BFS第一个搜到符合条件的数一定离起点最近，具有最短路的性质。但仅限于所有边长相等时

2、问题

1、DFS模板：题目：842.排列数字

1.思路

2.代码模板：

#include<iostream>

using namespace std;

const int N=10;

int n;
int path[N];		//记录当前路径上的数 
bool st[N];			//记录每个数字的状态，1就代表这个数字用过了 

void dfs(int u)
{
	if(u==n)		//每一层是一个位置，当走到第n个位置时结束 
	{
		for(int i=0;i<n;i++)
			printf("%d ",path[i]);
		printf("\n"); 
		return ;
	}
	for(int i=1;i<=n;i++)		//枚举数字 
	{
		if(!st[i])				//当前数字没被用过时 
		{
			path[u]=i;			//当前位就放这个数字
			st[i]=true;			//将这个数字标记用过了
			dfs(u+1);			//递归下一位 
			st[i]=false;		//用完要恢复现场，方便下一次用 	 
		}	
	} 
}
int main()
{
	cin>>n;
	dfs(0);
	return 0;
}

3.题目

2、DFS：n皇后问题

1、思路

第一种：与上一题差距不大，直接全排列找出答案

第二种：但是要注意剪枝，只要不符合直接下一个。

2、代码模板

第一种

#include<iostream>

using namespace std;

const int N=20;

int n;
char g[N][N];		//记录当前的方案，即棋子的摆放 
bool col[N],dg[N],udg[N];//记录每个数字的状态，1就代表这个数字用过了 
						 //col代表列，dg正对角线，udg反对角线 
void dfs(int u)			//第u行 
{
	if(u==n)		//每一层是一个位置，当走到第n个位置时结束 
	{
		for(int i=0;i<n;i++)
			puts(g[i]); 
		put("");
		return ;
	}
	for(int i=0;i<n;i++)		//从第一列开始枚举 
	{
		if(!col[i]&&!dg[u+i]&&!udg[n-u+i])//当前i列没有用过，u+i的正对角线上没有，n-u+i反对角线上没有
		{
			g[u][i]='Q';			//当前位就放这个数字
			col[i]=dg[u+i]=udg[n-u+i]=true;	//将这一列和正反对角线上标记用过了 
			dfs(u+1);			//递归下一位
			g[u][i]='.';		//用完要恢复现场，方便下一次用 	
			col[i]=dg[u+i]=udg[n-u+i]=false;		 
		}	
	} 
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			g[i][j]='.';
	dfs(0);
	return 0;
}

第二种,一个格子一个格子的判断

#include<iostream>

using namespace std;

const int N=20;

int n;
char g[N][N];		//记录当前的方案，即棋子的摆放 
bool rox[N],col[N],dg[N],udg[N];//记录每个数字的状态，1就代表这个数字用过了 
						 //rox代表行,col代表列，dg正对角线，udg反对角线 
void dfs(int x,int y,int z)	//x是行,y是列，s是皇后个数 
{
	if(y==n)	//当一行枚举完后，换到下一行第一个位置 
	{
		y=0;
		x++;	
	} 
	if(x==n)	//当到最后一行时 
	{
		if(s==n)
		{
			for(int i=0;i<n;i++)
				puts(g[i]);
			puts("");
		}
		return ;
	}
	dfs(x,y+1,s);	//不放皇后，递归到下一个格子
	//放皇后的话先判断是否可以放 
	if(!rox[x]&&!col[y]&&!dg[x+y]&&!udg[x-y+n])
	{
		g[x][y]='Q';
		rox[x]=col[y]=dg[x+y]=udg[x-y+n]=true;//记录皇后位置
		dfs(x,y+1,s+1); //递归到下一层
		rox[x]=col[y]=dg[x+y]=udg[x-y+n]=false;//恢复现场
		g[x][y]='.';
	} 
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			g[i][j]='.';
	dfs(0);
	return 0;
}

3、题目

3、BFS模板：844走迷宫

1、思路

根据队列的特性，每次用这一层的点寻找下一层的所有点，然后将这一层的点出队，下一层的点入队。

2、代码模板

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef pair<int,int> PII; 

const int N=110;

int n,m;
int g[N][N];				//存地图 
int d[N][N];				//存当前点到起点的距离 
PII q[N*N];					//手写队列 
int bfs()
{
	int hh=0,tt=0;			//hh是队头，tt是队尾
	q[0]={0,0};				//起点0，0
	memset(d,-1,sizeof d);	//将距离初始化为-1代表没有走过
	d[0][0]=0;				//起点走过了
	int dx[4]={-1,0,1,0};
	int dy[4]={0,1,0,-1};
	while(hh<=tt)
	{
		PII t=q[hh++];			//t存储当前队头,tt++让队头出队 
		for(int i=0;i<4;i++)	//进行上下左右移动 
		{
			int x=t.first+dx[i];
			int y=t.second+dy[i];
			if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)//移动后在边界里，且没有走过
			{
				d[x][y]=d[t.first][t.second]+1;//当前点到起点的距离等于前一个点+1 
				q[++tt]={x,y};			//让新点入队 
			} 	
		}	
	} 
	return d[n-1][m-1];				//返回终点的d，即终点到起点的最短距离 
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)	//输入整个地图 
		for(int j=0;j<m;j++)
			cin>>g[i][j];
	cout<<bfs()<<endl; 
	return 0;
}

如果要输出路径

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

typedef pair<int,int> PII; 

const int N=110;

int n,m;
int g[N][N];				//存地图 
int d[N][N];				//存当前点到起点的距离 
PII q[N*N],pre[N][N];					//手写队列 

int bfs()
{
	int hh=0,tt=0;			//hh是队头，tt是队尾
	q[0]={0,0};				//起点0，0
	memset(d,-1,sizeof d);	//将距离初始化为-1代表没有走过
	d[0][0]=0;				//起点走过了
	int dx[4]={-1,0,1,0};
	int dy[4]={0,1,0,-1};
	while(hh<=tt)
	{
		PII t=q[hh++];			//t存储当前队头,tt++让队头出队 
		for(int i=0;i<4;i++)	//进行上下左右移动 
		{
			int x=t.first+dx[i];
			int y=t.second+dy[i];
			if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]==0&&d[x][y]==-1)//移动后在边界里，且没有走过
			{
                pre[x][y]=t;            //如果要输出路径的话，记录一下前一个点是谁
				d[x][y]=d[t.first][t.second]+1;//当前点到起点的距离等于前一个点+1 
				q[++tt]={x,y};			//让新点入队 
			} 	
		}	
	} 
    int x=n-1,y=m-1;
    while(x||y)
    {
        cout<<x<<" "<<y<<endl;
        PII t=pre[x][y];
        x=t.first;
        y=t,second;
    }
	return d[n-1][m-1];				//返回终点的d，即终点到起点的最短距离 
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<n;i++)	//输入整个地图 
		for(int j=0;j<m;j++)
			cin>>g[i][j];
	cout<<bfs()<<endl; 
	return 0;
}