PYTHON LESSON 100
图的遍历两条路
在邻接表上实现图的 DFS 与 BFS，理解两种遍历顺序的差异与访问标记的作用。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- visited = [False] * n 全图访问标记
- 递归 dfs(u)：标记后向每个未访邻居钻
- deque 队列 BFS：出队一个、邻居入队
01 · 核心概念
图的 DFS 与 BFS
图的 DFS 与 BFS：图和树的遍历代码几乎一样，唯一的新麻烦是：图里可能有环！0 的朋友是 1，1 的朋友又包括 0。没有 visited 标记就会绕圈转到天荒地老——所以图的遍历，标记就是生命线。
GESP Python 7 级 · 图的遍历GESP Python 7 级 · 图的 DFS 与 BFS有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
02 · 语法与规则
先记住这 3 条，再开始写程序
visited = [False] * n 全图访问标记先准确读出这条写法的结构与作用。
递归 dfs(u)：标记后向每个未访邻居钻换一组最小数据，手工推演一次结果。
deque 队列 BFS：出队一个、邻居入队再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 图的遍历两条路：DFS vs BFS
from collections import deque
n = 6
edges = [(0, 1), (0, 2), (1, 3), (1, 4), (2, 4), (3, 5), (4, 5)]
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
# 深度优先：一条道走到黑
visited = [False] * n
order_dfs = []
def dfs(u):
visited[u] = True
order_dfs.append(u)
for v in adj[u]:
if not visited[v]:
dfs(v)
dfs(0)
# 宽度优先：一层一层向外扩
visited2 = [False] * n
order_bfs = []
queue = deque([0])
visited2[0] = True
while queue:
u = queue.popleft()
order_bfs.append(u)
for v in adj[u]:
if not visited2[v]:
visited2[v] = True
queue.append(v)
print("邻接表：", adj)
print("DFS 顺序：", order_dfs)
print("BFS 顺序：", order_bfs)邻接表： [[1, 2], [0, 3, 4], [0, 4], [1, 5], [1, 2, 5], [3, 4]] DFS 顺序： [0, 1, 3, 5, 4, 2] BFS 顺序： [0, 1, 2, 3, 4, 5]
同一幅图：DFS 先钻进深处（0→1→3→5），BFS 则按“距离起点几层”依次访问。
04 · 逐步理解
每一步只解决一个问题
- 01
从树的遍历到图的遍历
图和树的遍历代码几乎一样，唯一的新麻烦是：图里可能有环！0 的朋友是 1，1 的朋友又包括 0。没有 visited 标记就会绕圈转到天荒地老——所以图的遍历，标记就是生命线。
visited = [False] * n - 02
图的 DFS
和树的 DFS 一个模子：进函数先标记、记录，然后对每个没访问过的邻居递归。差别只在“孩子”换成了“邻居列表”。在邻接表上，每个顶点、每条边最多被处理常数次，效率很高。
def dfs(u): visited[u] = True order_dfs.append(u) for v in adj[u]: if not visited[v]: dfs(v) - 03
图的 BFS
起点入队并立即标记；每次出队一个顶点，把它所有没标记的邻居标记、入队。BFS 序列里排在前面的点，离起点的“边数”一定不超过排在后面的——这个性质下一课和单源最短路还要用。
queue = deque([0]) visited2[0] = True while queue: u = queue.popleft() - 04
邻居顺序决定访问顺序
DFS/BFS 序列并不唯一：先访问哪个邻居，顺序就偏向哪边。题目若要求唯一答案，会规定“按编号从小到大访问邻居”，建表后给每个 adj[i] 排个序即可。
for i in range(n): adj[i].sort() - 05
两个序列读出的信息
DFS 序列 [0,1,3,5,4,2] 暴露了“钻到底”的脾气：0→1→3→5 一路深入；BFS 序列 [0,1,2,3,4,5] 则层次分明。会从一个序列反推图的结构，是图论题的进阶功夫。
- 06
大图别忘迭代
递归 DFS 遇到 10⁵ 个顶点的链式图会超出递归深度。两个对策：sys.setrecursionlimit(10 ** 6)，或者用显式栈改写。配套题目里的链式大数据就是专门考验这一点的。
stack = [0] while stack: u = stack.pop() if visited[u]: continue visited[u] = True
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，对比 DFS 与 BFS 的访问顺序
- 2给图再加一条边，预测两个序列怎么变
- 3手画 DFS 的“钻到底再回头”路线
- 4数一数每个点在 BFS 序列里的“层数”
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
程序组织函数、参数、返回值与作用域用明确的输入、输出和职责拆分程序，理解参数绑定、作用域、递归与可变对象。＋
正式定义
函数把一段可复用行为绑定到名字。调用时实参按规则绑定到形参，函数执行后用 return 交回结果；没有显式 return 时返回 None。名字解析遵循局部、闭包、全局、内置的 LEGB 顺序。
必须掌握
- 位置参数先于关键字参数；默认值在 def 执行时创建一次，不应直接使用可变容器作默认值。
- return 立即结束当前函数；return a, b 实际返回一个元组。
- 函数内赋值默认创建局部变量；global 声明模块级名字，nonlocal 声明最近外层函数名字。
- 传参传递的是对象引用；函数是否影响调用方取决于对象是否可变以及函数是否原地修改。
- 递归必须有可到达的终止条件，并要考虑调用深度、重复子问题和栈空间。
- 纯函数更容易测试；把输入输出、计算逻辑和全局状态分开能显著减少错误。
常见误区
- 可变默认参数在多次调用间共享
- 忘记 return 导致得到 None
- 局部变量遮蔽全局同名变量
- 递归没有缩小问题规模
适用边界
- lambda 只能包含一个表达式，适合短小的排序键，不适合塞入复杂业务逻辑。
- 装饰器、生成器和闭包属于函数模型的进阶应用，应在基本参数与作用域稳定后学习。
核心数据结构栈、队列、链表与并查集按访问顺序和更新需求理解线性结构，并掌握各操作的真实代价。＋
正式定义
栈按后进先出访问，队列按先进先出访问，链表用节点引用连接次序，并查集维护元素所属的动态不相交集合。数据结构的价值在于为特定操作提供清晰语义和复杂度保证。
必须掌握
- Python list 的尾部 append/pop 可作栈，均摊 O(1)。
- 队列应使用 collections.deque 的 append/popleft，避免 list.pop(0) 的 O(n) 搬移。
- 循环队列用固定数组、队首队尾下标和取模复用空间，必须约定空与满的判定。
- 单链表节点保存值和 next；已知前驱时插入删除 O(1)，按下标查找仍是 O(n)。
- 并查集的 find 找代表元，union 合并集合；路径压缩与按大小/秩合并使均摊代价近似常数。
- 选择结构前先列出最频繁操作：随机访问、两端操作、按键查找或集合合并。
常见误区
- 用 pop(0) 实现大规模队列
- 空栈空队列仍然弹出
- 链表改指针时丢失后续节点
- 并查集只改父节点却不理解代表元
适用边界
- Python 没有课程必需的内置链表类型，教学实现用于理解指针关系；工程中应根据实际操作选择成熟容器。
- 并查集擅长连通性合并，不支持高效删除或一般最短路。
核心数据结构列表、元组、字典与集合按顺序、可变性、唯一性和查找需求选择容器，并掌握遍历、推导式、排序与复制。＋
正式定义
容器保存多个对象。list 是可变有序序列，tuple 是不可变有序序列，dict 保存唯一键到值的映射，set 保存无序且不重复的可哈希对象。
必须掌握
- list 支持下标、切片、append、extend、insert、pop、remove 与 sort；多数修改方法返回 None。
- tuple 的逗号比括号更关键，单元素元组必须写成 (value,)。
- dict 保持插入顺序；键必须可哈希且唯一，get 可提供缺省值，items 同时遍历键和值。
- set 用于去重与集合运算：| 并、& 交、- 差、^ 对称差；空集合必须写 set()。
- enumerate 同时给出序号和值，zip 并行遍历多个可迭代对象，默认在最短输入处停止。
- 浅复制只复制最外层容器；嵌套可变对象仍可能共享。
常见误区
- 把 list.sort() 的返回值赋回列表
- 遍历 dict 时同时改变其大小
- 用可变 list 当字典键
- 把 set 当成有固定顺序的序列
适用边界
- 大量从队首删除时 list.pop(0) 是 O(n)，应使用 collections.deque。
- 需要有序映射的特殊操作、计数或默认值时可查阅 collections，但先理解基本 dict。
完成检查