T02 Tutorial 2：BFS 与 DFS 手算，把访问顺序和解路径分开

一句话版

这份 tutorial 把 BFS 和 DFS 的手算流程完整走一遍，练习形式是：给一张有向图，写出 Open/Close 的变化、访问顺序和解路径。

题目地图

十六页，三道练习题加两道讨论题，共用的动作只有一个——手动维护两张表。

页	题目	考什么	主要失分点
p.3–4	同一棵树的 BFS / DFS 顺序	两种扩展次序的对比	把节点编号当成访问顺序
p.6–7	有向图上 BFS 找 A 到 F	Open 的查重	展开 B 时重复加入 C、D
p.8–9	同一张图 DFS，孩子按降序	孩子排列顺序的影响	没看清题目要求升序还是降序
p.10	用 DFS 输出全部节点	回溯与 Close 表	漏掉「已访问就掉头」那几步
p.12–13	换一张小图，DFS 找 A 到 F	死胡同后的回溯	走到 E 没退回去换分支
p.14–15	上图加一条 E → A	去掉查重后的完备性	只说「会出错」，没说清循环怎么形成

练习题那张有向图的边是 A→B、A→C、A→D、B→C、B→D、C→E、D→E、D→F、E→B、E→F。方向是这题全部的坑：A→D 是绕过 B、C 的那条长边，E→B 是斜着往回指的那条，箭头在 B 那一端。后半段讨论题换了一张更小的新图（A→B、A→C、B→C、B→D、C→E、D→F），别把两张图混着用。

概念卡

1. Open 与 Close 两张表（Open / Close List）

人话定义：Open 是「已经生成、还没展开」的待办清单，Close 是「已经展开过」的存档；手算时把这两列写在纸上，算法就跑起来了。

例子：BFS 的 Open 是队列，新节点加在队尾、从队首取；DFS 的 Open 是栈，加在栈顶、也从栈顶取。查重发生在生成的那一刻：展开一个节点时，它指向的节点若已经在 Open 或 Close 里，这条边就不再生成新条目（p.7 第 3 步）。答题表通常写成四列——步号、这一步展开谁、新生成什么、之后的 Open 长什么样。

常见误解

把查重当成可选的加速手段 → 它决定结果对不对。p.7 第 3 步展开 B 时，B→C 和 B→D 指向的两个节点都已在 Open 里，一个新条目都不加；漏了这步会写成 Open = [C, D, C, D]，后面每一行都错（p.7）。

2. BFS：兄弟先于孩子（Breadth-first Search）

人话定义：一层扩完再扩下一层，同层内按题目给的字母序处理。

例子：p.3 那棵树的结构是 1→{2, 3, 4}，2→{5}，3→{6, 7}，4→{8}，5→{9}，6→{10}。按层读是 1 | 2 3 4 | 5 6 7 8 | 9 10，访问顺序恰好等于节点编号——因为这张图本来就是按 BFS 顺序编号的，换一张图就对不上了。

常见误解

把节点上印的数字当成访问顺序 → p.4 用的是同一棵树，节点里的白色数字仍是编号，节点外的蓝色数字才是 DFS 访问顺序，两套数字并存（p.4）。另一处是以为 BFS 在有环图上不用查重——它照样需要，只是不会像 DFS 那样顺着环一路钻下去，后果轻一些（p.15）。

3. DFS：孩子先于兄弟，顺序由题目定（Depth-first Search）

人话定义：一条路走到底，走不动了退回上一个还有未展开兄弟的节点，换下一条。

例子：p.4 的 DFS 顺序是 1 → 2 → 5 → 9 → 3 → 6 → 10 → 7 → 4 → 8。验一遍：从 1 到 2，2 只有孩子 5，5 只有孩子 9，到底了；回到 1 换分支到 3，3 的第一个孩子 6，6 的孩子 10 到底；回到 3 走 7；回到 1 走 4，4 的孩子 8。练习题那道要求孩子按降序取，这是故意设的——DFS 的结果依赖孩子的排列顺序，做题前先确认题目要的是升序还是降序。

