PYTHON LESSON 117
最小生成树：修路问题
理解最小生成树的贪心思想，掌握 Kruskal 算法 + 并查集的标准写法，解决连通所有点的最小代价问题。
00 · 学习目标
这一课要解决什么？
学完后，你应该能够
- edges.sort() 按边权从小到大贪心
- find(parent, x) 并查集查找根节点
- if ra != rb: 不在同一连通块才选这条边
01 · 核心概念
Kruskal 算法与并查集
Kruskal 算法与并查集：要在 n 个村庄之间修路让所有村庄互相可达，只需选 n−1 条路（选多了必有环，浪费钱）。所有选法中总费用最小的那套方案，叫最小生成树（MST）。电网、光缆、水管铺设都是同一个模型。
GESP Python 8 级 · 最小生成树（Kruskal）GESP Python 8 级 · 并查集有向无环图、拓扑排序、强连通分量和负权最短路是图论后续主题。
02 · 语法与规则
先记住这 3 条，再开始写程序
edges.sort() 按边权从小到大贪心先准确读出这条写法的结构与作用。
find(parent, x) 并查集查找根节点换一组最小数据，手工推演一次结果。
if ra != rb: 不在同一连通块才选这条边再用边界值或反例确认它的适用条件。
03 · 完整实例
代码、运行结果和解释放在一起看
# 修路问题：Kruskal 最小生成树，花最少的钱连通所有村庄
def find(parent, x): # 并查集：找 x 所在连通块的“村长”（根）
while parent[x] != x:
parent[x] = parent[parent[x]] # 路径压缩，下次更快
x = parent[x]
return x
edges = [ # (费用, 村庄a, 村庄b)
(2, 1, 2), (3, 1, 3), (4, 2, 3),
(5, 2, 4), (6, 3, 4),
]
n = 4 # 4 个村庄
parent = list(range(n + 1))
edges.sort() # 贪心：从最便宜的路开始考虑
total = 0
chosen = []
for cost, a, b in edges:
ra, rb = find(parent, a), find(parent, b)
if ra != rb: # 两个村庄还没连通，修这条路
parent[ra] = rb
total += cost
chosen.append((a, b, cost))
print("修路的方案:", chosen)
print("最少总费用:", total)修路的方案: [(1, 2, 2), (1, 3, 3), (2, 4, 5)] 最少总费用: 10
n 个点的生成树恰好选 n−1 条边；选中边为 (1,2)、(1,3)、(2,4)，费用 2+3+5 = 10。
04 · 逐步理解
每一步只解决一个问题
- 01
什么是最小生成树
要在 n 个村庄之间修路让所有村庄互相可达，只需选 n−1 条路（选多了必有环，浪费钱）。所有选法中总费用最小的那套方案，叫最小生成树（MST）。电网、光缆、水管铺设都是同一个模型。
- 02
Kruskal 的贪心策略
把所有路按费用从小到大排序，依次考虑：如果这条路连接的两个村庄还不连通，就修它；已经连通就跳过（修了会成环）。正确性依赖“切分定理”，初中阶段先记住这个贪心直觉即可。
edges.sort() for cost, a, b in edges: - 03
并查集：快速判断“连没连通”
parent[x] 记录 x 的上级，根节点的上级是自己。find(x) 一路向上找到根；两个点根相同就在同一连通块。初始时每个村庄自成一家：parent = list(range(n + 1))。
parent = list(range(n + 1)) print(find(parent, 1) == find(parent, 2)) - 04
路径压缩加速查找
find 里 parent[x] = parent[parent[x]] 让沿途节点跳级指向更靠近根的位置，下次查找近乎 O(1)。没有这行优化，大数据下会慢到超时——竞赛细节决定成败。
parent[x] = parent[parent[x]] x = parent[x] - 05
合并与计数
选中一条边就把两个根合并：parent[ra] = rb，同时累加费用、把边记入方案。一个实用检查：选够 n−1 条边就可以提前结束循环；选完不足 n−1 条说明图本身不连通。
if ra != rb: parent[ra] = rb total += cost - 06
Prim 也了解一下
Prim 从某个点出发，每次选“连接树内与树外”的最短边，适合点少边多的稠密图；Kruskal 按边排序，适合边不太多的稀疏图。GESP 阶段掌握 Kruskal 即可，两者结果相同。
05 · 练习与检验
自己写出来，才算真正学会
- 1运行规划师，核对最少费用 10
- 2给图再加一条边重新选路
- 3画出选中边组成的树，验证没有环
- 4解释为什么“选最便宜的且不成环”是对的
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) 慢固定倍数
适用边界
- 复杂度隐藏常数与硬件差异，但仍是比较规模增长的核心工具。
- 考场策略、课程完成度和算法能力是不同证据，任何单项都不能保证考级通过。
核心数据结构栈、队列、链表与并查集按访问顺序和更新需求理解线性结构，并掌握各操作的真实代价。＋
正式定义
栈按后进先出访问，队列按先进先出访问，链表用节点引用连接次序，并查集维护元素所属的动态不相交集合。数据结构的价值在于为特定操作提供清晰语义和复杂度保证。
必须掌握
- 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 没有课程必需的内置链表类型，教学实现用于理解指针关系；工程中应根据实际操作选择成熟容器。
- 并查集擅长连通性合并，不支持高效删除或一般最短路。
完成检查