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

阿里云国内75折回扣微信号：monov8

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

第十三章 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();
}