深度优先搜索(DFS) 总结(算法+剪枝+优化总结)

深度优先搜索(DFS) 总结(算法+剪枝+优化总结)

本文中会引用部分实例、文献资料来自不同的作者之手，由于资料整理比较困难，转载地址不在文中列举。如有侵权请联系我更换或删除！对于提供题解思路的各位大佬和作者：非常感谢！

一、前导

定义上的深度优先搜索的思路与树的先序遍历非常相似，是针对图的搜索而提出的一种算法，下面是算法导论上的解释：

在深度优先搜索中，对于最新发现的顶点，如果它还有以此为顶点而未探测到的边，就沿此边继续探测下去，当顶点v的所有边都已被探寻过后，搜索将回溯到发现顶点v有起始点的那些边。这一过程一直进行到已发现从源顶点可达的所有顶点为止。如果还存在未被发现的顶点，则选择其中一个作为源顶点，并重复上述过程。整个过程反复进行，直到所有的顶点都被发现时为止。

在深度优先搜索中，每当扫描到已发现的顶点u的邻接表，从而发现新顶点v时，就将置v的先辈域Π[v]为u。与广度优先搜索不同的是，其先辈子图形成一棵树，深度优先搜索产生的先辈子图可以有几棵树所构成，因为搜索可能由多个源顶点开始重复进行。因此，在深度优先搜索中，先辈子图的定义也和广度优先搜索中稍有所不同：GΠ = (V, EΠ)，其中EΠ = {(Π[v], v) : v ∈V 且 Π[v] ≠ NIL}

在实际的操作中，我们一般对深度优先搜索问题进行分类：

1. 定义的DFS：对图的连通性进行测试，典型的问题：迷宫连通性测试、图的条件搜索等
2. 广义的DFS–DFS思路的应用：DFS搜索顺序+规则问题、穷举结果寻求最优解/符合条件解等等，由于其穷举答案的本质，又被称为爆搜

深度优先搜索(下文统称DFS)的精髓在于递归求解问题的思路以及回溯的处理。而针对搜索的过程，又有更为重要的剪枝、优化，必要的剪枝优化(通过对穷举答案方式进行改进)对DFS的顺利执行有着不可或缺的作用。本文章将针对DFS的原理、常见的题型、剪枝优化的思路进行分析。当然，爆搜的题型千千万，不可能一概而论，我会通过具体的题目对几类问题的求解思路进行总结分析，构建基本的思维模型。

二、原理分类与分析 1. DFS连通性模型

在测试图的连通性时，DFS与实际人们的思想一致，相对于起点选择一条路走到底，发现不行就返回选择的节点换一条路试，直到试出一条能到达终点的路。当然，一直试不出来就表示该起点与某点(终点)不连通。其他DFS连通性模型的思想与之类似。

针对实际问题，我又将连通性模型按照是否需要回溯继续细分：

1. 无需回溯：统计某点能到达的点的个数问题

在这类问题中，我们一般从某点出发进行搜索，对于已经被搜索过的点可以直接抛弃(标记不可访问)，对于当前被搜索的点递归搜索周围邻接的点并进行计数，直到无法搜索到合法的点返回。最终计数变量将记录所有能到达的点。

典型模板题：ACWing.1113 红与黑

解题报告：https://blog.csdn.net/yanweiqi1754989931/article/details/109243556X

2.需要回溯：迷宫类问题，测试两点间连通性

在这类问题中，由于当前选择的路径未必能够到达目标点，因此需要设置回溯，当搜索到非法路径返回时需要“恢复现场”，即：对于该路径下各点的访问状态重置。具体的搜索过程如下图所演示：

典型模板题：ACWing.1112 迷宫

解题报告：https://blog.csdn.net/yanweiqi1754989931/article/details/109239579

二维矩阵里走迷宫，非常简单

典型模板题：ACWing.1116 马走日

解题报告：https://blog.csdn.net/yanweiqi1754989931/article/details/109247649

这题堪称经典，与迷宫模板不同的是移动路径的选择和点合法性的判断，属于简单的搜索题

根据数据结构，又可以将两个模型分别继续细分，DFS可以基于邻接矩阵、邻接表、边集数组实现，思路相同，只是路径的遍历方式、点的访问有所改变。

这里留个坑，以后会选择不同数据结构类型的题目补充在这里

⭐总结一下DFS的模板框架(简单描述)

function dfs(当前状态){
	if(当前状态 == 目的状态){
        ···
    }
    for(···寻找新状态){
        if(状态合法){
            vis[访问该点]；
            dfs(新状态);
            ?是否需要恢复现场->vis[恢复访问]
        } 
    }
    if(找不到新状态){
        ···
    }
}

