如何高效记录深度优先搜索（DFS）算法学习心得？

本文共计2972个文字，预计阅读时间需要12分钟。

深度优先搜索+DFS+是图论中最基础的，最重要的算法之一。DFS+是一种盲目搜索方法，它在每个点$(u)$上，任意选择一条边DFS+，直到回溯到$(u)$时才选择其他的边。

深度优先搜索 学习笔记 引入

深度优先搜索 DFS 是图论中最基础，最重要的算法之一。DFS 是一种盲目搜寻法，也就是在每个点 \(u\) 上，任选一条边 DFS，直到回溯到 \(u\) 时才选择别的边，如下图。

他的搜索顺序为 1-2-3-4-6。

递归实现指数型枚举

从 \(1\sim n\) 中这 \(n\) 个整数选取任意多个，输出所有可能的选择方案。

每一个数都有选与不选两种可能，相当于在每次递归上尝试选与不选两种分支，最后的时间复杂度即为 \(O(2^n)\)。

递归实现组合型枚举

组合型枚举的实现与指数型枚举的实现十分相近，只不过该问题是必须要在 \(n\) 个数中选取 \(m\) 个数，每个数还是有选、不选两条分支，所以实现直接在“指数型枚举”中加入两个剪枝即可：

1. 若当前选择的数的个数大于 \(m\) 直接返回。
2. 若当前选择的数的个数加上剩余的数的个数小于 \(m\) 则直接返回。

时间复杂度 \(O(2^n)\)。

递归实现排列型枚举

题目链接：题目详情 - 全排列问题 - ClorOJ (zshfoj.com)。

把每个可用的数作为数列中的下一个数，求解把剩余的 \(n-1\) 个数按照任意次序排列这个规模更小的子问题。

时间复杂度 \(O(n!)\)。