动态最小生成森林

形式陈述 ​

三种更新模型与查询 ​

在动态图更新协议理路动态图算法模型Dynamic graph algorithm model统一图更新序列、查询接口、对手权限以及更新和查询保证。下，维护固定顶点集上的无向带权图 $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）确定性结果：对从空边集开始的无向简单图，边插入、删除的摊还时间为 $O({\log }^4(n+1))$。原论文实现先构造仅删边结构，再通过分层重建归约支持插入；其空间按各层副本计，可保守写为 $O((n+m)\log (n+1))$ words，包含孤立顶点。这个空间界属于整套 MSF 结构，不能沿用单棵动态树的线性空间。

维护一个全局森林总权即可最坏 $O(1)$ 读取；原论文采用确定性Top Tree理路Top TreeTop tree · Top-tree dynamic forest把动态树递归分解为边界顶点至多两个的 cluster，并以 join、split 与 expose 在对数层级中维护路径及整树摘要。支持最坏 $O(\log (n+1))$ 的连通与路径最大边查询。若另外选用普通伸展树版 Link–Cut Tree，相应路径操作只有摊还对数界。算术、权比较和固定大小摘要按单位成本计；非空初始图的构建成本须另计。

为使选择确定，可按 $(w(e),\mathrm{id}(e))$ 的字典序比较全部边；以下“更轻／更重”均按这个次序。它在不改变最小总权目标的前提下选定一份唯一森林。若只需维护任一最优森林，同权时保留旧边也正确，其成员查询仍以当前实际保存的森林为准。

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

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

若 $e$ 比 $f$ 更轻，就用 $e$ 替换 $f$；数值权严格更小时总权降低，同权时只按固定编号规范化选择。否则环性质允许保留原森林。

选定上述最坏对数保证的 Top Tree 后，可在 $O(\log (n+1))$ 找到 $f$，所以 incremental 情形相对直接。它不需要在全图扫描替代边。

删树边：最轻 Replacement Edge ​

删除非树边不改变 $F$。删除树边 $f$ 会把一棵树分成 $A,B$；若仍有跨割边，保留其余树边的一种最优修复，是选择

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

仅删边：还需要一个权重—层级不变量 ​

先从初始 MSF 出发，扩展HDT 连通性结构理路全动态连通性Fully dynamic connectivity · Dynamic graph connectivity以分层生成森林和 replacement-edge 搜索维护在线边插入删除下的无向图连通性，并用边层级单调提升证明多对数摊还更新界。：保留分层森林与小侧树边先提升的顺序，但在每层按权重递增检查小侧关联的非树边。除连通性与分量大小外，维护如下不变量：每个圈的最重边位于该圈的最低层级。这是只按任意次序扫描非树边时没有的额外条件。

该不变量说明最轻替代边必处于所有替代边的最高层。设同一删除割的两条候选 $e_1$ 比 $e_2$ 轻；它们在原森林中产生的两个基本圈都含被删边。去掉共同路径后得到含 $e_1,e_2$ 的圈，其中 $e_2$ 最重，故 $\ell (e_2)\le \ell (e_1)$。因此先找最高层、再在该层取最轻候选，才能等价于全局最轻替代。

按权顺序扫描还负责保持该不变量：一个内部候选被提升时，同圈中比它轻、又与小侧相邻的候选已经在更高层；小侧的树边也已先提升。若相关圈离开小侧，则必须穿过一条尚未发现的更高层替代边，与搜索前提矛盾。每个仅删边实例内部，边只向上提升，沿用连通性记账可得对数平方的摊还删除成本。

全动态：用重建归约引入插入 ​

上面的提升过程只负责一个固定初始边集中的删除。完整 HDT MSF 算法另外保存对数多个仅删边实例：每条全局非树边恰在其中一个实例里担当局部非树边，也可能作为树边出现在更高层实例中。删除全局树边时，从各实例返回的替代候选中选最轻的跨割边；这个局部／全局不变量保证真正最轻替代必在候选中。

插入或替代造成新的全局非树边时，把它与若干较小实例的非树边合并，重建一个容量按二次幂增长的新实例。为避免每次复制整片全局森林，归约只保留非树边端点间的必要树路径，把长路径压成带路径最大权的超级边；原路径任一边被删除时，对应超级边也失效。Top Tree 负责这些路径摘要及定位。

完整成本由两层记账组成：每个仅删边实例中，提升与删除每条边花对数平方；外层几何重建又控制一条非树边进入不同实例的次数。HDT 的归约定理将这两层以及 $O({\log }^{3}n)$ 的路径维护开销合成 $O({\log }^{4}n)$ 摊还更新界。这个定理并不是“给连通性候选排一下序”就能得到的全动态界；新实例可以重新初始化层级，其成本由外层重建账本承担。