DFS 总结

David_Mercury · 2022-10-03 12:08:33 · 个人记录

算法思想

DFS（Depth-First-Search），即深度优先搜索。算法的主要思想是，在出现分支的时候，将每一条可能的路径都进行尝试，最终比对路径的结果，找到答案。

一般来说，我们是基于递归来实现该算法的。因此， DFS 函数也应当具备一般递归函数所共有的条件：目标态和状态转移。

算法实现与应用

上面所说的可能比较抽象，在这里举几个基本的应用形式来讲解。

1. 枚举

下面是一个典型的求有序无重复字符串全排列的 DFS 函数：

void dfs(int step){
    if(step==strlen(s)){                //目标态 
        cnt++;
        for(int i=0; i<strlen(s); i++) cout<<ans[i]<<" ";
        cout<<endl;
        return;
    }
    for(int i=0; i<strlen(s); i++){     //状态转移 
        if(bjt[s[i]]) continue;         //bjt[]标记该字母是否使用过 
        bjt[s[i]] = true;
        ans[step] = s[i];
        dfs(step+1);
        bjt[s[i]] = false;              //回溯状态 
    }
}

对每一位进行枚举可能的排列，直到枚举完了所有的位。需要关注的是最后的回溯操作。这是 DFS 的一个特点——将一条路径走完了以后，清除选择的后果，再回到上一个分支点，尝试另一条可能的路径。这样，就可以保证每一个可能的路径都被不重不漏地走过。

当然，并不是所有的 DFS 题都需要进行回溯，还需通过情形来进行判断。

2. DFS 解决背包问题

有 n 件物品和一个容量为 v 的背包。第 i 件物品的费用（即体积，下同）是 w[i] ，价值是 c[i] 。在将物品装入背包可使这些物品的费用总和不超过背包容量的情况下，求最大的价值总和。

如果我们要使用搜索来解决该问题，则对于每一个物品都有选与不选两种选择，可以由此分支出两种不同的方案。下面是一个模板程序：

void dfs(int num, int sum_w, int sum_c){
    if(sum_w > v) return;
    if(num==n+1){
        ans = max(ans, sum_c);
        return;
    }
    dfs(num+1, sum_w+w[num], sum_c+c[num]);
    dfs(num+1, sum_w, sum_c);
}

可以发现，对于 DFS ，我们有会有 2^{n} 种方案，所以时间复杂度为 O( 2^n ) ， n 为 30 左右的时候就会有 TLE 的风险。

这种问题叫作 01 背包问题，是动态规划的分支背包问题的一个分支。使用动态规划的方法，我们可以在 n 较大的情况下比较高效地解决。但是这个方法会受到 v 大小的限制，一但 v 超出了 1e8 ，就也会遇到瓶颈。详情敬请期待以后的动态规划和背包问题总结。

3. 走迷宫

const int MAXN = 10;
bool bjt[MAXN][MAXN];
int n,m,sx,sy,fx,fy,ans=INT_MAX;
int dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0}; //一种常用的转移方法 

void dfs(int step, int x, int y){
    //判断位置是否非法 
    if(x<1 or x>n or y<1 or y>m) return;
    if(bjt[x][y]) return;
    //目标态 
    if(x==fx and y==fy) {ans=min(ans, step); return;}
    //状态转移 
    bjt[x][y]=true;
    for(int i=0; i<4; i++) dfs(step+1, x+dx[i], y+dy[i]);
    bjt[x][y]=false;
    return;
}

这个函数的目的是判断从当前位置走到目标点的最短路径。本质也是枚举，唯一不同的是加上了对非法越界的判断。

不过，该方法在求最短路径时的平均时间复杂度较高。常道， DFS 是一个“执着”的搜索算法。它选定一条路径，就会死咬着走到底，直到无法再转移状态，才开始回溯。如下图。

找到目标点就比较困难，更不提它还要将所有路径走遍再打一个擂台了。这个时候，我们就得请出 BFS 了。

但是，还是有一个小优化的。

void dfs(int step, int x, int y){
    if(step>=ans) return;       //剪枝 
    if(x<1 or x>n or y<1 or y>m) return;
    if(bjt[x][y]) return;
    if(x==fx and y==fy) {ans=min(ans, step); return;}
    bjt[x][y]=true;
    for(int i=0; i<4; i++) dfs(step+1, x+dx[i], y+dy[i]);
    bjt[x][y]=false;
    return;
}

路径长度 step 比已有的最小 ans 大，那么再往下搜索就是无意义的行为，因此直接 return 即可。这种减少冗余状态拓展的方式被称作剪枝。

4. 记忆化搜索

与记忆化递归一样，在该分支节点上记录已计算的值，以来剪枝。

