Borůvka + 隐式图模型

隐式稠密图上用 Borůvka 的 O(log n) 轮,把每轮化为最优出边 oracle;具体谓词结构与 SOS DP 见实例页。

标签 图论 / 生成树 / Borůvka / 问题模型

模型概述

有一类生成树题:连通图的边数达 𝑂(𝑛2),但边不是显式给出的,而是由顶点属性决定。直接建图或枚举边都不可行。

Borůvka 算法只要求每轮为每个连通块找一条“最优出边”。因此,只要我们能设计一个数据结构回答这个查询,就能在隐式图上求生成树。

本页的抽象重点是:谓词需要满足什么结构,才能让“最优出边”变成可查询的问题。具体的谓词结构见 Borůvka + 隐式图模型实例;主理想类实例(布尔格、树形偏序、DAG 可达性)见 Borůvka + 隐式图模型实例:主理想。

抽象形式

给定隐式无向图 𝐺=(𝑉,𝐸):

  • 顶点为 0,1,…,𝑛,每个点有属性 𝑚𝑖 和点权 𝑣𝑖;
  • 边 (𝑖,𝑗) 存在当且仅当谓词 𝑃(𝑖,𝑗) 成立;
  • 谓词必须对称:𝑃(𝑖,𝑗)⇔𝑃(𝑗,𝑖),保证图是无向的;
  • 边权可分离:𝑤(𝑖,𝑗)=𝑓(𝑣𝑖)+𝑔(𝑣𝑗);
  • 求最大(或最小)生成树 / 生成森林。

模型本身不限定 𝑃 的具体形式,只要求存在一个最优出边 oracle。实例页给出这个 oracle 可实现的常见结构条件。

Borůvka 框架

  1. 初始每个点自成一个连通块。
  2. 每一轮,为每个连通块选出最优出边。
  3. 把这些边同时加入,用并查集合并,跳过已经同块的边。
  4. 连通块数量至少减半,最多 𝑂(log𝑛) 轮。

于是问题从“枚举 𝑂(𝑛2) 条边”变成“每轮为每个当前连通块回答一次最优出边查询”。第 𝑖 轮(从 0 开始计)的连通块数不超过 𝑛2𝑖,所以 Borůvka 层的块级查询总数是 𝑂(𝑛),而不是 𝑂(𝑛log𝑛)。

最优出边 oracle

Borůvka 每轮要为每个当前连通块找一条最优出边。实现上先定义点级查询,再对块内所有点取最大值。

对点 𝑖 和它所在的分量 𝐶,定义查询

query(𝑖,𝐶)=argmax𝑗:𝑃(𝑖,𝑗),comp(𝑗)≠𝐶𝑤(𝑖,𝑗)

其中 comp(𝑗) 表示 𝑗 当前所在的 Borůvka 连通块。query(𝑖,𝐶) 的含义是:从 𝑖 出发,在所有满足 𝑃(𝑖,𝑗)、且不在块 𝐶 中的点 𝑗 里,选 𝑤(𝑖,𝑗) 最大的一个。它返回的是点 𝑗(等价地,边 (𝑖,𝑗)),不是最大权值;若候选集为空,则 𝑖 当前没有出边。

一个连通块 𝐶 的最优出边,就是块内所有点级查询结果中按 𝑤 最大的那一条;实际实现中通常对块内每个点各查一次再取最大,所以块级查询数按连通块数递减,但点级查询数仍是每轮 𝑛。

若 𝑤(𝑖,𝑗)=𝑓(𝑣𝑖)+𝑔(𝑣𝑗),固定 𝑖 后 𝑓(𝑣𝑖) 是常数,查询化简为

query(𝑖,𝐶)=argmax𝑗:𝑃(𝑖,𝑗),comp(𝑗)≠𝐶𝑔(𝑣𝑗)

难点是排除同分量。通用技巧是维护“来自不同分量的前两名”:

  • best1:候选集合中的全局最优;
  • best2:与 best1 不同分量的最优。

查询时:

  • 若 best1 不在 𝐶,选 best1;
  • 否则选 best2。因为 best2 与 best1 不同分量,所以它一定不在 𝐶。

这个技巧只依赖“能对候选集合做最值查询”,与具体谓词无关。

源码位置