第十三章 DFS与BFS（保姆级教学！！超级详细的图示！！）_算法

第十三章 dfs与bfs

一、深度优先搜索
二、广度优先搜索

一、深度优先搜索

1、什么是dfs？

dfs即depth first search，深度优先搜索。简单地理解为一条路走到黑。那么什么叫一条路走到黑呢？假设我们想在如下的地图中走出一条最长的路，那么最粗暴的方式就是枚举出每一种情况。
在这里插入图片描述
因此，按照dfs一条路走到黑的思想，我们将会出现如下路线：

先走a，然后到b，到了b有三种情况，意味着这条路还没走完，那我就接着走，从b走到e，走到e之后没路了。那我就回溯到b,为什么呢？
因为我原本走到b的时候就有三种情况，但是刚刚只走了一种情况，因此我要回到b再去尝试第二条路，于是我们就从e回到b，然后从b去f。到了f，又没路了，那我们就回到b走第三种情况，从b到g。这样我们就走完了从a->b的三种情况。又因为在a处其实还有三种情况，因此我们走完b的三种情况后，回到a,去走除了从a->b的第二种情况，即a->c。由此以往。

简而言之，就是我们一头扎进去，撞了南墙，我就退一步，但是决不放弃，在原基础上做出局部的改变去尝试第二条路，直到所有的情况我都试了，实在没有其他情况了，那我就回到a，从头出发，再做选择，再一头扎进去，直到成功。

2、dfs代码模板

（1）问题：

在这里插入图片描述

（2）分析：

在这里插入图片描述
我们将其各种选择，继续画成一棵树：

这张图就清晰很多了，因此想要用dfs，我们首先要有逻辑地画出一张地图，有了地图才能去搜。

（3）模板：

#include<iostream>
using namespace std;
const int n=10;
int ans[n];
bool mark[n];
int n;
void dfs(int u)
{
    //"回头"的条件
    if(u==n)
    {
        for(int i=0;i<n;i++)cout<<ans[i]<<" ";
        puts("");
        return;
    }
    
    for(int i=1;i<=n;i++)
    {
        if(mark[i]==false)
        {
            mark[i]=true;
            ans[u]=i;
            dfs(u+1);
            //复原
            mark[i]=false;
            ans[u]=0;
        }
    }
}

int main()
{
    cin>>n;
    dfs(0);
    return 0;
}

3、dfs代码分析

在这里插入图片描述
当然这个过程很抽象，那么我就帮大家模拟一下函数进行的过程吧^ _ ^（这里只模拟一部分，不理解的读者可自己模拟完。）

二、广度优先搜索

1、什么是bfs？

bfs即breadth first search，即广度优先搜索。如果说dfs是一条路走到黑的话，bfs就完全相反了。bfs会在每个岔路口都各向前走一步。因此其遍历顺序如下图所示：

在这里插入图片描述
我们发现每次搜索的位置都是距离当前节点最近的点。因此，bfs是具有最短路的性质的。为什么呢？这就类似于我们后面要学习的贪心策略。这里简单地介绍一下贪心，假设我们可以做出12次选择。我们想得到一个最好的方案。那么我们可以在第一次选择的时候，做出当前最好的选择，在第二次选择的时候，再做出那时候最好的选择，由此积累。当我们在每次的选择面前，都做到了当前最好的选择，那么我们就可以由局部最优推出整体最优。

这里也是类似的，我们可以在每次出发的时候，走到离自己最近的点，由此我们每次都保证走最近的，那从局部最近推整体最近，必有一条路是整体最近的。所以我们可以利用bfs做最短路问题。

2、bfs代码模板

（1）问题：

在这里插入图片描述
本题求的是最短路，因此我们可以利用bfs从当前节点出发，每次都向周围拓展。

（2）代码：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int n=110;
typedef pair<int,int> pii;
int map[n][n],mark[n][n];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},n,m,ans;
void bfs()
{
    memset(mark,-1,sizeof mark);
    queue<pii>q;
    q.push({0,0});
    mark[0][0]=0;
    while(!q.empty())
    {
        pii top=q.front();
        for(int i=0;i<4;i++)
        {
            int nex=top.first+dx[i],ney=top.second+dy[i];
            if(nex>=0&&nex<n&&ney>=0&&ney<m&&mark[nex][ney]==-1&&map[nex][ney]==0)
            {
                mark[nex][ney]=mark[top.first][top.second]+1;
                q.push({nex,ney});
            }
        }
        q.pop();
    }
    cout<<mark[n-1][m-1];
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            scanf("%d",&map[i][j]);
        }
    }
    bfs();
}