2. DFS思路应用-穷举求解问题

在无路可走时，我们往往会选择搜索算法，因为我们期望利用计算机的高性能来有目的的穷举一个问题的部分甚至所有可能情况，从而在这些情况中寻找符合题目要求的答案。这也是“爆搜”之名的由来

我们约定，对于问题的介入状态，叫初始状态，要求的状态叫目标状态。 这里的搜索就是对实时产生的状态进行分析检测，直到得到一个目标状态或符合要求的最佳状态为止。对于实时产生新的状态的过程叫扩展（由一个状态，应用规则，产生新状态的过程）

搜索的要点：

1. 选定初始状态，在某些问题中可能是从多个合法状态分别入手搜索；

2. 遍历自初始状态或当前状态所产生的合法状态，产生新的状态并进入递归；

3. 检查新状态是否为目标状态，是则返回，否则继续遍历，重复2-3步骤

对状态的处理：DFS时，用一个数组存放产生的所有状态。

1. 把初始状态放入数组中，设为当前状态；
2. 扩展当前的状态，从合法状态中旬寻找一个新的状态放入数组中，同时把新产生的状态设为当前状态；
3. 判断当前状态是否和前面的状态重复，如果重复则回到上一个状态，产生它的另一状态；
4. 判断当前状态是否为目标状态，如果是目标目标状态，则找到一个解答，根据实际问题需求，选择继续寻找答案或是直接返回。
5. 如果数组为空，说明对于该问题无解。

⭐与图的搜索类似，算法的框架基本不变，不同的是对于新状态的寻找、控制递归终止的条件更为复杂。在实际的题目中，会有一些题目需要对合法的新状态进行干预：可能在首轮搜索无法应用规则或所有条件均不满足且需要人为创建新的规则以继续搜索答案。这里也会设计到一系列剪枝与优化的问题。

function dfs(当前状态, 一系列其他的状态量){
	if(当前状态 == 目的状态){
        ···
    }
    for(···寻找新状态){
        if(状态合法){
            vis[访问该点]；
            dfs(新状态);
            ?是否需要恢复现场->vis[恢复访问]
        } 
    }
    if(找不到新状态){
        是否需要创建新规则？{
            创建并对当前状态进行访问vis;
            继续搜索;
            恢复现场/恢复访问vis;
        }
    }
}

这里举一道具体的题目案例来演示：ACWing分成互质组

题目描述：

给定 n 个正整数，将它们分组，使得每组中任意两个数互质。至少要分成多少个组？

输入格式

第一行是一个正整数 n。

第二行是 n 个不大于10000的正整数。

输出格式

一个正整数，即最少需要的组数。

数据范围

1≤n≤10

输入样例：

6
14 20 33 117 143 175

输出样例：

3

题目分析与算法设计：

给定n个数字分成互质组，那么考虑最坏的情况，要分成n组(n个数均不互质)。因为题目的数据量并不大，可以采用DFS解决，具体思路如下：

预备工作：准备一个数组存输入数据，准备一个容器，用于存不同的组，准备一个检索函数，可以检索指定分组内是否存在与目的数字重合的

1. **开始DFS：**首先是递归终止条件，判断是否搜到末尾，搜到末尾则更新组数计数的值，返回；
2. **继续：**每次在已有分组中从头开始搜索，用检索函数判断当前数字是否可以加入分组，若可以，加入后递归向下一个数字搜索
3. **新建分组：**考虑组数为0的情况、找不到可以加入组的情况，应该设置创建新分组的情况，加入新分组后，同样递归向后搜索。

#include 
#include 
#include 
using namespace std;
const int N = 11;
int n, p[N], cnt, ans = N;
vector num[N];	//这里使用STL中的Vector，其长度可变，更方便模拟分组的状态

int gcd(int x, int y){
    return y ? gcd(y, x % y) : x;	//辗转相除求最大公约数
}

//判断两数是否互质
bool check(int x, int t){
    for (int i = 0; i < num[t].size(); i++){
        if (gcd(x, num[t][i]) > 1) return false;
    }
    return true;


void dfs(int now)
{
    if (now == n){
        ans = min(ans,  cnt);	//每次搜完取最小组数
        return;
    }
    for (int i = 0; i <  cnt; i++){
        if (check(p[now], i)){
            num[now].push_back(p[now]);
            dfs(now + 1);
            num[i].pop_back();
        }
    }
    //需要考虑首次搜索无组可加、当前状态无组可加
    num[cnt++].push_back(p[u]);
    dfs(now + 1);
    num[--cnt].pop_back(); 
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];
    dfs(0);
    cout  word[i];

    for(int i=1;i