深度优先搜索（DFS）和广度优先搜索（BFS）

先说DFS：

  DFS是搜索的一种手段之一。他从某个状态开始，不断地转移状态，直到无法转移状态，然后回退到前一步的状态，继续转移到其他状态，如此不断重复，直到找到最终的解。DFS利用栈来进行计算

  关于DFS和BFS的搜索题目，首先要将其转化为树，如迷宫，也可转化为树来搜索

  DFS是一条链一条链的搜索，而BFS是逐层进行搜索，这是他俩一个很大的区别

 

最经典的部分和问题：

 给定整数a1、a2、a3、..............、an，判断是否可以从中选出若干个数，使得他们的和恰好为k。

限制条件：

• 1 <= n <= 20
• -10^8 <= ai <= 10^8
• -10^8 <= k <= 10^8

样例：

• 输入：

       4    (n);

       1 2 4 7    (a数组)

       13     (k)

• 输出：

       YES（13 = 2 + 4 + 7）

该题就可以用DFS来进行计算：首先先建树。 

直到遍历到最低端为止， 如果不满足情况，输出no，若满足情况，输出yes

#include<cstdio>
#include<iostream>

using namespace std;

const int maxn =100;
int n, k;
int a[maxn];

bool dfs(int i, int sum){
    if(i == n) return sum == k;  //递归结束条件

    //不加a[i]的情况
    if(dfs(i + 1, sum)) return true;;

    //加上a[i]的情况
    if(dfs(i + 1, sum + a[i])) return true;

    return false;    //加上a[i]都不能刚好等于k，则返回假
}

int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    scanf("%d", &k);

    bool result = dfs(0, 0);     //深度优先搜索

    if(!result) printf("NO\n");
    else printf("YES\n");

    return 0;
}

 

然后说一下BFS，BFS与DFS相类似，也是从某个状态出发索引所有可以到达的状态

不同之处在于搜索的方式不一样，BFS是一层一层的搜索。即先搜索距离近的，通过一次转移，可以到达这一层的所有状态，它只从上到下遍历一次。

 BFS利用队列来进行计算。搜索时首先将初始状态添加到队列里，此后从队列的最前端不断取出状态，把从该状态而可以转移到的状态（这些状态还未被访问）加入到队列里，如此重复，直到队列被取空或找到了问题的解。

 

最经典的迷宫问题：

给定一个大小为n * m的迷宫，迷宫由通道和墙壁组成，每一步都可以向邻接的上下左右四格的通道移动，请求出从起点到终点的最小步数。假设：从起点一定可以到达终点。（S代表起点，G代表终点）

限制条件：      0 <= N <= 100    ,    0 <= M <= 100

输入：

10  10         （N   M）

#S######.#
......##.#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.#######.#
....#.....
.####.###.
....#...G# 

输出：

22

BFS可以用来求最短路径，最少操作等问题，所以可以用BFS来做

 BFS只要将已经访问过的状态用标记标注，就可以很好的做到由近及远搜索（如果要输出最短距离，我们可以用一个二维数组把他保存起来，然后再输出）

因为要向四个不同方向移动，可以用dx[4]和dy[4]来表示四个方向。通过循环就可以实现四个方向的遍历

/*求最短路径*/ 
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<cstring>
#include<cmath>

using namespace std;

const int INF = 1000000000;

typedef pair<int, int>P;
char maze[110][110];
int N, M;
int sx, sy;   //起始坐标 
int gx, gy;   //终点坐标

int d[100][100];

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

void find(int gx, int gy){
	if(gx == 0&&gy == 0){
		printf("(%d,%d)\n", gx, gy);
	}
	find(d[gx][gy]);
	printf("(%d,%d)\n", gx, gy);
}

int bfs(){
	queue<P>Q;
	
	for(int i = 0; i < N; i++)
		for(int j = 0; j < M; j++)
			d[i][j] = INF;
			
	//将起点加入队列，并把这一地点的距离设置为0
	sx = 0; sy = 0;
	Q.push(P(sx, sy));
	d[sx][sy] = 0;
	
	while(!Q.empty()){
		P p = Q.front(); Q.pop();
		
		if(p.first == gx&&p.second == gy) break;
		
		for(int i = 0; i < 4; i++){
			int nx = p.first + dx[i];
			int ny = p.second + dy[i];
			if(nx >= 0&&nx < N&&ny >= 0&&ny < M&&maze[nx][ny] != '1'&&d[nx][ny] == INF){
				Q.push(P(nx, ny));
				d[nx][ny] = d[p.first][p.second] + 1;
			}
		}
	}	
	find(gx, gy);
}

int main()
{
	while(scanf("%d%d", &N, &M) != EOF){
		for(int i = 0; i < N; i++)
			for(int j = 0; j < M; j++)
				cin >> maze[i][j];
		solve();
	}
	return 0;
}