常见误解

用栈实现时把入栈顺序写反 → 栈是后进先出，想先访问 D 就要让 D 最后入栈（p.8）。另一处是看到 DFS 展开的节点少就下结论说它更快：p.9 里 DFS 只展开 A、D 两个而 BFS 展开了四个，原因是目标恰好落在降序的第一条分支上，改成升序结果完全不同（p.9）。

4. 环与完备性（Completeness）

人话定义：在有限有环图上，重复状态检查既影响终止性，也减少重复工作。

例子：p.12 那张小图加上一条 E → A 之后，A → C → E → A 构成一个环（p.14）。去掉重复检查，DFS 从 A 走到 C 再到 E，E 的出边指回 A，算法认为 A 是个新节点，于是又走 A → C → E → A，永远循环，F 永远访问不到（p.15）。这印证了 Lecture 2 p.36 那三行：DFS 完备吗，NOT REALLY；补救办法是沿路径检查重复状态；加上之后，在有限空间里才是完备的。

常见误解

以为「可以重复访问」只是效率变差 → 它直接让算法不终止，解就在旁边也找不到（p.15）。还有一处是把 p.10 图上的虚线当成没用的边：每条指向已访问节点的虚线都代表一次「查表发现来过了，掉头」，那正是 Close 表在工作（p.10）。

逐题拆解

p.8–9 的 DFS（降序）。同一张有向图，找 A 到 F，孩子按字母降序取。A 展开出 B、C、D，降序先取 D；D 展开出 E、F，降序先取 F——F 就是目标，结束。解路径 A → D → F，只展开了两个节点。答案图上实线是真正走过（展开）的边，虚线是生成了但没展开的边，A→B、A→C、D→E 都是虚线。

p.10 用 DFS 输出全部节点（仍是降序，按递归、进入时标记 visited 的口径）。不再找目标，把所有节点走一遍：A → D（降序最大）→ F（D 的孩子里降序最大，且 F 没有出边，是死路）→ 回到 D 取 E → E 的出边是 B 和 F，F 已访问，取 B → B 的出边是 C 和 D，D 已访问，取 C → C 的出边是 E，已访问 → 结束。输出顺序是 A, D, F, E, B, C。

p.12–13 换图之后的回溯。新图小得多：A→B、A→C、B→C、B→D、C→E、D→F，仍是 DFS、降序、找 A 到 F。走法是 A 的孩子 B、C，降序先取 C → C→E → E 没有出边，死路，回溯 → 回到 A 取 B → B 的孩子 C、D，C 已访问，取 D → D→F，找到。访问顺序 A, C, E, B, D, F；解路径 A → B → D → F。这一页真正要看的是那次回溯：DFS 走进 E 这个死胡同后还能退回 A 换分支，靠的是栈里留着的、路径上每个节点尚未展开的兄弟，这也是它空间复杂度 O(d·b) 而非 O(d) 的来源。

p.14–15 加一条边之后。只加 E → A，问题变成「如果节点可以被重复访问会怎样」。答案是 A → C → E → A 循环到底，F 永远访问不到。一句话记住：Close 表是 DFS 能不能停下来的前提。BFS 在同一张图上也需要查重（p.7 第 3 步就是），但它逐层推进、不会顺着环一路往下钻，所以后果没有这么致命。

课件里的坑

• [课件留白] p.6 的图只画了箭头，没有列出边表。两条最容易读错的是 A→D（绕过 B、C 的长边）和 E→B（斜着往回指，箭头在 B 那一端）。动笔前先把十条边抄成一张表再开算，比反复回看图省时间（p.6）。
• [课件留白] 练习题和讨论题用的是两张不同的图，p.12 换图时只在图上换了，正文没有提示。把讨论题的结论套回练习题那张图会得到完全不同的走法（p.12）。
• [补充] p.9 只呈现了降序的走法，升序的情形课件没算。这恰好是最值得自己补的一道——升序时 DFS 要先钻 B 那条分支，展开数和解路径都变，正好证明「DFS 更快」这个结论在这里不成立（p.9）。
• [补充] p.3 那棵树的访问顺序等于节点编号，是因为它本来就按 BFS 顺序编号。课件没点破这一层，照着记会以为「BFS 顺序 = 编号顺序」是普遍规律（p.3）。

