T02 Tutorial 2:BFS 与 DFS 手算,把访问顺序和解路径分开
Open/Close 怎么填,孩子按什么顺序取,以及去掉查重之后 DFS 为什么停不下来。
一句话版
这份习题课把 BFS 和 DFS 手算一遍:在有向图上写出 Open/Close 两张表的变化、访问顺序和解路径。
先认识这几个词
读之前最好先懂盲目搜索的基本思路,见 L02a-2 BFS 和 L02a-3 DFS。
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 有向图 | directed graph | 点和带箭头的边组成的图,A→B 表示只能从 A 走到 B |
| BFS | Breadth-first Search,广度优先搜索 | 离起点近的一层全看完,再看下一层 |
| DFS | Depth-first Search,深度优先搜索 | 一条路走到底,走不通再退回来换路 |
| 展开 | expand | 取出一个节点,把它的箭头指向的邻居都列出来 |
| Open 表 / Close 表 | 待办清单 / 存档 | Open 放发现了还没展开的节点,Close 放已经展开过的 |
| 解路径 | solution path | 从起点到目标真正连起来的那条路 |
| O(d·b) | 读「大 O,d 乘 b」 | 内存大约跟「深度 d × 每个节点的孩子数 b」成正比 |
| 递归 | recursion | 函数在处理一个节点时再调用自己去处理它的邻居,处理完自动退回上一层 |
题目地图
全卷三道练习题加两道讨论题,前面还有一段回顾。它们共用一个动作:手动维护两张表。
| 题 | 题目 | 考什么 | 主要失分点 |
|---|---|---|---|
| 回顾 | 同一棵树的 BFS / DFS 顺序 | 两种扩展次序的对比 | 把节点编号当成访问顺序 |
| 练习 1 | 有向图上 BFS 找 A 到 F | Open 的查重 | 展开 B 时重复加入 C、D |
| 练习 2 | 同一张图 DFS,孩子按降序 | 孩子排列顺序的影响 | 没看清题目要求升序还是降序 |
| 练习 3 | 用 DFS 输出全部节点 | 回溯与 Close 表 | 漏掉「已访问就掉头」那几步 |
| 讨论 1 | 换一张小图,DFS 找 A 到 F | 死胡同后的回溯 | 走到 E 没退回去换分支 |
| 讨论 2 | 上图加一条 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 是队列(queue,先进先出):新节点加在队尾、从队首取。DFS 的 Open 是栈(stack,后进先出):加在栈顶,也从栈顶取。查重发生在生成的那一刻。展开一个节点时,它指向的节点若已经在 Open 或 Close 里,就不再生成新条目。答题表通常写成四列:步号、这一步展开谁、新生成什么、之后的 Open 长什么样。
常见误解
把查重当成可选的加速手段 → 它决定结果对不对。练习 1 第 3 步展开 B 时,B→C 和 B→D 指向的两个节点都已在 Open 里,一个新条目都不加。漏了这步会写成 Open = [C, D, C, D],后面每一行都错。
2. BFS:兄弟先于孩子(Breadth-first Search)
人话定义:BFS 用来保证离起点近的节点先被看到。做法是一层扩完再扩下一层,同层内按题目给的字母序处理。
例子:回顾题那棵树的结构是 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 顺序编号,换一张图就对不上了。
常见误解
把节点上印的数字当成访问顺序 → DFS 那张图用的是同一棵树,节点里的白色数字仍是编号,节点外的蓝色数字才是 DFS 访问顺序,两套数字并存。另一处是以为 BFS 在有环图上不用查重。它照样需要,只是不会像 DFS 那样顺着环一路钻下去,后果轻一些。
3. DFS:孩子先于兄弟,顺序由题目定(Depth-first Search)
人话定义:DFS 用来快速钻到深处,内存比 BFS 省。做法是一条路走到底,走不动了退回上一个还有未展开兄弟的节点,换下一条。
例子:回顾题的 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。练习 2 要求孩子按降序取,这是故意设的。DFS 的结果依赖孩子的排列顺序,做题前先确认题目要升序还是降序。
常见误解
用栈实现时把入栈顺序写反 → 栈是后进先出,想先访问 D 就要让 D 最后入栈。另一处是看到 DFS 展开的节点少就说它更快。练习 2 里 DFS 只展开 A、D 两个,BFS 展开了四个。原因是目标恰好落在降序的第一条分支上,改成升序结果完全不同。
4. 环与完备性(Completeness)
人话定义:完备性问的是「只要有解,算法一定能找到吗」。在有限但有环的图上,重复状态检查(看一眼 Close 表,来过就跳过)决定算法能不能停下来,也顺带减少重复工作。
例子:讨论 1 那张小图加上一条 E → A 之后,A → C → E → A 构成一个环(从某点出发能绕回自己的路)。去掉重复检查,DFS 从 A 走到 C 再到 E。E 的出边指回 A,算法把 A 当成新节点,于是又走 A → C → E → A,永远循环,F 永远访问不到。这印证了 Lecture 2 的结论:DFS 在有环的空间里会失败,不算完备;沿路径检查重复状态后,在有限空间里才完备。
常见误解
以为「可以重复访问」只是效率变差 → 它直接让算法不终止,解就在旁边也找不到。还有一处是把练习 3 答案图上的虚线当成没用的边。每条指向已访问节点的虚线都代表一次「查表发现来过了,掉头」,那正是 Close 表在工作。
逐题拆解
回顾:同一棵树的 BFS 与 DFS
BFS 顺序是 1 到 10 按编号走,DFS 顺序是 1, 2, 5, 9, 3, 6, 10, 7, 4, 8。逐步验算见上面概念卡 2、3。
练习 1:BFS(升序)找 A 到 F
关键在展开 B 那一步不重复加入 C、D,完整表格见下方完整例题。答案页还追问了一句:用 BFS 把全部节点输出一遍会怎样?课件没给答案。不设目标、照同样的查重规则走完,输出顺序是 A, B, C, D, E, F,和找 F 时的生成顺序一样。
一步一步看
目标:用队列按升序做 BFS,逐步展开到生成 F,看已在表里的节点怎样跳过,解路径怎样顺父节点读出。
图里灰色箭头是边的方向,青绿圈是这一步正在展开的节点。Open 是队列,左边先出。
-
起点 A 进队,Close 还是空的。
-
A 出队展开,三条出边生成 B、C、D,按升序排进队尾,A 进 Close。
-
B 出队展开。B→C、B→D 指向的节点都已在 Open 里,一个都不加,Open 只减不增。
-
C 出队展开,生成 E,排在 D 后面。
-
D 出队展开。D→E 指向已在表里的 E,跳过;D→F 生成 F,命中目标,停。顺着父节点往回读,解路径是 A → D → F。
练习 2:DFS(降序)
同一张有向图,找 A 到 F,孩子按字母降序取。A 展开出 B、C、D,降序先取 D。D 展开出 E、F,降序先取 F,F 就是目标,结束。解路径 A → D → F,只展开了两个节点。答案图上实线是真正走过(展开)的边,虚线是生成了但没展开的边。A→B、A→C、D→E 都是虚线。
一步一步看
目标:把 Open 换成栈按降序做 DFS,看 D 怎样先被取出,F 到手时 B、C、E 还没展开。
Open 换成栈,左边是栈顶。想先取 D,就让 D 最后入栈。
-
起点 A 入栈。
-
A 出栈展开,按 B、C、D 的次序入栈,D 落在栈顶。
-
D 出栈展开,E、F 入栈,F 在栈顶。
-
F 出栈,是目标,结束。B、C、E 还躺在栈里,从没被展开。
练习 3:用 DFS 输出全部节点
仍是降序,按递归写法,进入节点时就标记为已访问(visited)。这题不找目标,只把所有节点走一遍:
- A → D(降序最大)→ F。F 没有出边,是死路。
- 回到 D 取 E。E 的出边是 B 和 F,F 已访问,取 B。
- B 的出边是 C 和 D,D 已访问,取 C。C 的出边是 E,已访问,结束。
输出顺序是 A, D, F, E, B, C。
一步一步看
目标:按递归口径做降序 DFS 走遍全部节点,看哪几条边因为已访问被跳过,最后输出什么顺序。
这里按递归口径画:下方「路径」是从 A 到当前节点的那条链,「已访问」按进入先后排。若改用一次把全部兄弟压栈的写法,顺序会变成 A, D, F, E, C, B,两种口径别混。
-
进入 A,标记已访问。
-
A 的出边按降序先试 D,D 没来过,进入 D。
-
D 降序先试 F,进入 F。F 没有出边,是死路,退回 D。
-
回到 D 试下一条出边 D→E,进入 E。
-
E 的出边降序先试 F,已访问,跳过(虚线);再试 B,进入 B。
-
B 先试 D,已访问,跳过;再试 C,进入 C。
-
C 唯一的出边指向 E,已访问。C、B、E、D、A 依次退回,全部结束。青绿边是这次实际走过的 DFS 树,三条虚线各是一次「查表发现来过了,掉头」。
讨论 1:换图之后的回溯
新图小得多:A→B、A→C、B→C、B→D、C→E、D→F,仍是 DFS、降序、找 A 到 F。A 的孩子是 B、C,降序先取 C,再到 E。E 没有出边,是死路,回溯(退回上一个还有路可选的节点)。回到 A 取 B。B 的孩子 C、D 里 C 已访问,取 D,再到 F,找到。访问顺序 A, C, E, B, D, F;解路径 A → B → D → F。这题要看的是那次回溯。DFS 能从死胡同 E 退回 A 换分支,靠的是栈里留着路径上每个节点还没展开的兄弟。这也是它空间复杂度 O(d·b) 而非 O(d) 的来源。
一步一步看
目标:在换过的图上做 DFS,看走进死胡同后,栈里留下的 B 怎样成为回溯的退路。
Open 是栈,左边是栈顶。盯住第 4 步栈里剩下的那个 B。
-
起点 A 入栈。
-
A 出栈展开,B、C 入栈,降序要先取的 C 在栈顶。
-
C 出栈展开,生成 E。
-
E 出栈展开,没有出边,死胡同。栈里还留着 B,这就是回溯的退路。
-
B 出栈展开。B→C 指向的 C 已在 Close,不再生成;只生成 D。
-
D 出栈展开,生成 F。
-
F 出栈,是目标。Close 的顺序 A, C, E, B, D, F 就是访问顺序;顺着父节点读出解路径 A → B → D → F。
讨论 2:加一条边之后
只加 E → A,问「如果节点可以被重复访问会怎样」。答案是 A → C → E → A 循环到底,F 永远访问不到。一句话记住:Close 表是 DFS 能不能停下来的前提。BFS 在同一张图上也需要查重,练习 1 第 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 用栈时的入栈顺序;再把下面的「变式题」做一遍;最后回查两处最容易错的地方——展开时重复加入已在表里的节点、把访问顺序当成解路径。三步做完再往下看答案。
必背
- 同一棵树上 BFS 与 DFS 的访问顺序完全不同:BFS 兄弟先于孩子,DFS 孩子先于兄弟。
- 展开一个节点时,指向已在 Open 或 Close 里的节点的那些边不重复加入;漏掉这一步 Open 会长出重复项,后面整张表全乱。
- 访问顺序与解路径是两回事:访问顺序里的节点未必在解路径上,答题时两样都要写清楚。
- DFS 的结果取决于孩子的排列顺序,做题前先确认题目要求升序还是降序;用栈实现时,想先访问谁就让谁最后入栈。
- 同一张图上 DFS 比 BFS 少展开几个节点,只说明目标恰好在先选的那条分支上,推不出 DFS 更快。
- DFS 靠栈里保留的、路径上每个节点尚未展开的兄弟回溯,这是它空间复杂度 O(d·b) 而非 O(d) 的来源。
- 有环的图上去掉重复状态检查,DFS 会沿着环无限循环、永远到不了目标;有限有环图需要重复状态检查保证终止;树或无环图不必依赖 Close 表。
- 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 时命中目标,结束。逐步说明:
- 第 2 步,A 的三条出边生成 B、C、D,按字母升序排进队尾。
- 第 3 步是这道题唯一的考点。展开 B,它的出边 B→C 和 B→D 指向的两个节点都已经在 Open 里,所以一个新条目都不加,Open 只是把 B 出队。写成 [C, D, C, D] 的话,后面每一行都跟着错。
- 第 4 步,展开 C,生成 E 排到队尾。注意此时 D 还在 E 前面,因为 D 比 E 早进队。
- 第 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 都不在解路径上,答题时把这两样混在一起是常见扣分点。
变式题(先自己做)
改编自课件 p.8–9。还是练习题那张图(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,题型一致但每一步要多算三个数,建议单独抽一次时间练。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。