PYTHON LESSON 094
真题精讲：传纸条的最远路程
精讲“树的直径”这一真题高频模型，掌握“邻接表存树、两遍 BFS 求直径”的完整套路。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- graph = [[] for _ in range(n+1)] 邻接表存树
- 无向边双向登记：graph[a] 与 graph[b] 都加
- 两遍 BFS：先找直径端点，再量直径长度
01 · 核心概念
树的直径与“两遍 BFS”套路
树的直径与“两遍 BFS”套路：第一遍从任意点（比如 1 号）出发，离它最远的点 x 必定是直径的一个端点；第二遍从 x 出发再跑 BFS，得到的最远距离就是直径。dist 全 -1 起手，既记步数又当访问标记，和第 7 课的迷宫 BFS 是同一把刀。
GESP Python 6 级 · 宽度优先搜索 BFSGESP Python 6 级 · 树的定义与构造有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
02 · 语法与规则
先记住这 3 条，再开始写程序
graph = [[] for _ in range(n+1)] 邻接表存树先准确读出这条写法的结构与作用。
无向边双向登记：graph[a] 与 graph[b] 都加换一组最小数据，手工推演一次结果。
两遍 BFS：先找直径端点，再量直径长度再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 真题精讲：传纸条的最远路程（树的直径，两遍 BFS）
from collections import deque
# 7 个班级连成一棵树，给出 6 条走廊
n = 7
edges = [(1, 2), (1, 3), (2, 4), (2, 5), (5, 6), (5, 7)]
graph = [[] for _ in range(n + 1)] # 邻接表存树，0 号位不用
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
def bfs(start):
dist = [-1] * (n + 1)
dist[start] = 0
queue = deque([start])
far = start
while queue:
u = queue.popleft()
if dist[u] > dist[far]:
far = u # 记录目前离起点最远的班级
for v in graph[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
queue.append(v)
return far, dist[far]
# 第一遍：从任意班级出发，最远的点一定是直径的一个端点
x, d1 = bfs(1)
# 第二遍：从这个端点再跑一遍，最远距离就是树的直径
y, diameter = bfs(x)
print("第一遍 BFS：从 1 班出发，最远的是", x, "班，距离", d1)
print("第二遍 BFS：从", x, "班出发，最远的是", y, "班，距离", diameter)
print("一张纸条最远要经过", diameter, "条走廊")第一遍 BFS：从 1 班出发，最远的是 6 班，距离 3 第二遍 BFS：从 6 班出发，最远的是 3 班，距离 4 一张纸条最远要经过 4 条走廊
点数比边数多 1 且连通就是树；树上“最远点对”的距离叫直径，两遍 BFS 是标准求法。
04 · 逐步理解
每一步只解决一个问题
- 01
真题长什么样
这类题通常给 n 个点、n-1 条边，问“最远的两个点相距几条边”。先识别模型：n 个点、n-1 条边且连通 = 一棵树；最远点对的距离 = 树的直径。六级常把它包装成传纸条、局域网、管道铺设等故事，换汤不换药。
- 02
存树：邻接表
树也是图，用邻接表存：graph[u] 列表里放所有与 u 相邻的点，下标从 1 开始对齐班级编号。注意每条无向边要在两边各登记一次——漏掉反向登记，BFS 就有去无回了。
for a, b in edges: graph[a].append(b) graph[b].append(a) - 03
套路核心：两遍 BFS
第一遍从任意点（比如 1 号）出发，离它最远的点 x 必定是直径的一个端点；第二遍从 x 出发再跑 BFS，得到的最远距离就是直径。dist 全 -1 起手，既记步数又当访问标记，和第 7 课的迷宫 BFS 是同一把刀。
x, d1 = bfs(1) y, diameter = bfs(x) - 04
为什么第一遍找到的是端点
直觉证明：假如从 u 出发的最远点不在某条最长路线的端点上，那它到真正端点的距离就比不上“端点到端点”，矛盾。考场上记住结论即可，但要能把这个理由复述给同桌听——讲得出来才算真懂。
- 05
编码细节与验证
bfs 返回两个值：最远点编号和最远距离；far 只在严格更远时才更新。验证靠手算：画出 7 班 6 条边的树，最远是 6 班到 3 班共 4 条走廊，和程序输出一致，才算吃透。
if dist[u] > dist[far]: far = u - 06
配套真题怎么练
题库 py-exam-l6-a2 就是“传纸条最远路程”的原题型；py-exam-l6-a1 考层序遍历输出全家福，同样是“存树 + BFS”的骨架。两题都独立做对，六级里树与搜索的大题分就稳了。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，说出两遍 BFS 各自的任务
- 2在纸上画出这棵班级树，标出直径
- 3加一条走廊 (3, 8)，预测新直径再核对
- 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 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
Python 基础条件、循环与程序流程准确理解 if、for、while、range、break、continue 和循环嵌套，而不是背代码模板。＋
正式定义
控制流决定下一条要执行的语句。分支依据布尔条件选择路径；循环在满足规则时重复执行代码块。Python 用冒号和缩进界定代码块。
必须掌握
- if/elif/else 从上到下判断，只执行第一个为真的分支；else 不写条件。
- for 依次取得可迭代对象中的元素；range(start, stop, step) 包含 start、不包含 stop，step 不能为 0。
- while 在每轮开始前检查条件；循环体必须让状态向终止条件推进。
- break 结束最内层循环，continue 跳过本轮剩余语句，循环的 else 仅在没有被 break 终止时执行。
- 嵌套循环的总执行次数通常需要把各层次数相乘；内层 break 不会结束外层循环。
- 边界测试至少覆盖空范围、单个元素、第一项命中、最后一项命中和始终不命中。
常见误区
- range 的右端点多算或少算一次
- while 忘记更新状态造成死循环
- 把两个互斥条件写成两个独立 if
- 误以为 break 会跳出所有嵌套循环
适用边界
- 流程图是算法的表示方法，不是 Python 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
算法方法算法、复杂度与解题验证把题意转成输入、状态、规则与输出，用正确性和复杂度共同评价解法。＋
正式定义
算法是解决一类问题的有限、明确步骤。正确性说明算法对所有满足前置条件的输入都得到规定结果；时间和空间复杂度描述输入规模增长时资源使用的增长量级。
必须掌握
- 先明确输入规模 n、数据范围、目标和允许误差，再选择数据结构与算法。
- O(1)、O(log n)、O(n)、O(n log n)、O(n²)、O(2ⁿ) 表示增长量级，不是精确运行秒数。
- 顺序代码复杂度取较大项，嵌套循环常相乘，二分每步把范围缩小一半。
- 正确性可用循环不变量、数学归纳、交换论证、反证或状态定义来说明。
- 样例只验证少量输入；必须自己设计边界、极端、重复、有序/逆序和无解数据。
- 优化前先得到正确基线并测量瓶颈，不为小数据盲目增加复杂实现。
常见误区
- 只看样例通过就宣称正确
- 不看数据范围使用 O(n²)
- 二分区间开闭混用
- 把 O(n) 当成永远比 O(log n) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
工程能力异常、文件、测试与调试读懂报错、缩小问题、设计测试，并安全地打开、读取和关闭文本文件。＋
正式定义
异常是在运行期间表示错误或特殊情况的对象。调试是用可复现输入和证据定位实际行为与预期行为差异的过程；文件对象连接程序与持久化字节数据。
必须掌握
- 先读 traceback 最后一行的异常类型与消息，再从最靠近自己代码的栈帧向上追踪。
- try 只包可能失败的最小代码；except 捕获具体异常；else 处理成功路径；finally 做必需清理。
- raise 主动报告不满足的前置条件；assert 用于开发期内部假设，不用于校验不可信用户输入。
- with open(...) as file 会在退出代码块时可靠关闭文件。文本模式必须明确编码，本站统一推荐 encoding='utf-8'。
- 测试至少包含正常值、边界值、空数据、极端值和反例；每个测试只应有明确目的。
- 定位错误时一次只改一个假设，保留能稳定复现问题的最小输入。
常见误区
- 使用 except: 吞掉所有错误
- 只测题目样例就认为程序正确
- 文本文件不写 encoding
- 修复报错表象却不验证根因
适用边界
- 在线判题的学生代码由独立 Worker 执行；文件系统、网络和资源权限必须受平台限制。
- 二进制文件、JSON/CSV 和数据库各有专门格式与错误处理方式，不能按普通文本随意拆分。
完成检查