学习顺序主线第 19 / 22 课 · 阶段 6

为什么现在学:换成后进先出,观察搜索顺序改变了什么、没改变什么。

返回算法课程
图与搜索基础

深度优先搜索Depth-First Search

沿一条分支尽可能深入,再回到尚未探索的分支。

40 分钟前置:栈 · 图的邻接表

学完这一课,你应该能做到

  • 解释栈如何把新分支排在最前面
  • 看懂重复入栈与弹出判重
  • 用具体反例区分可达与最短

01先从一个问题出发

检查迷宫里哪些房间能到达。先沿走廊深入,碰到尽头再回到岔路。

一个具体的例子

与 BFS 同一张图。栈从左到右表示栈底到栈顶,右端弹出。

换成栈,先走最新发现的分支

仍用 0–1、0–2、1–3、2–3 这张图。0 发现 1、2 后,栈让最后压入的节点先被处理。为了先访问较小编号,示例先压 2 再压 1。于是顺着 0→1→3→2 深入,而不是先把 0 的所有邻居都处理完。

递归版本依靠语言调用栈记住返回位置;本课用显式栈保存待探索节点,便于在动画里展示。两者都体现深入后回到尚未探索分支的思想,但访问次序还受到邻居排列与标记时机影响。

本课为什么允许栈里有重复项

这里在弹出一个未访问节点时才把它加入 visited。0 先把 2 压入栈,之后从 3 又发现尚未被弹出的 2,因此栈中可能同时有两个 2。先弹出的那次真正展开它,后一次看到 visited 后直接跳过。

因此必须把『入栈』与『真正访问并展开邻居』区分。若选择入栈时标记,可以避免重复待处理项,但那是另一种标记约定,不能只删掉弹出判重语句而保持其他代码不变。

02最直接的办法,为什么慢?

不记忆访问历史,不断递归探索所有邻居。

暴力 · 有环时可能不终止

一旦遇到环,就会重复走回同一节点,甚至永不终止。

03一步步,推导出优化思路

1

记住已经展开的节点

探索过的节点无需反复展开,用 visited 保存信息。

2

用栈保存尚未探索的分支

用递归调用栈,或显式后进先出栈,保存待探索节点。

3

弹出判重后再深入

本课用显式栈并在弹出时判重;逆序压邻居使小编号优先访问。

贯穿算法的不变量

只有尚未访问的节点会真正展开邻接表,每个节点至多展开一次。

拿一个小输入,逐步手算

与 BFS 同一张图。栈从左到右表示栈底到栈顶,右端弹出。

动作栈真正访问顺序说明
初始化[0][]起点待访问
弹出 0,逆序压邻居[2,1][0]1 将先弹出
弹出 1,压入 3[2,3][0,1]继续深入
弹出 3,压入 2[2,2][0,1,3]2 还没真正访问
弹出一个 2[2][0,1,3,2]标记并展开
弹出另一个 2[]不变已访问,跳过

访问顺序为 0、1、3、2。待处理栈里出现两个 2 并不是动画错误,而是本实现延迟判重的结果。

为什么能覆盖所有可达节点并终止

  1. 起点进入栈。真正展开一个节点时,把尚未访问的邻居安排进栈,所以沿任意可达路径都有机会继续向前。
  2. visited 保证每个节点最多真正展开一次,即使重复入栈也不会反复展开邻接表。
  3. 有限图中只有有限次邻居检查与入栈动作,栈最终耗尽。若有可达节点未访问,在从起点到它的路径上总有一条已访问到未访问的边,与展开时安排邻居矛盾。

04让每一步,都看得见

试着先预测下一步,再点击「下一步」验证。变量、动画与代码会同步变化。

Depth-First Search交互演示
STEP 01 / 15
0123
无向图 · 源点 0 · 邻居按编号处理
当前处理已处理 / 已确定未处理
01

从节点 0 开始:栈顶在右侧,弹出未访问节点后标记。

dfs.py参考实现 · 当前第 2 行
正在载入代码编辑器…

动画展示参考实现的执行轨迹。切换语言时,当前操作会定位到对应代码行。

代码里的每个关键决定

node = stack.pop()
取最新安排的节点。这个顺序决定深入探索,与 BFS 的 popleft 不同。
if node in visited:
必须在展开邻居之前判重;本例的第二个 2 就会在这里被跳过。
for neighbor in reversed(graph[node]):
先压较大编号,后压较小编号,使较小编号先弹出。这是演示顺序约定,不是 DFS 必须按数字大小运行。

05复杂度,来自具体的工作量

时间复杂度
O(V+E)O(V+E)

每个节点真正展开一次,所有邻接表总长度 O(E),重复弹出仍不超过入栈次数。

辅助空间
O(V+E)O(V+E)

本课在弹出时判重,同一节点可重复入栈,栈最坏 O(E),visited 为 O(V)。递归 DFS 或入栈判重的版本可做到辅助空间 O(V)。

拖动 n,看看增长速度

把工作量具体数出来

每个节点只真正展开一次,全部邻接项共 O(E);重复弹出次数也受入栈次数约束,因此总时间 O(V+E)。

本课弹出时判重,栈可能同时保存重复候选,最坏 O(E),加上 visited 为 O(V+E) 辅助空间。不能套用另一个实现的 O(V) 栈结论。

递归 DFS 或入栈时判重的版本可以用 O(V) 辅助空间;深链上的递归还可能触发语言递归深度限制。

06看到什么,应该想到它?

这些特征值得停下来想一想:

关键词只是线索,继续检查适用条件

07这些细节,容易踩坑

01

记得处理环

图的 DFS 需要 visited;树上也要避免沿无向边回到父节点。

02

DFS 不保证最短

首次到达只表示找到一条路,并不保证边数最少。

用反例检查前提

第一次走到并不意味着路径最短

图中有直接边 0–2,但按本课顺序,DFS 先沿 0→1→3→2 到达 2,经过三条边。最短路线 0→2 只要一条边。

怎样修正:DFS 回答可达性、连通分量和结构探索;无权最短路用 BFS。若需要回溯枚举路径,还必须区分路径内标记与全局访问标记。

08把想法带进真实题目

合上答案,自己推一次

为什么孤岛需要外层循环

在本课图中增加一个没有任何边的节点 4,从 0 做一次 DFS 会访问 4 吗?要统计全图连通分量,应该加什么步骤?

需要一点提示

搜索只能沿已有边向外推进。

查看完整推导与答案
  1. 不会,4 不在 0 的可达范围内。
  2. 用外层循环检查每个节点;遇到尚未访问的节点,就启动一次 DFS,并把分量计数加一。
  3. 这张图有两个连通分量:{0,1,2,3} 和 {4}。搜索过程中应共享 visited,避免重复计数。

完成上面的手算练习,再把思路迁移到这些题目。

09不用背模板,回答这几个问题

01显式 DFS 用什么结构?

02DFS 首次找到的路径一定最短吗?

03为什么弹出后还要检查 visited?

你已经走完了这次推导。

能用自己的话解释复杂度和不变量,再标记为掌握。

把知识连起来

继续阅读

本课例子与推导为本站编写。需要另一种表述或进一步学习时,可对照这些公开课程与文档:

MIT 6.006 · 算法讲义Princeton Algorithms · 课程资料

能独立完成本课练习,再标记掌握。也可以直接用上面的链接继续学习。