深度优先搜索

连通块

图上连通块：在图中用 DFS 给可达点标记，统计连通块数量、大小等。
迷宫连通块：把迷宫看成网格图，用 DFS 统计相连的空地区域数目。

判环

无向图：DFS 时遇到已访问但不是父亲的结点 ⇒ 有环。
有向图：用“正在访问 / 已访问”标记，DFS 中再次走到“正在访问”的点 ⇒ 有环。

搜索

图上搜索：在图中找是否存在某条路径、或枚举所有路径。
迷宫搜索：从起点 DFS 到终点，可以统计能否到达、路径条数等。
带回溯搜索：每一层做选择，失败就撤销选择继续试。

折半搜索（Meet in the middle）

把一次大搜索拆成“前一半 + 后一半”两部分：

• 先 DFS 枚举前一半并存表；
• 再 DFS 枚举后一半，用前半结果快速配对。
• 常用于子集和等状态数较大的枚举题。

暴力枚举

把“枚举所有方案”的过程写成 DFS：

• 每一层代表一次决策；
• 到达叶子结点就得到一个完整方案并检查是否满足条件。
• 可配合剪枝，提前丢掉不可能的分支。

【思维导图】