深搜笔记

2203chenzirui · 2023-04-15 08:35:20 · 个人记录

前言

这对于作者来说，还是有点难度的，所以参考了很多资料

优点

1.代码量小

2.可读性强

3.更容易实现

缺点

1.如果深度太高，容易发生栈溢出

2.容易超时

概念

深搜（DFS）全称 Depth First Search，是一种用于遍历或搜索树或图的算法。所谓深度优先，就是说每次都尝试向更深的节点走。

应用

全排列问题

出门右转传送门

这道题是进阶的 DFS。还包括了搜索中重要的技巧：回溯法。如果说递归(DFS)是一种“不撞南墙不回头”的算法，那么回溯法就是让他回头。比如我们要达到一个目的地，但是我们面前有三条路，并且只有一条路是可以到达目的地的，因此我们需要一条一条去尝试，如果不行的话就得回到原点，选择下一条路进行尝试，这种就叫做回溯。

具体过程：

1.构造空间树；

2.进行遍历；

3.如遇到边界条件，即不再向下搜索，转而搜索另一条链；

4.达到目标条件，输出结果。

So

伪代码为：

void dfs(int a)
{
   if(条件满足）
   {
      操作;
      return;
    }
    当层要做的事;
    标记为已用;
    进行下一层;
    回溯;
}

总结

1.深搜在图论中大量使用（实际上深搜的概念就是基于图论的，只不过我们通常把深搜的概念广义化）

2.当你实在做不出来时骗分