[笔记]深度优先搜索与广度优先搜索

Dream_World · 2022-10-04 09:43:00 · 个人记录

看似\text{DFS}并没有不需要任何栈，但实际上，我们使用的是系统给的隐式栈，也称为调用栈（\text{Call Stack}）\text{DFS}的应用场景其实只有图论里，但是我们通常把\text{DFS}广义化

> 所有的状态的集合叫作状态空间 > 如果模型越**烂**，所用到的状态空间就越大 ~~(这是一个非常奇怪的发现)~~

深搜本质上是一种帝龟（递归）

优点

代码量小

可读性强

更容易实现

缺点

如果深度太高，容易栈溢出

容易超时

int cnt = 0; //解的数量
int a[...]; //每个格子上的数字
//设从a[0]开始填
bool vis[...]; //每个数字有没有填过
void dfs(int k){
    if (k >= n){
        cnt++;
        return ;
    }
    for (int i = 1; i <= n; i++){
        if (!vis[i]){
            vis[i] = true ;
            dfs(k + 1);
        }
    }
    for (int i = 1; i <= n; i++){
        bool flag = false ;
        for (int j = 0; j <
        k; j++)
            if (i == a[j]){
                flag = true ;
                break ;
            }
        if (!flag){
            a[k] = i;
            dfs(k + 1);
        }
    }
}

$pps$：因为深搜可以用**搜索树**来表示，所以可以用**剪枝**来**优化** $ppps$：恭喜！！！我们深搜的代码的**时间复杂度**成功的达到了 $O(n!)$ 这种**恐怖如斯**的时间，$but$ **剪枝**这种思路是**很玄学**的，所以有些深搜的代码可能卡不到$O(n!)

[笔记]深度优先搜索与广度优先搜索

目录

The First 深度优先搜索 \text{Depth First Search}