计算图中的三角形（长度为 3 的周期）

Question

在具有 V 个顶点和 E 个边的无向图中，如何计算 O(|V||E|) 中三角形的数量？我在这里看到了该算法，但我不太确定如何实现该算法来实现这种复杂性。这是该帖子中提供的代码：

for each edge (u, v):
  for each vertex w:
     if (v, w) is an edge and (w, u) is an edge:
          return true
return false

您是否会使用图的邻接列表表示来遍历外循环中的所有边，然后使用邻接矩阵来检查内循环中是否存在 2 条边？

另外，我看到另一个解决方案为 O(|V||E|)，它涉及在图上执行深度优先搜索，当您遇到来自您正在访问的顶点 u 的后边 (u,v) 时，检查是否顶点 u 的祖父母是顶点 v。如果是，那么您就找到了一个三角形。这个算法正确吗？如果是这样，这不是 O(|V|+|E|) 吗？在我链接的帖子中，提供了广度优先搜索解决方案的反例，但根据我提出的示例，我上面概述的深度优先搜索方法似乎有效。

Answer 1

首先，请注意，该算法并不计算三角形的数量，而是返回三角形是否存在。

对于第一个算法，如果我们假设我们可以在恒定时间内查找(a, b) 是一条边，那么分析就会变得简单。（因为我们循环遍历所有边的所有顶点，并且仅在恒定时间内执行某些操作，所以我们得到 O(|V||E|*1)。）可以使用 for 来在恒定时间内判断某物是否是集合的成员例如哈希表/集合。正如您所说，我们还可以通过使用邻接矩阵来做到这一点，我们可以通过循环所有边来预先创建邻接矩阵，而不改变我们的总复杂性。

也许可以使用用于在边缘上循环的邻接列表表示，但遍历它可能是 O(|V|+|E|)，给我们总复杂度 O(|V||V| + |V||E| ）这可能比我们想要的更多。如果是这种情况，我们应该首先循环遍历它，并将所有边添加到普通集合（如列表）中。

对于您提出的 DFS 算法，问题在于我们无法确定在正确的时刻遇到某个边缘作为后边缘，如以下反例所示：

A -- B --- C -- D
      \   /     |
        E ----- F

这里如果我们从ABCE看，然后找到后边EB，我们就正确地找到了三角形；但如果我们改为 ABCDFE，则后边 EB 和 EC 不再满足我们的条件。