PYTHON LESSON 105
考点精讲：距离表与连通块
把图的 DFS/BFS 从“会写”升级为“会用”：BFS 距离表解决无权最短路，扫描加遍历统计连通块。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- dist = [-1] * n 用 -1 表示“到不了”
- 入队时 dist[v] = dist[u] + 1 并立即标记
- 外层 for 扫描 + 内层 dfs 数连通块
01 · 核心概念
BFS 距离表与连通块计数的实战范式
BFS 距离表与连通块计数的实战范式：第 52 课我们学会了 DFS/BFS 的访问顺序，但考级不问“顺序是什么”，而是问“最少几步能到”“有几块互不相通”。本课把两种遍历改造成两件成品工具：BFS 距离表和连通块计数器。工具不大，却是七级图论题的万能钥匙。
GESP Python 7 级 · 图的 DFS 与 BFSGESP Python 7 级 · 无权图单源最短路GESP Python 7 级 · 连通块计数有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
02 · 语法与规则
先记住这 3 条，再开始写程序
dist = [-1] * n 用 -1 表示“到不了”先准确读出这条写法的结构与作用。
入队时 dist[v] = dist[u] + 1 并立即标记换一组最小数据，手工推演一次结果。
外层 for 扫描 + 内层 dfs 数连通块再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 图遍历进阶：BFS 距离表 + DFS 连通块计数
from collections import deque
n = 7
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (5, 6)]
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
# BFS 距离表：dist[v] 表示从 0 号到 v 的最短边数，-1 表示到不了
dist = [-1] * n
dist[0] = 0
queue = deque([0])
while queue:
u = queue.popleft()
for v in adj[u]:
if dist[v] == -1:
dist[v] = dist[u] + 1
queue.append(v)
print("从 0 号出发的距离表：", dist)
print("0 到 4 的最短距离：", dist[4])
# DFS 连通块计数：每发现一个没访问过的点，就染掉一整座“小岛”
visited = [False] * n
def dfs(u):
visited[u] = True
for v in adj[u]:
if not visited[v]:
dfs(v)
blocks = 0
for i in range(n):
if not visited[i]:
blocks += 1
dfs(i)
print("连通块个数：", blocks)从 0 号出发的距离表： [0, 1, 1, 2, 3, -1, -1] 0 到 4 的最短距离： 3 连通块个数： 2
BFS 按层扩展，每个点第一次到达时的距离就是最短距离；-1 表示到不了（5 号和 6 号自成一团）。
04 · 逐步理解
每一步只解决一个问题
- 01
主线课之后还差什么
第 52 课我们学会了 DFS/BFS 的访问顺序，但考级不问“顺序是什么”，而是问“最少几步能到”“有几块互不相通”。本课把两种遍历改造成两件成品工具：BFS 距离表和连通块计数器。工具不大，却是七级图论题的万能钥匙。
- 02
距离表：-1 的妙用
dist 数组身兼两职：既当访问标记，又存答案。-1 表示“还没到过”，一旦入队就写成 dist[u] + 1。省下一个 visited 数组，代码更短，考场上也更不容易漏写标记。
dist = [-1] * n dist[0] = 0 queue = deque([0]) - 03
为什么 BFS 的距离一定最短
队列保证先进先出：距离为 1 的点全部处理完，才轮到距离为 2 的点。所以任何点第一次被碰到时，走的边数一定最少。注意这个性质只对“每条边长度相同”的无权图成立，带权图的最短路要到八级学 Dijkstra。
- 04
连通块：扫描 + 染色
数连通块像数小岛：扫描每个顶点，发现一个没访问过的，说明找到一座新岛，计数加一，然后 dfs 把整座岛染遍。扫完全部顶点，岛数自然出来。本例中 0~4 是一座岛，5、6 是另一座，答案 2。
for i in range(n): if not visited[i]: blocks += 1 dfs(i) - 05
大数据的生存装备
顶点数到 10 万时三件事必须做：邻接表代替邻接矩阵、sys.stdin.buffer 一次性快读、递归 DFS 换成显式栈或调大递归上限。少任何一件，大数据点不是超时就是爆栈。
import sys sys.setrecursionlimit(10 ** 6) data = sys.stdin.buffer.read().split() - 06
考场速认题型
题目出现“最少经过几个人、几条边”——BFS 距离表；出现“是否连通、有几个部分”——连通块计数；出现“把整片区域染掉”——泛洪。先把题目归到类，再默写对应模板，七级图论题就是送分题。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行程序，读懂距离表里每个数字的含义
- 2找出距离表里的 -1，说说它们对应哪两位同学
- 3删掉边 (3, 4)，先预测 4 号的新距离再运行验证
- 4加一条边 (4, 5)，看连通块个数变成几
06 · 完整知识
继续理解定义、规则和适用边界
第一次学习先完成上面的六个步骤；需要查定义、核对规则、分析误区或理解“为什么”时，再展开对应知识章。
核心数据结构树、图、DFS、BFS 与最短路从节点与边的模型出发，掌握遍历、连通性、树结构、最小生成树和最短路径的适用条件。＋
正式定义
图由顶点和边构成；树是连通且无环的无向图。DFS 沿路径深入后回溯，BFS 按距离层次扩展。算法的正确选择取决于图是否有向、边权是否为负、是否稠密以及目标是遍历、连通还是最短路。
必须掌握
- 邻接矩阵占 O(V²) 空间，适合稠密图和快速查边；邻接表占 O(V+E)，适合稀疏图。
- DFS 常用递归或显式栈，BFS 使用队列；一般图都必须记录 visited 防止重复和死循环。
- 无权图的 BFS 首次到达即得到最少边数距离，可用 parent 还原路径。
- 树有 V-1 条边且任意两点路径唯一；二叉树前/中/后序描述根的访问时机。
- Dijkstra 只适用于非负边权；Floyd 求所有点对最短路并允许负边，但不能有可达负环。
- Kruskal 按边权排序并用并查集避环，得到连通无向带权图的最小生成树。
常见误区
- 遍历一般图时不记录 visited
- 对负权边使用 Dijkstra
- 混淆最短路径树与最小生成树
- 递归 DFS 忽略深度限制
适用边界
- 有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
- 网格搜索也是图搜索：格子是顶点，可移动关系是边；不要只背二维数组模板。
核心数据结构栈、队列、链表与并查集按访问顺序和更新需求理解线性结构，并掌握各操作的真实代价。＋
正式定义
栈按后进先出访问，队列按先进先出访问，链表用节点引用连接次序，并查集维护元素所属的动态不相交集合。数据结构的价值在于为特定操作提供清晰语义和复杂度保证。
必须掌握
- 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 没有课程必需的内置链表类型，教学实现用于理解指针关系；工程中应根据实际操作选择成熟容器。
- 并查集擅长连通性合并，不支持高效删除或一般最短路。
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 语法。
- 递归也能表达重复，但有调用开销和递归深度限制，不能无条件代替循环。
工程能力异常、文件、测试与调试读懂报错、缩小问题、设计测试，并安全地打开、读取和关闭文本文件。＋
正式定义
异常是在运行期间表示错误或特殊情况的对象。调试是用可复现输入和证据定位实际行为与预期行为差异的过程；文件对象连接程序与持久化字节数据。
必须掌握
- 先读 traceback 最后一行的异常类型与消息，再从最靠近自己代码的栈帧向上追踪。
- try 只包可能失败的最小代码；except 捕获具体异常；else 处理成功路径；finally 做必需清理。
- raise 主动报告不满足的前置条件；assert 用于开发期内部假设，不用于校验不可信用户输入。
- with open(...) as file 会在退出代码块时可靠关闭文件。文本模式必须明确编码，本站统一推荐 encoding='utf-8'。
- 测试至少包含正常值、边界值、空数据、极端值和反例；每个测试只应有明确目的。
- 定位错误时一次只改一个假设，保留能稳定复现问题的最小输入。
常见误区
- 使用 except: 吞掉所有错误
- 只测题目样例就认为程序正确
- 文本文件不写 encoding
- 修复报错表象却不验证根因
适用边界
- 在线判题的学生代码由独立 Worker 执行；文件系统、网络和资源权限必须受平台限制。
- 二进制文件、JSON/CSV 和数据库各有专门格式与错误处理方式，不能按普通文本随意拆分。
完成检查