下面是一个用 C++ 实现的三角形计数算法。这个实现使用邻接表存储图，并计算三角形的数量。

C++ 代码实现

#include <iostream>
#include <vector>
#include <unordered_set>
#include <unordered_map>

using namespace std;

// 函数：计算三角形的数量
int countTriangles(const vector<pair<int, int>>& edges) {
    // 构建邻接表
    unordered_map<int, unordered_set<int>> graph;

    // 添加边到邻接表
    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;

        if (u != v) { // 忽略自环
            graph[u].insert(v);
            graph[v].insert(u); // 无向图，所以添加双向边
        }
    }

    int triangleCount = 0;

    // 遍历每一对邻接节点
    for (const auto& [u, neighbors] : graph) {
        for (int v : neighbors) {
            if (u < v) { // 只考虑(u, v)一对，避免重复
                // 找到共同邻居
                int commonNeighbors = 0;
                for (int w : neighbors) {
                    if (graph[v].count(w)) { // 检查w是否在v的邻居中
                        commonNeighbors++;
                    }
                }
                triangleCount += commonNeighbors;
            }
        }
    }

    return triangleCount;
}

int main() {
    // 示例边列表
    vector<pair<int, int>> edges = {
        {1, 2},
        {2, 3},
        {3, 1},
        {1, 4},
        {2, 4},
        {3, 4},
    };

    // 调用函数
    int triangles = countTriangles(edges);
    cout << "三角形的数量: " << triangles << endl;

    return 0;
}

代码解析

1. 数据结构：

   • 使用 unordered_map 来实现邻接表，每个顶点映射到其邻居的集合 (unordered_set)。

2. 构建邻接表：

   • 遍历边列表，将每条边加入邻接表中，同时忽略自环。

3. 三角形计数：

   • 对于每对邻接的顶点 (u, v)，检查 u 和 v 的共同邻居。
   • 通过检查 v 的邻居是否在 u 的邻居集合中来找到共同邻居，并累加计数。
   • 只考虑 u < v 的情况以避免重复计数。

4. 输出结果：

   • 在 main 函数中，调用 countTriangles 函数并打印结果。

性能分析

该算法与前面的 Python 实现类似，复杂度为 (O(V^2 + E))，其中 (V) 是顶点数，(E) 是边数。在稀疏图中表现良好，但在非常密集的图中可能效率较低。

总结

这个 C++ 实现提供了一个基本的方法来计算简单无向图中的三角形数量。可以根据具体需求对其进行优化，例如使用并行处理或者更高效的数据结构来提升性能。