DFS 与 BFS Lv.1

IceAge · 2021-11-02 23:07:58 · 个人记录

一、DFS 基本过程

二、BFS 基本过程

三、DFS 与 BFS 对比

数据结构：DFS 用的是 stack ，BFS 用的是 queue 。
空间：DFS 是 O(h) ，BFS 是 O(2^h) （ h 代表深度）。
BFS 搜到的具有“最短性”，DFS 不具有（边的权值均为 1 ）。

四、DFS

1. 算法概述

每个 DFS 都对应着一棵搜索树。

回溯：回到上一步的状态，对应着树上走向父节点。回溯的时候一定要注意恢复现场。

DFS 最重要的是顺序，即我们要以怎样的顺序遍历所有的方案。我们在纸上画一棵树就基本明白了。

以全排列问题为例：

2. 例题1 排列数字——如何回溯

顺序：先填第一位，再填第二位，……，最后填第 n 位。

当 n=3 时，搜索树如图所示：

代码实现：

// AcWing 842. 排列数字
#include <bits/stdc++.h>
using namespace std;
const int N=10;
int n;
int path[N];
bool vis[N];
void dfs(int u)
{
    if (u==n)
    {
        for (int i=0;i<n;i++)
            printf("%d ",path[i]);
        puts("");
        return;
    }
    for (int i=1;i<=n;i++)
        if (!vis[i])
        {
            path[u]=i;
            vis[i]=true;
            dfs(u+1);
            vis[i]=false;
        }
    return;
}
int main()
{
    scanf("%d",&n);
    dfs(0);
    return 0;
}

3. 例题2 n - 皇后问题——如何剪枝

剪枝：如果我们能提前判定某个方案已经不合法了，我们就不用再往下搜了，形象上就是把树枝剪掉了。

解法1

顺序：对于每一层，我们枚举每个皇后放在哪一列，用枚举全排列的方法去做。

按照如上顺序枚举，我们已经保证了每行只有一个皇后。我们还需要三个 bool 数组，分别表示哪几列已经有了皇后，哪条形如 ‘/’ 的对角线已经有了皇后，以及哪条形如 ‘\’ 的对角线已经有了皇后。比较麻烦的时后两个 bool 数组，仿照行和列，我们可以给每种对角线编号为 0\sim2n-2 共 2n-1 条对角线，找横纵坐标与这些对角线编号的规律。这个规律可以自己画张图手推。

代码实现：

// AcWing 843. n-皇后问题
#include <bits/stdc++.h>
using namespace std;
const int N=20;
char g[N][N];
bool col[N],dg[N],udg[N];
int n;
void dfs(int u)
{
    if (u==n)
    {
        for (int i=0;i<n;i++)
            puts(g[i]);
        puts("");
        return;
    }
    for (int i=0;i<n;i++) // 第u行第i列
        if (!col[i] && !dg[u+i] && !udg[u-i+n-1])
        {
            g[u][i]='Q';
            col[i]=dg[u+i]=udg[u-i+n-1]=true;
            dfs(u+1);
            g[u][i]='.';
            col[i]=dg[u+i]=udg[u-i+n-1]=false;
        }
    return;
}
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            g[i][j]='.';
    dfs(0);
    return 0;
}

解法2

挨个枚举所有格子，枚完了最后一个格子就找到了一组答案。

// AcWing 843. n-皇后问题
#include <bits/stdc++.h>
using namespace std;
const int N=20;
char g[N][N];
bool row[N],col[N],dg[N],udg[N];
int n;
void dfs(int x,int y,int s)
{
    if (y==n)
    {
        x++;
        y=0;
    }
    if (x==n)
    {
        if (s==n)
        {
            for (int i=0;i<n;i++)
                puts(g[i]);
            puts("");
        }
        return;
    }
    dfs(x,y+1,s);
    if (!row[x] && !col[y] && !dg[x+y] && !udg[x-y+n-1])
    {
        g[x][y]='Q';
        row[x]=col[y]=dg[x+y]=udg[x-y+n-1]=true;
        dfs(x,y+1,s+1);
        g[x][y]='.';
        row[x]=col[y]=dg[x+y]=udg[x-y+n-1]=false;
    }
    return;
}
int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++)
            g[i][j]='.';
    dfs(0,0,0);
    return 0;
}

五、BFS

1. 算法概述

形象化的理解，BFS 的搜索就像是一层一层往外搜的，第一次把所有距离为 1 的点搜到，第二次把所有距离为 2 的点搜到，这样就可以保证第一次搜到某个点时是最短的（边权为 1 ）。

2. 例题1 走迷宫