如这道题：

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles

很明显直接搜索会 TLE 。加上记忆化后的 DFS 函数如下：

void dfs(int x, int y){
    if(mem[x][y]!=-1)   return;     //初始化为-1，与值为0的路径区别 
    if(x>r or y>x)      {mem[x][y]=0; return;}
    mem[x][y] = trio[x][y];
    dfs(x+1, y); dfs(x+1, y+1);
    mem[x][y] += max(mem[x+1][y], mem[x+1][y+1]);
    return;
}

5. 连通块

一个 DFS 的重要应用。连通块，即在矩阵中，以定义的方式连通在一起的相同元素。这种连通方式大部分时候是四个边相连，但有时是八个方向周围一圈相连，甚至是其它的连通方式。

举个栗子：

0 0 0 0 1 1 1 0
0 0 0 0 1 1 1 0
0 0 0 0 1 1 1 0
0 0 1 0 1 1 1 0
0 1 1 1 0 0 0 0
0 0 1 0 0 0 0 0
0 0 0 0 0 0 0 0

现在我们以最典型的方式——即上下左右四个方向——定义连通块，则上图就有两个元素 1 的连通块。若以八个方向定义，它就有只有一个。

那我们该如何去求一个连通块包含的元素个数，或是去计算不同连通块的个数呢？很自然的，可以想到，我们可以使用走迷宫类 DFS 类似的方式来求连通块的个数

在这里，我先给出一个 DFS 求 01 矩阵中元素 1 的连通块个数的模板。

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 35;
int n, cnt, dx[4]={0,1,0,-1}, dy[4]={1,0,-1,0};
bool mp[MAXN][MAXN], bjt[MAXN][MAXN];

bool check_err(int x, int y){       //检查是否非法
    if(x<1 or x>n or y<1 or y>n) return true;
    if(!mp[x][y] or bjt[x][y]) return true;
    return false;
}

void dfs(int x, int y){
    bjt[x][y] = true;               //标记访问
    for(int i=0; i<4; i++){
        int nx=x+dx[i], ny=y+dy[i];
        if(check_err(nx, ny)) continue;
        dfs(nx, ny);
    }
    //注意：连通块求解时不需要回溯！！！ 
    return;
}

int main(){
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++) cin>>mp[i][j];
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++){
            if(!mp[i][j]) continue; 
            if(bjt[i][j]) continue; //若已经被访问过，则说明它是已经计算过的连通块里的元素 
            cnt++;                  //连通块个数 
            dfs(i, j);
        }
    cout<<cnt;

    return 0;
}

数连通块个数时的 DFS 不能回溯。因为这时我们需要标记桶 bjt[] 来记录它是否是属于之前已经被计算过的连通块里的元素。可以说，如果加上回溯操作整个程序将不会有任何意义。

经典例题

DFS 的运用很广泛，经常结合其它的算法来进行考察。下面是我个人认为比较好的几道 DFS 例题。

• P1162 填涂颜色：先将所有元素 0 标记为 2 ，然后对整个矩阵的最外围的那一圈 2 进行 DFS ，将它们重新标记为 0 。需要注意的是，我们需要将这个矩阵外再额外加上一圈 0 ，以来避免如下的情况：

                            0 0 0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 0             0 1 1 1 1 1 1 1 0 0
1 0 0 0 0 0 0 1             0 1 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 1             0 1 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 1     =>      0 1 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 1             0 1 0 0 0 0 0 0 1 0
1 0 0 0 0 0 0 1             0 1 0 0 0 0 0 0 1 0 
1 0 0 0 0 0 0 1             0 1 0 0 0 0 0 0 1 0 
0 1 1 1 1 1 1 0             0 0 1 1 1 1 1 1 0 0
                            0 0 0 0 0 0 0 0 0 0

这样不管从外围什么地方开始搜索，都可以正确地填涂。这种方法叫做洪水填充。

• P1441 砝码称重：DFS 枚举所有可能的方案，结合二进制 bitset 与位运算来进行桶标记重量。很综合的一道题。

• P4799 [CEOI2015 Day2] 世界冰球锦标赛：用背包来做的话， 10^{18} 的数据范围过大了；单纯地使用搜索的话， 2^{40} 次方的搜索量也过大。因此在这里引出折半搜索的概念：将比赛平分为两半比赛，分别 DFS 出所有的方案。然后按照金额对左半边的比赛的方案进行排序处理；再依次枚举右半边的方案，在左半边二分查找与该方案的总金额的和小于等于 m 的方案总数。这样，我们就将时间复杂度巧妙地转化为了 O( 2^n * \log{2^n} ) = O( 2^n * n ) 。

感谢您的观看

:)