补图连通性

给定稀疏图,求补图的连通块;用未访问集合做 BFS,间接遍历稠密补图,O((n+m) log n)。

标签 图论 / 补图 / BFS / 问题模型

模型概述

给定一个简单无向图 𝐺=(𝑉,𝐸),𝑛=|𝑉|,𝑚=|𝐸|,且 𝑚 通常较小。需要求补图 𝐺𝑐 的连通块数、连通性,或每个点所属的连通块。

补图 𝐺𝑐 保留全部顶点,两点之间有边当且仅当它们在 𝐺 中不相邻:

𝐸𝑐≝{{𝑢,𝑣}:𝑢≠𝑣,{𝑢,𝑣}∉𝐸}

补图可能有 𝑂(𝑛2) 条边,不能直接建图;但 𝐺 稀疏,因此可以利用“在 𝐺 中不相邻”这一条件间接遍历补图。

抽象形式

输入是 𝐺 的邻接表,可以 𝑂(1) 判断一条边是否属于 𝐸。

要求输出:

  • 𝐺𝑐 的连通块数;或
  • 每个点在 𝐺𝑐 中的连通块编号;或
  • 各个连通块的大小。

核心查询是:对当前点 𝑢,找出所有尚未访问、且与 𝑢 在 𝐺 中不相邻的点。

框架

维护一个集合 unvisited,初始包含全部顶点。外层每次取出一个未访问点 𝑠,连通块数加一,从 𝑠 开始 BFS。

对队首 𝑢,遍历 unvisited 中的所有 𝑣:

  • 若 (𝑢,𝑣)∉𝐸,则 (𝑢,𝑣) 是补图边,把 𝑣 从 unvisited 删除并入队;
  • 若 (𝑢,𝑣)∈𝐸,则 𝑣 暂时保留,等后续点发现它。

同一个点一旦被删除,就不会再被其他点重复发现。遍历时先收集本轮要删除的点,再统一删除,避免迭代器失效。

正确性

BFS 只在 (𝑢,𝑣)∉𝐸 时扩展,因此走过的每条边都属于补图。

若两个点在补图中连通,沿补图路径依次扩展,路径上的点都会被加入队列;反之,所有被加入队列的点都通过补图边相连。因此每个连通块恰好被外层计数一次。

复杂度

每个点最多从 unvisited 删除一次,对应 𝑂(𝑛) 次成功发现。

每次检查 (𝑢,𝑣) 但没有删除 𝑣 时,(𝑢,𝑣) 必是 𝐺 的边;由于 𝑢 已经被访问并从集合中删除,这条边不会在反方向再次被检查。因此这类检查总数是 𝑂(𝑚)。

总检查次数 𝑂(𝑛+𝑚)。用有序集合维护 unvisited 时,每次删除和遍历有 𝑂(log𝑛) 代价,总复杂度

𝑂((𝑛+𝑚)log𝑛)

空间 𝑂(𝑛+𝑚)。

变式

  • 01-MST:0 边图就是给定 1 边图的补图;若补图有 𝑐 个连通块,MST 权值为 𝑐−1。
  • 补图 BFS / 最短路:按层扩展时同时记录距离,可以求补图上的最短路。
  • 连通块大小:BFS 时统计本块删除的点数。
  • 补图稀疏时:若 𝑚 接近 𝑛(𝑛−1)2,直接枚举补图边可能更快;两种做法按 𝑚 与补图边数取较小者。

关联题目

源码位置