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

问题描述 投票：0回答：5

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

考虑判断给定的无向图G是否存在的问题 = (V, E) 包含一个长度为 3 的三角形或环。

(a) 给出一个 O(|V |^3) 来查找三角形（如果存在）。

(b) 改进 您的算法运行时间为 O(|V |·|E|)。你可以假设 |V | ≤ |E|。

观察这些界限让您有时间在 G 的邻接矩阵和邻接表表示。

这是我的想法：

(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。每当找到交叉边，例如

if y-x is a cross edge
，那么我就会
check whether parent[y] == parent[x], if true, then a triangle is found
。

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

同样对于这个（b），我不确定它的复杂性。应该是 O(|V| + |E|) 吧？

如何在 O(|V|*|E|) 中做到这一点？

algorithm data-structures graph-theory
5个回答
38
投票

一个可能的

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) 是一个可行的解决方案！

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)
时间；更准确地说，无论矩阵乘法需要多长时间，它都会花费多长时间。您可以在该算法和 if-any-edge-end-points-have-a-common-neighbor 算法之间动态切换amit 在他们的答案中解释，以将其改进为
O(V min(V^1.4, E))
。

这里有一篇论文更深入地探讨了这个问题。

这个问题对理论发现的依赖程度非常好。 如果关于矩阵乘法实际上是二次的猜想被证明是正确的，那么你会得到一个非常好的时间界限 

O(V^2)
或 
O(V^2 log(V))
或类似的东西。但如果量子计算机成功，我们将能够做得甚至比这更好（类似于
O(V^1.3)
）！

1
投票

这是我的想法：

如上所述，最初的 BFS 解决方案是不正确的。但我们可以修改DFS。当我们访问 DFS 中的每个顶点时，为所访问的节点分配编号。现在，如果我们到达一个顶点（在我看到交叉边的问题中，无向图中没有交叉边），我们检查它的邻接列表并假设发现一个顶点（但没有处理，不可能发生），然后我们检查它的编号。如果差值为 2，则存在长度为 3 的循环。

0
投票

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

设 a = 邻接矩阵

  • a*a (a2) 矩阵中的邻接相乘就是 2 长度路径的数量
  • a2*a 矩阵中的邻接相乘就是 3 长度路径的数量

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

0
投票

使用 DFS 解决这个问题： （虽然上面讨论了解决方案，但我想用DFS给出一个清晰的解释）

周期检测

  • 在 DFS 期间，如果遇到 
    edge(u, v)
    ，其中 v 先前已被发现但未处理（即它是 u 的祖先），我们可以检测循环。

验证周期为三角形

  • 只要在处理 
    edge(u, v)
    过程中发现循环，当且仅当存在一个顶点同时具有 
    u
    和 
    v
    的边时，才将其视为三角形循环。该标准表明图中存在长度为 3 的循环。

时间复杂度 O(|V|·|E|):

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.