Borůvka + 隐式图模型
隐式稠密图上用 Borůvka 的 O(log n) 轮,把每轮化为最优出边 oracle;具体谓词结构与 SOS DP 见实例页。标签 图论 / 生成树 / Borůvka / 问题模型
模型概述
有一类生成树题:连通图的边数达 ,但边不是显式给出的,而是由顶点属性决定。直接建图或枚举边都不可行。
Borůvka 算法只要求每轮为每个连通块找一条“最优出边”。因此,只要我们能设计一个数据结构回答这个查询,就能在隐式图上求生成树。
本页的抽象重点是:谓词需要满足什么结构,才能让“最优出边”变成可查询的问题。具体的谓词结构见 Borůvka + 隐式图模型实例;主理想类实例(布尔格、树形偏序、DAG 可达性)见 Borůvka + 隐式图模型实例:主理想。
抽象形式
给定隐式无向图 :
- 顶点为 ,每个点有属性 和点权 ;
- 边 存在当且仅当谓词 成立;
- 谓词必须对称:,保证图是无向的;
- 边权可分离:;
- 求最大(或最小)生成树 / 生成森林。
模型本身不限定 的具体形式,只要求存在一个最优出边 oracle。实例页给出这个 oracle 可实现的常见结构条件。
Borůvka 框架
- 初始每个点自成一个连通块。
- 每一轮,为每个连通块选出最优出边。
- 把这些边同时加入,用并查集合并,跳过已经同块的边。
- 连通块数量至少减半,最多 轮。
于是问题从“枚举 条边”变成“每轮为每个当前连通块回答一次最优出边查询”。第 轮(从 开始计)的连通块数不超过 ,所以 Borůvka 层的块级查询总数是 ,而不是 。
最优出边 oracle
Borůvka 每轮要为每个当前连通块找一条最优出边。实现上先定义点级查询,再对块内所有点取最大值。
对点 和它所在的分量 ,定义查询
其中 表示 当前所在的 Borůvka 连通块。 的含义是:从 出发,在所有满足 、且不在块 中的点 里,选 最大的一个。它返回的是点 (等价地,边 ),不是最大权值;若候选集为空,则 当前没有出边。
一个连通块 的最优出边,就是块内所有点级查询结果中按 最大的那一条;实际实现中通常对块内每个点各查一次再取最大,所以块级查询数按连通块数递减,但点级查询数仍是每轮 。
若 ,固定 后 是常数,查询化简为
难点是排除同分量。通用技巧是维护“来自不同分量的前两名”:
best1:候选集合中的全局最优;best2:与best1不同分量的最优。
查询时:
- 若
best1不在 ,选best1; - 否则选
best2。因为best2与best1不同分量,所以它一定不在 。
这个技巧只依赖“能对候选集合做最值查询”,与具体谓词无关。