MST 增量更新：为什么只需保留旧的最小生成森林

给定一张无向带权图，已经求出了它的一棵 MST。现在加入一批新边，重新求 MST 时，还需要保留那些上次没选中的旧边吗？

只要旧边不删除、不改权，就可以把全部旧边压缩成一棵旧 MST。 如果旧图不连通，则保留各个连通分量的 MST，合起来称为最小生成森林。

算法背景与实现见：最小生成树。本文只讨论为什么这次压缩不会丢掉最优解。

命题与适用条件

固定点集 $V$，旧边集为 $E$，新增边集为 $S$。边权可以重复、可以为负；允许重边，边以各自的身份区分。自环不能属于生成森林，以下先将自环忽略。

记 $\operatorname{MSF}(E)$ 为旧图的一份最小生成森林的边集：在每个连通分量内取一棵 MST，孤立点仍保留在点集 $V$ 中。记 $w(F)$ 为边集 $F$ 的权值和。

任取一份 $F=\operatorname{MSF}(E)$，都有：

$$w\bigl(\operatorname{MSF}(E\cup S)\bigr) =w\bigl(\operatorname{MSF}(F\cup S)\bigr).$$

而且两张图的连通分量完全相同。因此，当新图连通时，两边都可以写成 MST；旧图本身不必连通。

若旧图连通，令 $T$ 为它的任意一棵 MST，就是原命题的常用形式：

$$w\bigl(\operatorname{MST}(E\cup S)\bigr) =w\bigl(\operatorname{MST}(T\cup S)\bigr).$$

等号比较的是最小权值，不要求两次算法选出完全相同的边。

先抓住替代路径

取一条被舍弃的旧边 $e=(u,v)\in E\setminus F$。因为 $u,v$ 在旧图的同一连通分量内，旧森林 $F$ 中有唯一的 $u$ 到 $v$ 路径，记为 $P$。

这条路径上，每条边 $f$ 都满足：

$$w(f)\leqslant w(e).$$

理由只有一次换边：如果 $P$ 上某条边比 $e$ 更重，那么在旧森林中加入 $e$、删掉那条更重的边，就能让同一连通分量的生成树变轻，与 $F$ 最优矛盾。

所以，舍弃 $e$ 时，我们已经保留了一条连接相同两端的路径，且路径上的每条边都不比 $e$ 贵。后续只加入新边，这条旧路径依然存在，边权也没有变化。

证明：断开一条，再接回一条

先看连通性。压缩图 $F\cup S$ 是完整图 $E\cup S$ 的子图，当然不会额外连接原本不连通的点。反过来，任何被删掉的旧边，都可以用上面的旧森林路径替代。因此完整图里的每条路径，在压缩图中也有对应的走法，两张图的连通分量相同。

下面先假设新图连通。

设完整图的一棵 MST 为 $T_*$。如果 $T_*$ 已经只用了 $F\cup S$ 中的边，就已经找到我们需要的最优树。

否则，选一条 $e=(u,v)\in T_*\setminus(F\cup S)$。它必然是一条被压缩舍弃的旧边。

1. 断开。 从 $T_*$ 中删掉 $e$，树分成两块 $A,B$，其中 $u\in A$、$v\in B$。
2. 找桥。 旧森林中的路径 $P$ 从 $u$ 走到 $v$，一定有一条边 $f$ 跨过 $A,B$。它不在 $T_*-e$ 中，否则这两块就没有断开。
3. 接回。 加入 $f$，得到生成树 $T'=T_*-e+f$。由替代路径的性质，

$$w(f)\leqslant w(e) \quad\Longrightarrow\quad w(T')=w(T_*)-w(e)+w(f)\leqslant w(T_*).$$

$T_*$ 本来已经最优，所以只能取等号。$T'$ 仍是完整图的一棵 MST，但少用了一条被舍弃的旧边，补入的边则属于 $F$。

每次交换都让 $T_*\setminus(F\cup S)$ 的大小减少一，重复有限次后，就得到一棵完全位于压缩图中的 MST。

最后把两个方向合起来：

• 压缩图可选边更少，其最优权值不可能小于完整图。
• 压缩图已经包含一棵完整图的 MST，其最优权值不可能更大。

因此两者相等。

如果新图不连通，在每个连通分量内进行同样的交换即可。替代路径不会走出该分量，各分量的最优权值分别不变，相加便得到最小生成森林版本。

同权边为什么不影响结论

例如三角形的三条边权都为 $1$。旧 MST 可以保留其中任意两条，第三条被舍弃。

被舍弃的边仍然可能属于另一棵 MST。压缩所保证的是：至少保留一份最优解，足够求最优权值或输出一份方案。 它不保留所有最优方案，也不能用来统计原图的 MST 数量。

证明从始至终只用了 $w(f)\leqslant w(e)$，允许等号，因此任意一份旧最小生成森林都可以作为压缩结果，不需要固定同权边的排序方式。

分批加边时怎样使用

每次加入新的一批边 $S$ 后，在旧森林 $F$ 与 $S$ 的并集上重新运行 Kruskal，把选中的原边保存为新的森林：

F = empty edge set
for each batch S:
    candidates = F + S
    reset DSU for all vertices
    sort candidates by weight
    F = empty edge set
    for edge in candidates:
        if merge(edge.u, edge.v):
            append edge to F
    if size(F) == n - 1:
        report sum of weights in F
    else:
        report no spanning tree yet

这里保存的是选中的原边，不是并查集的父亲指针，也不能只保存权值和。点集中的孤立点即使没有边，也不能省掉。

如果本批有 $k$ 条新边，旧森林最多有 $n-1$ 条边，因此只需排序至多 $n-1+k$ 条候选边。使用路径压缩和按大小合并，一次重算的时间可写为 $O((n+k)\log(n+k+1))$，空间为 $O(n+k)$。

这减少了反复处理的历史边数，但不是每次更新 $O(\log n)$ 的动态 MST 算法。

为什么不能直接沿用旧并查集

旧 MST 有边 $(1,2,1)$ 和 $(2,3,5)$，权值和为 $6$。现在加入新边 $(1,3,2)$，新 MST 应改选权值为 $1$ 和 $2$ 的两条边，答案变成 $3$。

但旧并查集里三个点早已连通，直接追加新边只会判定“形成环”并跳过它。旧边虽然仍可作为候选，却不再是必须保留的选择。因此上面的流程需要重置并查集，让新边与旧树边一起竞争。

删边和改权为什么不能直接套用

考虑旧三角形：$w(1,2)=1$、$w(2,3)=2$、$w(1,3)=3$。旧 MST 保留前两条边，舍弃权值为 $3$ 的边。

• 若之后删除 $(2,3)$，原图仍能通过 $(1,3)$ 连通，但压缩图已经丢掉这条备用边。
• 若把 $(2,3)$ 的权值增大到 $100$，新 MST 应选权值为 $1$ 和 $3$ 的边，只保留旧树仍会漏解。

这两种操作都破坏了证明所依赖的“旧替代路径始终存在，且边权不变”。需要处理删边或改权时，应另外证明维护方法，不能直接沿用只加边的压缩结论。