01先把问题说具体
三个城市之间铺线路,边 AB=1、BC=2、AC=4。要全部连通且总造价最小,应选哪些线路?
02一步步得到方法
先分清优化目标
生成树包含所有 V 个节点、恰好 V−1 条边、连通且无环。最小生成树最小化选中边权总和,通常针对无向图。它不保证任一源点到其他点的路径都最短。
若图不连通,不存在覆盖全图的生成树,但可求各分量的最小生成森林。边权可以为负;只要目标是选一棵树,不会无限绕负环。
割性质为什么让贪心可靠
把节点分为两组叫一个割,跨两组的边叫跨割边。若当前已选森林没有边跨这个割,则选择一条最轻跨割边是安全的:存在某棵最小生成树包含当前森林与这条边。
交换论证:若某棵最优树不含这条边,加进去会产生环;环上必有另一条跨割边,权重不小于所选边。删掉那条边后仍是树,成本不增加。Kruskal 与 Prim 用不同方式寻找这样的安全边。
边总重与根路径是不同目标
MST 连接全部节点且不成环,最小化选中边的总重。它不指定起点,也不承诺某个根到每个点的路径最短。先写清目标,才能判断应该用 MST 还是最短路。
负边权不破坏 MST 定义,环和连通性才是关键。若原图不连通,就不存在覆盖所有节点的一棵生成树;可以求最小生成森林,并显式说明输出已变。
03把一个小例子完全算清楚
AB=1、BC=2、AC=4。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 枚举 AB、BC | 连通无环,总重 3 | 候选生成树 |
| 枚举 AB、AC | 总重 5 | 比 3 更大 |
| 枚举 BC、AC | 总重 6 | 最优选 AB、BC |
窄屏可左右滑动表格,阅读完整计算与理由。
下面的穷举程序只用于小图建立定义和独立参考答案,后两课才给高效算法。
04为什么这个方法成立
- V−1 条边若连通就必无环,因此可以用它验证生成树。
- 枚举所有 V−1 边子集不会漏掉任何生成树。
- 从合法候选中取最小总权重,恰好满足 MST 定义。
05把推导翻译成代码
Python · 可独立运行的教学实现
from itertools import combinations
def tiny_mst(n, edges):
if n <= 1:
return 0
answer = float("inf")
for chosen in combinations(edges, n-1):
adj = [[] for _ in range(n)]
for u,v,w in chosen:
adj[u].append(v); adj[v].append(u)
seen, stack = {0}, [0]
while stack:
for v in adj[stack.pop()]:
if v not in seen:
seen.add(v); stack.append(v)
if len(seen) == n:
answer = min(answer, sum(w for u,v,w in chosen))
return None if answer == float("inf") else answer逐个理解关键决定
combinations(edges, n-1)- 只枚举树可能拥有的边数,但仍需验证连通。
len(seen) == n- 防止把一个有环分量加孤立点误认为生成树。
06时间、空间与实现范围
穷举约 C(E,V−1) 个候选,每次检查 O(V+E) 上界,仅适合微型图与校验。
后续 Kruskal、Prim 将利用割性质降低成本;不要把这里的穷举复杂度当作 MST 问题的必要代价。
07改变条件,检查哪里会出错
将 MST 当成最短路径树
MST 优化边总和;最短路径树优化源点到各点的距离,目标不同。
把 n−1 条边当作连通的充分条件
还需保证无环或独立验证连通性;任意 n−1 条边可能带环且遗漏节点。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
边 AB=2、BC=2、AC=3,MST 中 A 到 C 路径一定最短吗?
需要一点提示
MST 选哪两条?
查看解析与答案
MST 选 AB、BC,总重 4,但树上 A→C 为 4,原图直接边是 3。
等权边会使答案不唯一吗?
需要一点提示
三角形三条边都为 1。
查看解析与答案
会,任选两条都是总重 2 的 MST。
负权边是否禁止?
需要一点提示
树不能重复绕环。
查看解析与答案
不禁止,Kruskal、Prim 都可处理负边;和 Dijkstra 的前提不同。