dfs，bfs入门精讲、、、

最近随着和郑州师范学院的ACM队员的接触，我感触还是比较大的，我们和他们的差距还是比较大的，他们已经有了成体系的学习方法 ，有比较科学的训练，而且有相对较好的硬件设备（这点没法比，毕竟人家学习有政府的资助），然后他们管理还是比较严格的话，虽然可能会很难受，但是确实能学到真本事，这个世界本没有无缘无故的便能得到的荣誉，你想得到什么就必须要付出什么。但既然要搞这个，一些晦涩难懂的算法你能绕过去吗？你不啃，别人啃，然后别人拿奖，到时候你有后悔，然后露出羡慕的眼神，和作为绿叶陪衬鲜花的那份失落感，但是又有谁去怜惜呢。
希望自己能在这次暑期特训的过程中一点点的进步，基础总不能一直不好吧。
自己目前跟不上，就从最基本的递归，bfs，dfs ，对字符串的处理等简单算法搞起。多刷题。
迷宫问题
定义一个二维数组：

int maze[5][5] = {

0, 1, 0, 0, 0,

0, 1, 0, 1, 0,

0, 0, 0, 0, 0,

0, 1, 1, 1, 0,

0, 0, 0, 1, 0,

};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。

Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。

Output
左上角到右下角的最短路径，格式如样例所示。

Sample Input
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

Sample Output
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)

##2、解题思路
问题要求解从左上角的点到右下角的点的最短路径，并输出。要求解最短路径，可以用广度优先搜索，因为广度优先搜索具有最佳解的性质：若所有边的长度相等，广度优先搜索算法是最佳解——亦即它找到的第一个解，距离根节点的边数目一定最少。因为这题要求输出走过的路径，所必须在搜索的过程中记录下路径。

广度优先搜索的具体做法

从初始节点start开始，将start加入队列
取出队列中的队头元素，访问以该节点为起始点的四个邻域节点,，这里需要判断该节点是否可访问(maps[i][j]==0)，是否已经被访问过(visited[i][j]==0)，同时检查该节点是否超出地图越界。
如果经过检查后该节点可以访问，则访问该节点，visited[i][j]=1,并将该节点的信息(横坐标x,纵坐标y,父节点f)存入队列中。
重复2步骤，直到找到end节点，或者队列为空。
因为我们需要输出路径，所以在进行广度优先搜索时并没有采用STL里的queue，因为如果使用STL里的队列，队头元素出队后就真正地丢失了这个节点的信息，所以具体做法是自己用数组模拟队列，队列中存储一个节点的信息，包括：节点横坐标，纵坐标，父节点。
开始用dfs做，由于dfs不能解决最短路，只是找到了，起点和终点之间的路径。后来看博客发现也可以有dfs，要再加个变量数组存储路径；然后当路径到达终点时程序结束。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=6;
bool vst[maxn][maxn]; // 访问标记
int map[maxn][maxn]; // 坐标范围
int dir[4][2]={0,1,0,-1,1,0,-1,0}; // 方向向量，(x,y)周围的四个方向
 int k=0;
bool CheckEdge(int x,int y) // 边界条件和约束条件的判断
{
	if(!vst[x][y] && x>=0&&x<5&&y>=0&&y<5 && map[x][y]!=1) // 满足条件
		return 1;
	else // 与约束条件冲突
		return 0;
}
 
void dfs(int x,int y)
{
	vst[x][y]=1; // 标记该节点被访问过
	if(map[x][y]==0) // 出现目标态G
	{
		printf("(%d,%d)\n",x,y);	
		if(x==4&&y==4)
		k=1;
	}
	if(k) return;	
	for(int i=0;i<4;i++)
	{
		if(CheckEdge(x+dir[i][0],y+dir[i][1])) // 按照规则生成下一个节点
			dfs(x+dir[i][0],y+dir[i][1]);
	}
 // 没有下层搜索节点，回溯
}
int main()
{
	int x,y;
	int x1,y1;
    for(x=0;x<5;x++)
        for(y=0;y<5;y++)
        
        scanf("%d",&map[x][y]);
    dfs(0,0);  
	return 0;
}

