如何在图表中找到三角形？

Question

如何在图表中找到三角形？

26

这是一道算法设计手册中的练习。

考虑确定一个给定的无向图 G = (V, E) 是否包含长度为 3 的三角形或循环。

(a) 给出一个时间复杂度为 O(|V|^3) 的算法来查找是否存在三角形。

(b) 改进你的算法，使其在 O(|V|·|E|) 的时间内运行。你可以假设 |V| ≤ |E|。

注意，这些边界值允许你在邻接矩阵和邻接表表示之间进行转换。

这是我的想法：

(a) 如果以邻接表的形式给出图，则我可以通过 O(|V|^2) 将列表转换为矩阵，然后执行以下操作：

for (int i = 0;i < n;i++) 
   for (int j = i+1;j < n;j++) 
   if (matrix[i][j] == 1) 
      for (int k = j+1;k < n;k++) 
         if (matrix[i][k] == 1 && matrix[j][k] == 1)
             return true;

这应该会给出一个O(|V|^3)的测试三角形。

(b) 我的第一直觉是，如果图以邻接列表的形式给出，我会进行广度优先搜索（BFS）。每当找到横跨边时，例如，如果 y-x 是横跨边，然后我将检查 parent[y] == parent[x] 是否成立，如果成立，则找到了一个三角形。

能否有人告诉我我的想法是否正确？

对于(b)部分，我不确定它的复杂度。应该是O(|V| + |E|)，对吗？

我如何在O(|V|*|E|)中完成它？

- Jackson Tale

(a)的前三行正在迭代所有边... - uty

由于您进行了一点优化，最内层循环仅在ij是边缘时运行。因此，更仔细的分析可得，当ij不是边缘时的成本为O（V ^ 2），当ij是边缘时的成本为O（EV），总共为O（EV），假设E> = V。 - uty

@ARJUN 你能更新一下链接吗？那个链接现在似乎成了一个钓鱼网站。 - dcsan

请查看此C程序以查找图中三角形的数量。 - ARJUN

4个回答

9

如果你有一个邻接矩阵，可以通过对矩阵进行平方并查看原始矩阵和平方矩阵在同一位置是否具有非零条目来找到三角形。

朴素的矩阵乘法需要时间复杂度为O(n^3)，但是有快速矩阵乘法算法可以做得更好。其中最著名的是Coppersmith-Winograd算法，其运行时间为O(n^2.4)。这意味着算法大致如下：

- 使用O(V^2)时间将其转换为邻接矩阵。 - 使用O(V^2.4)时间计算邻接矩阵的平方。 - 使用O(V^2)时间检查两个矩阵中是否存在重合的非零条目。 - 在（如果有的话）发现重合非零条目的行和列的索引告诉您涉及的两个节点之一。 - 使用O(V)时间缩小共同已知节点的第三个节点。

总的来说，这需要O(V^2.4)的时间；更确切地说，它需要矩阵乘法所需的时间。您可以动态地在这个算法和如果任何边缘端点有一个公共邻居算法由amit在他们的答案中解释之间切换，以将其改进为O(V min(V^1.4, E))。

这里有一篇更深入探讨该问题的论文。

这个问题与理论发现息息相关，这很有趣。如果关于矩阵乘法的猜想被证明是二次的，那么你会得到一个非常好的时间复杂度为O(V^2)或O(V^2 log(V))之类的东西。但如果量子计算机能够实现，我们将能够做得比这更好（大约是O(V^1.3)）！

- Craig Gidney

很棒的答案，但是...！我正在研究这个问题，但我不明白你如何在O（V）中找到所有第三个节点。每个非零条目都是O（V）吗？那么对于整个矩阵来说就是O（V^3）了，因为您可能需要为矩阵的每个条目花费O（V）。如果不是这样，那么您是如何管理的呢？能否在答案中添加一些解释？谢谢 - ameerosein

@ameerosein 你知道A-B和A-?-B。通过交集找到A和B的邻居中的共同元素最多需要O(V)时间。 - Craig Gidney

所以仅对于 A-?-B，它是 O(V)。然后对于每个三角形，你都需要这样做... 所以总体来说它不是 O(V)，而是超过了 O(V^2)。我是对的吗？ - ameerosein

@ameerosein 你只需要做一个三角形就行了。寻找邻接矩阵和它的平方都有1的条目的目的就是为此。 - Craig Gidney

为什么是“一个”三角形？对于任何重合的非零元素，您都需要找到第三个节点，不是吗？ - ameerosein

哦，抱歉，我们正在寻找一个三角形...但我实际上想找到所有的三角形...对于这个问题有什么想法吗？ - ameerosein

1

我认为：

原始的 BFS 解决方案是错误的，正如上面指出的那样。但是我们可以修改 DFS。在访问每个顶点时给已访问的节点分配数字。现在，如果我们到达一个顶点（在我看到的问题中有交叉边，在无向图中没有），我们检查它的邻接列表，假设发现了一个顶点（但未处理，不可能发生），然后我们检查它的数字。如果差为2，则存在长度为3的循环。

- Prashant

0

我真的很喜欢这篇博客文章中讨论的矩阵乘法解决方案。

令a为邻接矩阵

a*a（a2）矩阵相乘中的邻接点是2长度路径的数量
a2*a矩阵相乘中的邻接点是3长度路径的数量

问题在于，矩阵乘法速度较慢... 但是，您可以使用GPGPU执行矩阵乘法，并且可以在包括GPU的现代架构上获得高性能的解决方案。

- class

6

你链接了错误的内容。这个链接指向了这个问题，而不是一个博客文章。 - Craig Gidney

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

一种可能的O(|V||E|)解决方案，是与(a)中暴力算法相同的思路：

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

检查所有边，而不是所有顶点对 - 与形成三角形的另一个顶点 - 这足以确定边和顶点是否形成可行解。

BFS解法的反例：

       A
     / | \
    /  |  \
   B   C   D
   |   |   |
   |   |   |
   F---G---H
   |       |
   ---------
    (F, H) is also an edge

请注意，father[F] != father[G] != father[H]，因此算法将返回 false - 但是，(F，G，H) 仍然是一个可行解！