给 DFS 套上一个逐渐放宽的深度限制，反复搜索——用 DFS 的省内存，换来和 BFS 一样"最先找到的就是最浅的解"这个保证。
12.1 节的 DFS 内存开销很小——只需要 O(深度) 的栈空间，但它不保证第一个找到的解是最浅的：DFS 会一条道走到黑，如果先走的那条分支恰好很深、绕了很远才碰到解，DFS 就会先返回那个更深的解，即使旁边其实存在一个浅得多的解。
14.1 节的 BFS 能保证第一个找到的解就是最浅的，但它的代价是内存：BFS 的队列里，某一时刻要同时装下"这一层全部的节点"，当分支因子 b 较大、深度 d 也较大时，队列能膨胀到 O(b^d) 量级——很多题目（尤其是搜索空间几乎无穷大的场景，比如某些迷题、状态空间搜索）会直接把内存爆掉。
迭代加深搜索（Iterative Deepening DFS，简称 IDDFS）就是为了同时拿到"DFS 的低内存"和"BFS 的最浅解保证"而设计的：给 DFS 加一个深度限制，超过这个深度就不再往下探；如果限制内没找到解，就把限制加一层，重新从头开始搜索。因为每一轮都是先探浅的、后探深的（在限制范围内仍然是深度优先，但整体上是一轮比一轮更深），第一次找到解的那一轮，深度必然是最浅的。
IDDFS 由两部分组成：
| 组成部分 | 作用 |
|---|---|
| 深度限制 DFS | 普通的 DFS，但多带一个参数 limit；一旦当前深度达到 limit，就不再继续往下递归（即使还没到终点） |
| 外层驱动循环 | 从 limit = 0 开始，每次深度限制 DFS 找不到解就把 limit 加 1，重新完整地搜索一遍，直到找到解为止 |
用一棵简单的树演示：根节点 A（深度 0），A 有两个孩子 B、C（深度 1），B 的孩子是 D、E，C 的孩子是 F、G（都是深度 2）。假设目标节点是最右边的 G：
limit=0、limit=1）都没找到 G，因为限制不够深，根本没搜索到 G 所在的深度；第 3 轮 limit=2 时，DFS 依然是"一条道走到黑"的顺序（A→B→D→E，退回来再 →C→F→G），最终在深度 2 找到 G。因为是逐轮加深、每轮都从浅到深搜索，第一次找到目标的那一轮，深度必然是最小的——这正是 IDDFS 能保证"最浅解"的原因。| 1 | vector<int> adj[MAXN]; |
| 2 | int target; |
| 3 | |
| 4 | // 深度限制 DFS：depth 是当前深度，limit 是这一轮允许的最大深度 |
| 5 | bool DLS(int u, int depth, int limit) |
| 6 | { |
| 7 | if (u == target) return true; // 找到了 |
| 8 | if (depth == limit) return false; // ★ 到达本轮深度上限，不再往下递归 |
| 9 | for (int v : adj[u]) |
| 10 | if (DLS(v, depth + 1, limit)) return true; |
| 11 | return false; |
| 12 | } |
| 13 | |
| 14 | int IDDFS(int root, int maxPossibleDepth) |
| 15 | { |
| 16 | for (int limit = 0; limit <= maxPossibleDepth; limit++) // ★ 深度限制从 0 开始逐层加深 |
| 17 | { |
| 18 | if (DLS(root, 0, limit)) return limit; // 这一轮找到了，limit 就是最浅深度 |
| 19 | } |
| 20 | return -1; // 到最大可能深度都没找到，说明不存在 |
| 21 | } |
DLS（Depth-Limited Search）几乎就是一个标准的 DFS，唯一的区别是第 8 行——多了一个"到达深度上限就返回"的判断。真正实现"逐轮加深"的，是第 16 行的外层循环：limit 从 0 开始，每次 DLS 找不到解就把 limit 加 1，重新完整地跑一次 DLS。看起来 IDDFS 很浪费——limit=2 那一轮，等于把 limit=0、limit=1 时探索过的节点又重新走了一遍。但因为树（或图）的节点数量是随深度指数增长的，浅层节点数量相比最深一层几乎可以忽略：
| 深度 | 该层节点数（分支因子 b=10） | 占最深一层的比例 |
|---|---|---|
| 0 | 1 | 约 0.001% |
| 1 | 10 | 约 0.01% |
| 2 | 100 | 约 0.1% |
| 3 | 1,000 | 约 1% |
| 4（最深一层） | 10,000 | 100% |
b/(b-1) 倍（这里 b 是分支因子）。也就是说，IDDFS 的总时间复杂度和"直接对最深一层做一次 BFS"是同一个数量级，只是多了一个不到 2 倍的常数因子——用这一点点重复计算的代价，换来了 O(深度) 的内存占用（而不是 BFS 的 O(b^深度)），在搜索空间巨大、内存吃紧的场景下非常划算。