26

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

考虑确定给定无向图 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|) 中做到这一点？

4

4 回答 4

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

于 2012-04-17T14:38:44.517 回答
8

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

一个简单的矩阵乘法需要时间O(n^3)，但是有一些快速的矩阵乘法算法做得更好。最著名的算法之一是及时运行的Coppersmith-WinogradO(n^2.4)算法。这意味着算法类似于：

  • 使用O(V^2)时间转换为邻接矩阵。
  • 使用O(V^2.4)时间计算邻接矩阵的平方。
  • 使用O(V^2)时间检查矩阵是否符合非零条目。
  • 您在（如果有的话）中找到重合的非零条目的行和列的索引告诉您两个相关节点。
  • 使用O(V)时间来缩小两个已知节点共有的第三个节点。

所以总的来说这需要O(V^2.4)时间。更准确地说，它需要很长的矩阵乘法。您可以在此算法和amit 在其答案中解释的 if-any-edge-end-points-have-a-common-neighbor 算法之间动态切换，以将其改进为O(V min(V^1.4, E)).

这是一篇更深入地研究这个问题的论文。

It's kind of neat how dependent-on-theoretical-discoveries this problem is. If conjectures about matrix multiplication actually being quadratic turn out to be true, then you would get a really nice time bound of O(V^2) or O(V^2 log(V)) or something like that. But if quantum computers work out, we'll be able to do even better than that (something like O(V^1.3))!

于 2015-01-07T03:01:06.823 回答
1

这是我的想法：

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

于 2013-11-10T18:18:49.890 回答
0

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

令 a = 邻接矩阵

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

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

于 2014-06-12T23:49:35.810 回答