#include <iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int maxn=5;
int place[maxn][maxn];
int dx[] = { 0, 0, 1,-1} ;
int dy[] = { 1,-1, 0, 0} ;//dx dy是搜索节点的边or称2为方向
struct node
{
    int x,y;
    //int step;
    int pre;
}way[1000];
//保留问题 怎么输出路径
bool judge(int x,int y)
{
    if(x < 0 || x > 4 || y < 0 || y > 4)
        return false;
    return true;
}
void print (int i)
{
    if(way[i].pre == -1)return;
    print(way[i].pre);//把pre作为下标
    printf("(%d, %d)\n",way[i].x,way[i].y);
 
}
void BFS(int sx,int sy)//给的参数是起点和终点
{
    place[sx][sy]=1;
    int i=0;
    way[i].x=sx;
    way[i].y=sy;
    way[i].pre=-1;//设置初始状态
    queue<node>q;
    q.push(way[i]);
    node next;
    while(!q.empty())
    {
        //队列非空 判断入队条件
        //四个方向
        way[i]=q.front();
        q.pop();
        if(way[i].x == 4&&way[i].y == 4)
        {
            print(i);
            return;
        }
        for(int j = 0; j < 4 ; j++)//4个方向
        {
            int x = way[i].x + dx[j];
            int y = way[i].y + dy[j];
 
            if(judge(x,y) && !place[x][y])//如果满足条件 没有越界且能访问
            {
                next.x = x ;
                next.y = y ;
                next.pre = i;//pre记录的是上一个的坐标！！理解！
                place[x][y]=1;
                q.push(next);
            }
 
        }
        i++;
    }
 
}
 
int main()
{
   for(int i=0;i<maxn;i++)
   {
       for(int j=0;j<maxn;j++)
       {
           scanf("%d",&place[i][j]);
       }
   }
   printf("(0, 0)\n");
    BFS(0,0);
    return 0;
}

ps：两种算法的特点及其应用场景：
二维数组的题目，N小于20的，适用DFS。而一般 N<= 200，N<=1000这种，一定不可能用DFS去做。而且并不只是整个题目不能用DFS，其中的每一步也不能使用DFS。

BFS的基本步骤

1.将初始点（一个或多个）加入一个集合尾

2.从集合头取出点，判断初始点的周边点，将符合条件的点加入队列

3.重复2操作，直至集合为空。(一般每个点只加入队列一次)

一般来说用DFS解决的问题都可以用BFS来解决。

DFS(深搜的同时考虑回溯）

bfs＝队列，入队列，出队列；dfs=栈，压栈，出栈
bfs是按一层一层来访问的，所以适合有目标求最短路的步数，你想想层层搜索每次层就代表了一步。bfs优先访问的是兄弟节点，只有这一层全部访问完才能访问下一层，也就是说bfs第几层就代表当前可以走到的位置(结点).而dfs是按递归来实现的，它优先搜索深度，再回溯，优先访问的是没有访问过的子节点

DFS多用于连通性问题因为其运行思想与人脑的思维很相似，故解决连通性问题更自然。BFS多用于解决最短路问题，其运行过程中需要储存每一层的信息，所以其运行时需要储存的信息量较大，如果人脑也可储存大量信息的话，理论上人脑也可运行BFS。
总的来说多数情况下运行BFS所需的内存会大于DFS需要的内存(DFS一次访问一条路，BFS一次访问多条路)，DFS容易爆栈(栈不易”控制”)，BFS通过控制队列可以很好解决”爆队列”风险。
它们两者间各自的优势需要通过实际的问题来具体分析，根据它们各自的特点来应用于不同的问题中才能获得最优的性能。