课后 10 分钟：考点复习

这 10 分钟怎么用：合上页面，先默写三条——Open/Close 各存什么、查重发生在哪一刻、DFS 用栈时的入栈顺序；再把下面的「变式题」做一遍；最后回查两处最容易错的地方——展开时重复加入已在表里的节点、把访问顺序当成解路径。三步做完再往下看答案。

必背

1. 同一棵树上 BFS 与 DFS 的访问顺序完全不同：BFS 兄弟先于孩子，DFS 孩子先于兄弟。
2. 展开一个节点时，指向已在 Open 或 Close 里的节点的那些边不重复加入；漏掉这一步 Open 会长出重复项，后面整张表全乱。
3. 访问顺序与解路径是两回事：访问顺序里的节点未必在解路径上，答题时两样都要写清楚。
4. DFS 的结果取决于孩子的排列顺序，做题前先确认题目要求升序还是降序；用栈实现时，想先访问谁就让谁最后入栈。
5. 同一张图上 DFS 比 BFS 少展开几个节点，只说明目标恰好在先选的那条分支上，推不出 DFS 更快。
6. DFS 靠栈里保留的、路径上每个节点尚未展开的兄弟回溯，这是它空间复杂度 O(d·b) 而非 O(d) 的来源。
7. 有环的图上去掉重复状态检查，DFS 会沿着环无限循环、永远到不了目标；有限有环图需要重复状态检查保证终止；树或无环图不必依赖 Close 表。
8. BFS 逐层推进，不会顺着环一路往下钻，所以它同样需要查重，但有限分支且有有限深解时仍可找到解，无解时也可能不终止。

完整例题

p.6–7 那道 BFS 完整走一遍。图的边是 A→B、A→C、A→D、B→C、B→D、C→E、D→E、D→F，外加 E→B、E→F；目标是从 A 找到 F，同层节点按字母升序处理。Open 是队列，队首在左。

步	展开	新生成	Open（队首在左）
1	—	A	A
2	A	B, C, D	B, C, D
3	B	无	C, D
4	C	E	D, E
5	D	F	E, F

第 5 步生成 F 时命中目标，结束。逐步说明：

1. 第 2 步，A 的三条出边生成 B、C、D，按字母升序排进队尾。
2. 第 3 步是这道题唯一的考点。展开 B，它的出边 B→C 和 B→D 指向的两个节点都已经在 Open 里，所以一个新条目都不加，Open 只是把 B 出队。写成 [C, D, C, D] 的话，后面每一行都跟着错。
3. 第 4 步，展开 C，生成 E 排到队尾。注意此时 D 还在 E 前面，因为 D 比 E 早进队。
4. 第 5 步，展开 D，它的出边 D→E 指向已在表里的 E，不重复加入；D→F 生成 F，命中目标。

两个答案分开写：生成顺序是 A, B, C, D, E, F；本表实际展开到 D 就停止，E、F 未展开；解路径是 A → D → F。搜索树上 A 的孩子是 B、C、D，C 的孩子是 E，D 的孩子是 F，顺着 F 往上回溯父节点就得到解路径。生成顺序里的 B、C、E 都不在解路径上，答题时把这两样混在一起是常见扣分点。

变式题（先自己做）

还是练习题那张图（A→B、A→C、A→D、B→C、B→D、C→E、D→E、D→F、E→B、E→F），改用递归 DFS、孩子按字母升序取，仍找 A 到 F，进入节点时标记 visited。本题逐个递归邻居，不预先把全部兄弟放入 Open；不要混用前面 BFS 的 Open 查重规则。

(1) 写出访问顺序和解路径。(2) 和 p.9 降序的结果（解路径 A → D → F，只展开两个节点）对比，能得出什么结论、不能得出什么结论？(3) 若把 Close 表去掉，同样升序跑，会发生什么？

