更快的无向图三元环计数

· · 算法·理论

updated 2025.11.8
简化了算法流程。

一个一个数是不能突破 O(m \sqrt m) 的下界的。
设矩阵乘法的复杂度为 O(n^\omega)，这里提供一种 O(m^{\frac{2\omega}{\omega + 1}}) 的做法。
例如，使用 Strassen 方法可以将其复杂度降为 O(m^{1.475})。

算法1. 矩阵乘法

考虑我们枚举一条边 (a, b)，接下来需要计数有多少个点 c 满足 (a, c), (b, c) 均存在。
设图的邻接矩阵为 A，则由 (a, b) 边参与形成的三元环个数即为 \sum \limits_{i = 1}^{n} A_{a, i} \times A_{i, b}
不难看出这是一个矩阵乘法的形式。我们可以求出来 B = AA^T，然后 B_{a, b} 即为所求。

这里需要计算一次矩阵乘法，然后 O(m) 枚举边。
由于矩阵乘法不会低于 O(n^2)，所以复杂度为 O(n^\omega)。

算法 1 的好处在于，不是一个一个数的，可以突破 O(m \sqrt m) 的下界。
不过稀疏图上表现很差就是了。

算法2. 生成树

这里是另一个算法。
假设图连通，我们求图的一个 dfs 生成树出来。
（任意生成树都可以，但是 dfs 生成树没有横叉边方便我们处理）

然后将三元环拆成以下四种情况：

  1. 由三个树边组成。显然不成立。
  2. 由一个树边两个非树边组成。
  3. 由两个树边一个非树边组成。
  4. 由三个非树边组成。

首先看情况 2。
我们枚举一个点 p，然后标记所有通过非树边与 p 相连的点。
然后判断这些点之间由多少祖先关系即可。
这部分的复杂度为 O(m)。

然后看情况 3。
我们枚举一条非树边 (a, b)，然后判断 a, b 两个点在树上的距离是否为 2 即可。
由于没有横叉边，所以只可能是 fa[fa[a]] = b 或者 fa[fa[b]] = a。

最后，将所有树边去掉，然后递归处理上述过程即可。

Q：该算法复杂度？
考虑每次删除一个生成树，每个点的度至少减一。
所以该过程至多进行 n - 1 轮。
复杂度即为 O(nm)。

如果阈值分治并结合暴力该算法也可以分析得到 O(m \sqrt m) 的复杂度。在此不表。
反正也是一个一个数的，不会低于 O(m \sqrt m)。
不过在稀疏随机图上表现会很好。

阈值分治

上述两个算法分别在稠密图和稀疏图上表现良好。
这里使用阈值分治结合一下。

考虑我们先进行 B 轮算法 2，然后去掉所有的孤点，对于剩下的点使用算法 1。
所有点的总度数为 O(m)，进行 B 轮之后剩下的点在原图上的度数均 >B，而这样的点只有 O(\frac{m}{B}) 个。
所以两部分的复杂度和为 O(mB + \left( \frac{m}{B} \right)^\omega)。
取 B = m^{\frac{\omega - 1}{\omega + 1}} 最优，总复杂度为 O(m^{\frac{2\omega}{\omega + 1}})。

实现

当然，Strassen 方法常数巨大。
所以我实现矩阵乘的时候直接写的压位。复杂度 O(\frac{n^3}{w})。
总复杂度可以平衡到 O(\frac{m \sqrt m}{w^{\frac{1}{4}}})。

实测如果跑满 B 轮的话会很慢。
推荐是当剩余点数不超过 \frac{m}{B} 的时候直接退出，会跑的飞快。
261ms

拜谢 UT 提供的复杂度分析指导 orz orz orz