动态最小生成森林

三种更新模型与查询 ​

维护固定顶点集上的无向带权图 $G=(V,E,w)$。Incremental MSF 只插边，decremental MSF 只删边，fully dynamic MSF 同时允许 insert/delete；边实例与权重必须在更新接口中明确。

输出状态是一片最小生成森林公理库最小生成树Minimum spanning tree · MST连通加权图中总边权最小的生成树及其算法问题。 $F$。常见查询包括 connected$(u,v)$、某边是否在 $F$、分量或全图 MSF 总权，以及路径最大边。更新时间、查询时间、空间和保证类型要分开报告。

本页固定经典 Holm–de Lichtenberg–Thorup（HDT）确定性框架：一般比较/RAM 实现可给 fully dynamic update 摊还 $O({\log }^{4}n)$；若维护森林总权，读取总权为最坏 $O(1)$，用动态树回答连通或路径查询可取最坏 $O(\log n)$，空间 $O(n+m)$ words。这里不把后续随机化或更优结果混入同一成本表。

插边：环性质给出局部替换 ​

插入 $e=(u,v,w_e)$ 时，若 $u,v$ 原本不连通，$e$ 必加入森林并合并两分量。若已连通，$e$ 与森林路径 $P_F(u,v)$ 形成唯一环；设 $f$ 是路径上最重边。

若 $w_e<w_f$，用 $e$ 替换 $f$ 会降低总权；若 $w_e\ge w_f$，环性质说明可以保留原森林。相等时需固定 edge-id tie-breaking，才能让维护对象确定且更新可复现。

支持 path-max 的动态树可在 $O(\log n)$ 找到 $f$，所以 incremental 情形相对直接。它不需要在全图扫描替代边。

删树边：最轻 Replacement Edge ​

删除非树边不改变 $F$。删除树边 $f$ 会把一棵树分成 $A,B$；若仍有跨割边，新的 MSF 必须选择

$$e^{\ast }=\arg min\{w(e):e\in E\setminus F,e\in \delta (A)\}.$$

这里只找到“任意跨割边”不足够。全动态连通性公理库全动态连通性Fully dynamic connectivity · Dynamic graph connectivity以分层生成森林和 replacement-edge 搜索维护在线边插入删除下的无向图连通性，并用边层级单调提升证明多对数摊还更新界。可以用第一条候选恢复连通，却可能选到很重的边；动态 MSF 必须维护按权比较的最小候选及其失效处理。

层级框架与摊还来源 ​

HDT 把边放入 $O(\log n)$ 个单调层级，并维护一族嵌套生成森林及受限大小的 clusters。删除树边后从相关层级搜索较小一侧，过滤已经成为内部边的候选，并把失败候选提升或重新归类。

对 MSF，还要在每个层级/cluster 中维护候选边的权序，并在 forest replacement 后更新哪些边是 tree/non-tree。一次候选检查调用动态树或局部搜索的多对数操作；每条边只能跨越 $O(\log n)$ 个层级，嵌套记账给出经典 $O({\log }^{4}n)$ 摊还更新界。

这不是单次最坏界：一次删除可能暴露许多失效候选，成本由它们以后不再停留在原状态偿还。若允许边层级任意下降或同一失败边反复回到同一候选表，摊还证明即失效。

四边形真例 ​

图有边

$$ab:1,bc:2,cd:3,da:4,ac:10.$$

初始 MSF 为 $ab,bc,cd$，总权 $6$。删除树边 $bc$ 后，森林分成 $\{a,b\}$ 与 $\{c,d\}$；跨割非树边为 $da$ 与 $ac$，必须选较轻的 $da:4$，新总权为 $8$。只做 connectivity replacement 若先遇到 $ac:10$，虽恢复连通，却得到非最优树。

随后插入 $bd:1.5$，它与森林路径 $b-a-d$ 形成环，路径最重边是 $da:4$；替换后总权降为 $5.5$。这展示插入的 path-max 与删除的 cut-min 是两种不同搜索。

边界与近邻问题 ​

权重改变可建模为删除旧边实例再插入新权边，但这会触发两次更新时间。顶点插删、动态图最短路、动态二边连通都有不同状态和证书。

负权不妨碍 MST cut/cycle 性质；有向图则对应最小树形图，不能使用同一替代边论证。多重边必须保留实例身份，相等权边必须固定 tie-break，否则“该边是否在 MSF”没有唯一答案。

参考资料

• Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup, “Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity,” Journal of the ACM 48(4), 2001.
• David Eppstein et al., “Sparsification—A Technique for Speeding Up Dynamic Graph Algorithms,” Journal of the ACM 44(5), 1997.
• Monika R. Henzinger and Valerie King, “Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation,” Journal of the ACM 46(4), 1999.