提示

升序意味着 A 的三个孩子里先取 B。走到 E 时它有两条出边，其中一条指向已经访问过的节点。第 (3) 问不必重算全程，找出图里那个能绕回来的环即可。

参考答案与自检（非官方评分标准）

自检要点：① 升序时从 A 先进的是 B 而非 D；② E 的出边里 E→B 指向已访问节点要跳过；③ 解路径要顺着父节点回溯写出，别拿访问顺序充数。

(1) A → B（升序最小）→ B 的孩子 C、D，取 C → C→E → E 的出边是 B 和 F，B 已访问，跳过，取 F，命中目标。访问顺序 A, B, C, E, F；解路径 A → B → C → E → F。

(2) 能得出的结论是 DFS 的结果完全取决于孩子的排列顺序——同一张图、同一个目标，降序展开两个节点、解路径长 2，升序展开四个节点、解路径长 4。推不出的结论是「DFS 比 BFS 快」或者「降序比升序好」：降序赢只是因为目标恰好挂在第一条分支上，换个目标节点结论就反过来。顺带一提，这条解路径也说明 DFS 找到的路径不保证最短。

(3) 去掉 Close 表后，E→B 那条边不再被跳过，于是走成 A → B → C → E → B → C → E → …，B、C、E 三个节点构成的环会被反复走下去，F 永远访问不到。这和 p.15 讨论题里 A → C → E → A 那个环是同一件事：环不必经过起点，任何一个能绕回来的圈都足以让无查重的 DFS 停不下来。

闪卡自测

1. Open 和 Close 各存什么？查重发生在哪一刻？

Open 存已生成、未展开的节点，Close 存已展开的节点。查重发生在生成的那一刻：展开某个节点时，它指向的节点若已在 Open 或 Close 里，就不再生成新条目（p.7）。

2. 练习题里展开 B 时，为什么一个新节点都没加进 Open？

B 的出边是 B→C 和 B→D，这两个节点在第 2 步展开 A 时就已经进了 Open，所以都不重复加入，这一步 Open 只减不增（p.7）。

3. 为什么 p.3 那棵树的 BFS 访问顺序恰好等于节点编号？

因为那张图本来就是按 BFS 顺序编号的，属于出题时的巧合。换一棵编号方式不同的树就对不上，不能当规律记（p.3）。

4. 用栈实现 DFS 时，想先访问 D 应该让 D 第几个入栈？

最后一个。栈是后进先出，最后入栈的最先被取出（p.8）。

5. 同一张图，BFS 展开了四个节点、DFS 只展开两个，这说明 DFS 更快吗？

不说明。DFS 这次快是因为目标恰好在降序的第一条分支上；把孩子顺序改成升序，它就要先钻 B 那条分支，展开数和解路径都变（p.9）。

6. DFS 走进死胡同后靠什么回溯？这和空间复杂度有什么关系？

靠栈里保留的、当前路径上每个节点尚未展开的兄弟节点。正因为要保留这些兄弟，它的空间是 O(d·b) 而非 O(d)（p.13）。

7. 加上 E → A 之后，无查重的 DFS 为什么走不到 F？

A → C → E → A 构成环，不查 Close 表时算法每次都把 A 当成新节点，于是无限循环，F 所在的那条分支永远轮不到（p.15）。

8. BFS 在有环的图上也会无限循环吗？

在有限分支、有有限深解时，BFS 不会因某个环而错过该解；但无解且有可达环时，不查重同样可能永不终止。

下一步

先把上面那道升序变式题在纸上重做一遍，两张表一起写——考卷要的就是这张表，脑内默算写不出得分点。再回去做 Lecture 2 p.32–33 那道二十二步的 DFS 手算题，手法和这里三道练习题完全一样，只是规模更大，正好用来练查重不出错。这份 tutorial 只覆盖了盲目搜索，启发式那半边（f = g + h 的 A* 手算）在 Lecture 2 p.61–67，题型一致但每一步要多算三个数，建议单独抽一次时间练。