专题进阶 · 图算法推荐总顺序 · 第 78 / 148 课

区分连通网络的总成本与单源最短路,用割性质理解安全加边。

先学会这些,再进入本课 图的表示 贪心思想 并查集
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 图算法

最小生成树Minimum Spanning Tree

在连通无向加权图中,用最小总权重连接所有节点且无环。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

区分连通网络的总成本与单源最短路,用割性质理解安全加边。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. V−1 条边若连通就必无环,因此可以用它验证生成树。
  2. 枚举所有 V−1 边子集不会漏掉任何生成树。
  3. 从合法候选中取最小总权重,恰好满足 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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

边 AB=2、BC=2、AC=3,MST 中 A 到 C 路径一定最短吗?

需要一点提示

MST 选哪两条?

查看解析与答案

MST 选 AB、BC,总重 4,但树上 A→C 为 4,原图直接边是 3。

练习 2 · 边界与辨析

等权边会使答案不唯一吗?

需要一点提示

三角形三条边都为 1。

查看解析与答案

会,任选两条都是总重 2 的 MST。

练习 3 · 变式与迁移

负权边是否禁止?

需要一点提示

树不能重复绕环。

查看解析与答案

不禁止,Kruskal、Prim 都可处理负边;和 Dijkstra 的前提不同。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 图算法

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。