如图是我们在地图上 BFS 的模拟图，点上的值表示这个点是在至少第几次搜索的时候搜到的。

这样，我们不仅走到了终点，还求出了起点到终点的最短路程，即 8 。

BFS 算法通用伪代码：

queue <- 初始化
while 队列不空
{
    t <- 队头
    拓展t
}

BFS 小技巧：我们可以用一个方向数组代替多次的 if 判断，即用数组分别存下四个方向的向量（方向数组具体为多少依题目而定，此题就是上下左右移动一格的四个向量）。

代码实现：

// AcWing 844. 走迷宫
#include <bits/stdc++.h>
using namespace std;
typedef pair <int,int> PII;
const int N=110;
const int dx[4]={0,-1,0,1},dy[4]={1,0,-1,0};
int g[N][N];
int d[N][N];
int n,m;
int bfs()
{
    memset(d,-1,sizeof d);
    d[0][0]=0;
    PII q[N*N];
    int hh=0,tt=0;
    q[0]={0,0};
    while (hh<=tt)
    {
        auto t=q[hh++];
        for (int i=0;i<4;i++)
        {
            int x=t.first+dx[i],y=t.second+dy[i];
            if (x>=0 && x<n && y>=0 && y<m && g[x][y]==0 && d[x][y]==-1)
            {
                d[x][y]=d[t.first][t.second]+1;
                q[++tt]={x,y};
            }
        }
    }
    return d[n-1][m-1];
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i=0;i<n;i++)
        for (int j=0;j<m;j++)
            scanf("%d",&g[i][j]);
    printf("%d\n",bfs());
    return 0;
}

【拓】如果我们要求出一条具体的路径该怎么做呢？我们可以考虑给每个点 (x,y) 额外记录一条信息 pre[x][y] ，表示走到这个点的上一个点是从哪儿过来的，然后从终点往回一直找到起点，就找到了一条路径。可以自己试着实现一下。

六、习题——八数码

考虑用 BFS 做这道题。我们将每个八数码游戏的状态用一个如题意所示的字符串表示出来了，这就提示我们用每一个状态作为搜索树中的每一个节点，对于每个节点，将 x 分别向上下左右四个方向移动可以得到四个状态，如果该状态未出现过，我们就把它插入队列中；否则就跳过，这个时候求得的也不是最小步数。总而言之，算法流程如下：

首先确定如何将状态表示成一个字符串。
将初始状态插入队列。
每次取出队头字符串，还原回一个状态，分别表示出上下左右移动后的四个状态。先判定某状态是否是 \texttt{12345678x} ，如果是，直接返回答案；否则，如果某个状态已经有答案了，直接跳过；否则更新答案并插入队列。
若一直没有返回，直接输出 -1 。

代码实现：

// AcWing 845. 八数码
#include <bits/stdc++.h>
using namespace std;
const string STD="12345678x";
string s;
queue <string> q;
unordered_map <string,int> d; // 每个状态的答案
int bfs()
{
    q.push(s);
    d[s]=1; // 实际上应该是0，只不过我们再判断一个状态是否访问过时用的是0判断，所以把每个状态的最小步数加1
    while (q.size())
    {
        string t=q.front();
        q.pop();
        int pos=0;
        for (pos=0;pos<9;pos++)
            if (t[pos]=='x')
                break;
        string backup=t;
        if (pos%3!=2) // 向右
        {
            swap(backup[pos],backup[pos+1]);
            if (backup==STD)
                return d[t]; // 原本是d[t]+1，但如上面所说，d是最小步数+1，所以这里要再减个1，最终是d[t]
            if (!d[backup])
            {
                d[backup]=d[t]+1;
                q.push(backup);
            }
        }
        backup=t;
        if (pos>=3) // 向上
        {
            swap(backup[pos],backup[pos-3]);
            if (backup==STD)
                return d[t];
            if (!d[backup])
            {
                d[backup]=d[t]+1;
                q.push(backup);
            }
        }
        backup=t;
        if (pos%3) // 向左
        {
            swap(backup[pos],backup[pos-1]);
            if (backup==STD)
                return d[t];
            if (!d[backup])
            {
                d[backup]=d[t]+1;
                q.push(backup);
            }
        }
        backup=t;
        if (pos<=5) // 向下
        {
            swap(backup[pos],backup[pos+3]);
            if (backup==STD)
                return d[t];
            if (!d[backup])
            {
                d[backup]=d[t]+1;
                q.push(backup);
            }
        }
    }
    return -1;
}
int main()
{
    char op[2];
    for (int i=0;i<9;i++)
    {
        scanf("%s",op);
        s.push_back(op[0]);
    }
    printf("%d\n",bfs());
    return 0;
}