什么是计算图形中三角形数量的有效算法？

Question

什么是计算无向图中三角形数量的有效算法)(其中图形是一组顶点和边)？我一直在搜索Google,每天连续三天阅读我的教科书架几个小时.

这是一个家庭作业,我需要这样一个算法,但开发它不会指定任何任务.我们可以简单地从外部资源中找到这样的算法,但我已经走到了尽头.

为了清楚起见,图中的三角形是长度为3的循环.诀窍是它需要处理最多10,000个节点的顶​​点集.

我目前正在使用C#,但更关心解决此问题的一般方法,而不是复制和粘贴代码.

在高层,我迄今为止的尝试包括:

• 广度优先搜索,跟踪长度为3的所有独特循环.这对我来说似乎是一个好主意,但我无法让它发挥作用
• 在图中的所有节点上循环以查看三个顶点是否共享边.这对于较大的数据集而言运行时间太慢.为O(n ^ 3).

算法本身是计算聚类系数的一部分.

Answer 1

您将需要深度优先搜索。该算法将是：

1）对于当前节点询问所有未访问的相邻节点

2）对于这些节点中的每一个，运行深度二，检查深度为 2 的节点是否是第一步中的当前节点

3) 将当前节点标记为已访问

4）使每个未访问的相邻节点成为当前节点（1乘1）并运行相同的算法

Answer 2

取决于您的图表的表示方式。

如果您有一个邻接矩阵 A，则三角形的数量应为 tr(A^3)/6，换句话说，是对角线元素之和的 1/6（除法负责方向和旋转）。

如果您有邻接列表，只需从每个节点开始并执行深度 3 搜索。计算到达该节点的频率 -> 再次除以 6。