三元环计数（Triple Counting in Undirected Graphs） 问题描述 给定一个无向简单图 \( G = (V, E) \)（简单图指没有自环和重边），计算图中存在多少个“三元环”。一个三元环是指由三个不同的顶点 \( u, v, w \) 构成的环，即这三个顶点两两之间都有边相连，形成一个长度为3的环。换句话说，若 \( (u, v) \in E \)，\( (v, w) \in E \)，且 \( (w, u) \in E \)，则 \( \{u, v, w\} \) 构成一个三元环。注意，由于是无向图，每个三元环只应被计数一次（即不考虑顶点顺序，\( \{u, v, w\} \) 和 \( \{v, u, w\} \) 被视为同一个三元环）。 输入 ：通常以邻接表或邻接矩阵形式给出图 \( G \)。 输出 ：三元环的总数。 这是一个基础但重要的图论问题，在社交网络分析（如计算社群聚类系数）、复杂网络理论中都有应用。直接暴力枚举三个顶点的组合并检查是否两两相连，时间复杂度是 \( O(n^3) \)（n为顶点数），在顶点较多时不可行。下面我将介绍一种更高效的算法，其思想是基于“定向”来避免重复计数，并利用邻接关系加速。 解题步骤 步骤1：算法核心思想——给无向边定向 为了避免重复计数和降低复杂度，我们可以将原无向图的每条边赋予一个方向，将其转化为一个有向无环图（DAG）。 定向规则： 对于任意一条无向边 \( (u, v) \)，我们比较两个顶点的“度”（degree，即与顶点相连的边的数量）： 如果 \( \deg(u) < \deg(v) \)，则将边定向为 \( u \rightarrow v \)（从度小的指向度大的）。 如果 \( \deg(u) > \deg(v) \)，则将边定向为 \( v \rightarrow u \)。 如果度相等，可以比较顶点编号（或其他确定的全序），比如若 \( u < v \)，则定向为 \( u \rightarrow v \)。 这样定向后，图中不会出现有向环，因为边的方向总是从“度较小”的顶点指向“度较大”的顶点（或度相等时按编号比较），不会形成环。这个定向后的图我们称为 \( D \)。 为什么这个定向有用？ 在原无向图 \( G \) 中，一个三元环 \( \{u, v, w\} \) 在定向后，由于三个顶点两两有边，根据上述规则，这三条边不可能全部同向（否则会产生有向环），因此 每个三元环在 \( D \) 中必然恰好有一个顶点，它的两条出边指向另外两个顶点 。也就是说，每个三元环中，出度最大的那个顶点（即度最大者，或度相等时编号最大者）会有两条出边，指向另外两个顶点。 我们可以转而计算：在 \( D \) 中，对每个顶点 \( x \)，考察它的所有“出边邻居”对 \( (y, z) \)（即 \( x \rightarrow y \) 且 \( x \rightarrow z \)），然后检查 \( y \) 和 \( z \) 在原图中是否有边相连（即是否构成环）。因为每个三元环唯一对应一个这样的顶点 \( x \)，所以这样计数不会重复。 步骤2：算法流程 计算每个顶点的度 ：遍历所有边，统计每个顶点的度 \( \deg(v) \)。 建立有向图 \( D \) 的邻接表 ：遍历原图的每条无向边 \( (u, v) \)： 若 \( \deg(u) < \deg(v) \)，或 \( \deg(u) = \deg(v) \) 且 \( u < v \)，则添加有向边 \( u \rightarrow v \) 到 \( D \) 中（即在 \( D \) 中，顶点 \( u \) 的出边列表中加入 \( v \)）。 否则，添加有向边 \( v \rightarrow u \) 到 \( D \) 中。 标记每个顶点的出边邻居 ：为了快速检查两个顶点是否在原图中有边，我们可以在遍历过程中标记。一种高效做法是： 对每个顶点 \( x \)，将其所有出边邻居记录在一个集合（如布尔数组或哈希集合）中，记为 \( \text{out}(x) \)。 枚举可能的“中心”顶点 \( x \) 及其邻居对 ： 对每个顶点 \( x \)： 设 \( x \) 的出边邻居列表为 \( N_ x = \{ y_ 1, y_ 2, \dots, y_ k \} \)。 枚举所有无序对 \( (y_ i, y_ j) \)，其中 \( i < j \)。 检查 \( y_ i \) 和 \( y_ j \) 在原图中是否有边：即判断 \( y_ i \) 是否在 \( \text{out}(y_ j) \) 的集合中（或 \( y_ j \) 在 \( \text{out}(y_ i) \) 中，因为定向是单向的，只需检查一个方向即可）。注意，这里我们只需要检查 \( y_ i \) 和 \( y_ j \) 之间是否有边，而不必关心方向，因为原图是无向的。 如果有边，则找到一个三元环，计数器加1。 输出计数结果 。 步骤3：复杂度分析 设 \( n = |V| \)，\( m = |E| \)。 步骤1、2：\( O(n + m) \)。 步骤3：对每个顶点 \( x \)，设其出度为 \( d_ x \)。则枚举邻居对的次数为 \( \sum_ {x} \binom{d_ x}{2} \)。可以证明，由于定向规则，每个顶点的出度 \( d_ x \) 不超过 \( O(\sqrt{m}) \)。这是因为，对于任意顶点 \( x \)，如果它有出边指向 \( y \)，则 \( \deg(x) \le \deg(y) \)（由定向规则）。若 \( d_ x > \sqrt{m} \)，则 \( x \) 的所有出边邻居的度都至少为 \( d_ x > \sqrt{m} \)，而图中度大于 \( \sqrt{m} \) 的顶点最多只有 \( 2\sqrt{m} \) 个（因为度之和为 \( 2m \)，每个这样的顶点度 > \( \sqrt{m} \)，所以个数 < \( 2m / \sqrt{m} = 2\sqrt{m} \)），矛盾。因此 \( d_ x \le O(\sqrt{m}) \)。 于是总枚举量 \( \sum_ {x} d_ x^2 \le n \cdot O(m) \) 吗？不，更精确地，因为 \( d_ x \le O(\sqrt{m}) \)，所以 \( \sum_ {x} d_ x^2 \le n \cdot O(m) \) 是松的。实际上，由 Cauchy-Schwarz 不等式，\( \sum_ {x} d_ x^2 \le \sqrt{ \sum_ {x} 1^2 \cdot \sum_ {x} d_ x^4 } \) 不是好方向。直接利用 \( d_ x \le \sqrt{2m} \) 可得 \( \sum_ {x} d_ x^2 \le n \cdot 2m \) 仍然松。但更紧的界是：因为 \( \sum_ {x} d_ x = m \)（每个无向边变为一条有向边），且 \( d_ x \le \sqrt{2m} \)，所以 \( \sum_ {x} d_ x^2 \le \max_ {d_ x} \sum d_ x^2 \) 在给定 \( \sum d_ x = m \) 和 \( d_ x \le \sqrt{2m} \) 条件下，最大值在尽可能多的 \( d_ x \) 取到上界时达到，但上界是 \( O(\sqrt{m}) \)，所以大约有 \( O(\sqrt{m}) \) 个顶点取上界，此时 \( \sum d_ x^2 \approx O(\sqrt{m}) \cdot O(m) = O(m^{3/2}) \)。实际上，可以证明更严格的界是 \( O(m^{3/2}) \)。 检查边是否存在：可以用哈希集合存储每个顶点的出边邻居，则每次检查 \( y_ i \) 是否在 \( \text{out}(y_ j) \) 中，可以在 \( O(1) \) 平均时间内完成。 总时间复杂度：\( O(m^{3/2}) \)，空间复杂度 \( O(n + m) \)。 步骤4：示例演示 假设一个无向图有顶点 \( \{1,2,3,4\} \)，边为：\( (1,2), (1,3), (2,3), (2,4), (3,4) \)。 度：\( \deg(1)=2, \deg(2)=3, \deg(3)=3, \deg(4)=2 \)。 定向（度相等时按编号小→大）： 边(1,2)：\( \deg(1) <\deg(2) \)，定向 1→2。 边(1,3)：\( \deg(1) <\deg(3) \)，定向 1→3。 边(2,3)：度相等，2 <3，定向 2→3。 边(2,4)：\( \deg(2)>\deg(4) \)，定向 4→2。 边(3,4)：\( \deg(3)>\deg(4) \)，定向 4→3。 有向图 \( D \) 的邻接表： 1的出边：{2,3} 2的出边：{3} 3的出边：{} 4的出边：{2,3} 现在枚举每个顶点作为可能的“中心” \( x \)： \( x=1 \)：出边邻居 {2,3}。检查对(2,3)：2的邻接集合是{3}吗？是（因为2→3）。找到三元环{1,2,3}。计数=1。 \( x=2 \)：出边邻居 {3}，邻居对不足两个，跳过。 \( x=3 \)：出边邻居 {}，跳过。 \( x=4 \)：出边邻居 {2,3}。检查对(2,3)：同上，2的邻接集合包含3，找到三元环{2,3,4}。计数=2。 最终结果：2个三元环（{1,2,3} 和 {2,3,4}）。 步骤5：算法实现要点 在实现时，可以用一个哈希表（如unordered_ set）数组来存储每个顶点的出边邻居集合，以便快速判断两个顶点是否在原图中有边（即检查是否在彼此的出边集合中）。注意，由于我们定向是单向的，原图中的无向边在 \( D \) 中只出现一次，但若 \( y \) 是 \( x \) 的出边邻居，我们只需检查 \( y \) 的出边集合中是否有 \( x \) 吗？不，因为原边是无向的，但我们的定向是单向的，所以检查时应看：对 \( x \) 的两个出边邻居 \( y, z \)，是否 \( y \) 有出边指向 \( z \) 或 \( z \) 有出边指向 \( y \)。实际上，由于定向规则，如果 \( y \) 和 \( z \) 之间有原边，那么这条边在 \( D \) 中必然是从度较小（或编号较小）者指向度较大者，因此只需检查这两个顶点中出度较小的那个顶点是否指向另一个即可。但为了简便，我们可以用无向的邻接关系来判断：可以预先存储原图的无向邻接表，或者利用“在 \( D \) 中，若 \( y \) 和 \( z \) 之间有原边，则这条边在 \( D \) 中要么是 \( y\rightarrow z \) 要么是 \( z\rightarrow y ”，因此只需检查 \( y \) 的出边集合中是否有 \( z \) 或 \( z \) 的出边集合中是否有 \( y \)。但注意，当我们以 \( x \) 为中心时，\( y \) 和 \( z \) 都是 \( x \) 的出边邻居，这意味着在原图中 \( x \) 与 \( y \)、\( x \) 与 \( z \) 都有边，且 \( \deg(x) \le \deg(y) \) 和 \( \deg(x) \le \deg(z) \)。那么 \( y \) 和 \( z \) 之间的边如何定向？因为 \( y \) 和 \( z \) 的度都至少为 \( \deg(x) \)，所以它们之间的边定向取决于它们两个之间的比较。为了检查 \( y \) 和 \( z \) 之间是否有原边，我们可以直接检查“ \( y \) 的出边集合中是否有 \( z \) ”即可，因为如果 \( y \) 和 \( z \) 有边，那么在 \( D \) 中，如果 \( \deg(y) < \deg(z) \) 或度相等且 \( y<z \)，则边是 \( y\rightarrow z \)，否则是 \( z\rightarrow y \)。所以只需检查一个方向（因为我们的存储是单向的）。但为了不遗漏，我们可以在枚举时，对每个 \( x \)，将其出边邻居列表排序（按顶点编号），然后对每个对 \( (y, z) \)，检查 \( y \) 的出边集合是否包含 \( z \)（因为 \( y \) 的度可能小于等于 \( z \) 的度，但即使 \( y \) 的度大于 \( z \)，这条边在 \( D \) 中会是 \( z\rightarrow y \)，所以我们检查 \( y \) 的出边集合可能找不到 \( z \)）。因此，更稳妥的方法是：用一个布尔型二维数组或哈希集合存储 原无向图的邻接关系 （即无向边），这样可以在 \( O(1) \) 时间检查任意两点是否直接相连。但这样空间开销是 \( O(n^2) \)，对稀疏图不可取。实际上，我们可以用哈希集合数组存储每个顶点的 所有邻居 （无向），检查时看 \( y \) 是否在 \( z \) 的邻居集合中即可，空间 \( O(n+m) \)。实现中，可以就用在步骤2中构建的无向邻接表（或邻接集合）来检查。 步骤6：总结 这个算法通过巧妙的定向，将三元环计数转化为对每个顶点枚举其出边邻居对，并检查这两个邻居之间是否有边。由于每个顶点的出度被控制在 \( O(\sqrt{m}) \) 以内，总时间复杂度为 \( O(m^{3/2}) \)，适合处理边数较多的稀疏图。这是三元环计数问题中最经典的优化算法。