c++：DFS与BFS详解_dfs和bfs c++

DFS（深度优先搜索）：从某个状态开始，不断转移状态到无法转移为止，然后退回到前一步，继续转移到其他状态，不断重复，直至找到最终的解。

         总是从最开始的状态出发，遍历所有的可到达状态。隐式利用栈进行计算

eg：有一个N*M的田，雨后积水，八连通（下图相对w的*部分）的积水被认为连在一起，请给出园里有多少水洼？

      ***

      *w*

      ***

  input ：3 3  

***

*w*

w**

 output: 1

  解析：从任意w开始，不停把w邻接部分用*代替，复杂度O（N*M）

int n, m;
char field[max_n][max_m+1];
 
//现在的位置
void dfs(int x, int y)
{
	field[x][y] = '*';
	for (int dx = -1; dx <= 1; dx++)
	{
		for (int dy = -1; dy <= 1; dy++)
		{
			int nx = x + dx, ny = y + dy;
			if (0 < nx&&nx < n && 0 < ny&&ny < m&&field[nx][ny] == 'W')
				dfs(nx, ny);
 
		}
	}
	return ;
}
 
void solve()
{
	int count = 0;
	for (int i = 0; i < n; i++)
	for (int j = 0; j < m; j++)
	if (field[n][m] == 'W')
	{
		dfs(i, j);
		count++;
	}
	printf("d%\n", count);
}

BFS(宽度优先搜索）总是先搜索距离初始状态近的状态，利用队列进行运算。复杂度O(状态数*转移的方式）

给定一个大小为N*M的迷宫，由通道('.')和墙壁('#')组成，其中通道S表示起点，通道G表示终点，每一步移动可以达到上下左右中不是墙壁的位置。试求出起点到终点的最小步数。（本题假定迷宫是有解的）(N,M<=100)

样例输入：

10 10

样例输出：

22

解析：bfs中，对于已经访问过得状态用标记管理，本例用INF标记，并初始化d数组，这样到达终点就会终止搜索，可如果一直下去直到队列为空，就可以计算出各个地点的

最 短距离。

#include <iostream>
#include <queue>
using namespace std;
const int MAX_N = 100;
const int MAX_M = 100;
const int INF = 0x3f3f3f3f;

//用pair表示状态时，用typedef更方便一些

typedef pair<int, int> P;

char maze[MAX_N][MAX_M + 1];
int N, M;
int sx, sy; //起点的位置
int gx, gy; //终点的位置
 
int d[MAX_N][MAX_M];//储存起点到某一点的距离
int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; //表明每次x和y方向的位移
 
void bfs()
{
	queue<P> que;
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			d[i][j] = INF;	//初始化所有点的距离为INF
	que.push(P(sx, sy));
	d[sx][sy] = 0;	//从起点出发将距离设为0，并放入队列首端
 
	while (que.size()) //题目保证有路到终点，所以不用担心死循环
	{
		P p = que.front(); que.pop();//弹出队首元素
		int i;
		for (i = 0; i < 4; i++)
		{
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];//移动后的坐标
			//判断可移动且没到过
			if (0 <= nx&&nx < N
				&& 0 <= ny&&ny < M
				&&maze[nx][ny] != '#'
				&&d[nx][ny] == INF)//之前到过的话不用考虑，因为距离在队列中递增，肯定不会获得更好的解
			{
				que.push(P(nx, ny));	//可以移动则设定距离为之前加一，放入队列
				d[nx][ny] = d[p.first][p.second] + 1;
				if(nx==gx && ny==gy) break;
 
                        }
		}
		if(i!=4) break;
	}
 
}
 
int main()
{
	cin>>N>>M;
	for (int i = 0; i < N; i++)
		cin>>maze[i];
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
		{
			if (maze[i][j] == 'S')
			{
				sx = i; sy = j;
			}
			if (maze[i][j] == 'G')
			{
				gx = i; gy = j;
			}
		}
	bfs();
	cout<<d[gx][gy]<<endl;
 
	return 0;
}

总结：bfs与dfs两种都能生成所有遍历状态，但是要求对所有状态进行处理时使用dfs比较方便；在求最短路径用bfs比较好。