数据结构与算法-----BFS与DFS（广度优先搜索与深度优先搜索）

DFS：（Deep First Search）深度优先搜索。
是一种利用队列实现的搜索算法。简单来说，其搜索过程和 “湖面丢进一块石头激起层层涟漪” 类似。

BFS：（Breath First Search）广度优先搜索。
是一种利用递*归实现的搜索算法。简单来说，其搜索过程和 “不撞南墙不回头” 类似。
BFS 的重点在于队列，而 DFS 的重点在于递归。这是它们的本质区别。

话不多说，先从DFS说起。

**

1.DFS（深度优先搜索）

深度优先搜索的步骤：递归下去，回溯上来。
顾名思义，深度优先，则是以深度为准则，先一条路走到底，直到达到目标。

直到既没有达到目标又无路可走了，那么则退回到上一步的状态，走其他路。这便是回溯上来。

下面结合具体例子来理解。
如图所示，在一个迷宫中，黑色块代表玩家所在位置，红色块代表终点，问是否有一条到终点的路径

我们用深度优先搜索的方法去解这道题，由图可知，我们可以走上下左右四个方向，我们规定按照左下右上的方向顺序走，即，如果左边可以走，我们先走左边。然后递归下去，没达到终点，我们再回溯上来，等又回溯到这个位置时，左边已经走过了，那么我们就走下边，按照这样的顺序与方向走。并且我们把走过的路标记一下代表走过，不能再走。

所以我们从黑色起点首先向左走，然后发现还可以向左走，最后我们到达图示位置

已经连续向左走到左上角的位置了，这时发现左边不能走了，这时我们就考虑往下走，发现也不能走，同理，上边也不能走，右边已经走过了也不能走，这时候无路可走了，代表这条路是死路不能帮我们解决问题，所以现在要回溯上去，回溯到上一个位置，

在这个位置我们由上可知走左边是死路不行，上下是墙壁不能走，而右边又是走过的路，已经被标记过了，不能走。所以只能再度回溯到上一个位置寻找别的出路。

最终我们回溯到最初的位置，同理，左边证明是死路不必走了，上和右是墙壁，所以我们走下边。然后递归下去

到了这个格子，因为按照左下右上的顺序，我们走左边，递归下去

一直递归下去到最左边的格子，然后左边行不通，走下边。

然后达到目标。DFS的重要点在于状态回溯。
代码如下

int goal_x = 9, goal_y = 9;     //目标的坐标，暂时设置为右下角
int n = 10 , m = 10;               //地图的宽高，设置为10 * 10的表格
int graph[n][m];        //地图
int used[n][m];         //用来标记地图上那些点是走过的
int px[] = {-1, 0, 1, 0};   //通过px 和 py数组来实现左下右上的移动顺序
int py[] = {0, -1, 0, 1};
int flag = 0;           //是否能达到终点的标志

void DFS(int graph[][], int used[], int x, int y)
{
    // 如果与目标坐标相同，则成功
    if (graph[x][y] == graph[goal_x][goal_y]) {     
        printf("successful");
        flag = 1;
        return ;
    }
    // 遍历四个方向
    for (int i = 0; i != 4; ++i) {    
        //如果没有走过这个格子          
        int new_x = x + px[i], new_y = y + py[i];
        if (new_x >= 0 && new_x < n && new_y >= 0 
            && new_y < m && used[new_x][new_y] == 0 && !flag) {
            
            used[new_x][new_y] = 1;     //将该格子设为走过

            DFS(graph, used, new_x, new_y);      //递归下去

            used[new_x][new_y] = 0;//状态回溯，退回来，将格子设置为未走过
        }
    }
}

BFS广度优先：
很像二叉树的层次遍历过程，一级一级的来～。
首先起始节点压入队列，然后当这个节点被推出队列，它的所有邻就得马上给我进到队列里来！然后一直这样重复下去，直到队列空了。这期间，我们可以把自己的实际问题“放入”出队进队这一活动中，实现我们的算法目的。

代码如下

int n = 10, m = 10;                   //地图宽高
void BFS()
{
    queue que;              //用队列来保存路口
    int graph[n][m];          //地图
    int px[] = {-1, 0, 1, 0};   //移动方向的数组
    int py[] = {0, -1, 0, 1};
    que.push(起点入队);      //将起点入队
    while (!que.empty()) {    //只要队列不为空
        auto temp = que.pop();          //得到队列中的元素
        for (int i = 0; i != 4; ++i) {
            if(//可以走) {
                //标记当前格子
                //将当前状态入队列，等待下次提取
            }
        }
    } 
}