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

Question

这是 Algorithm Design Manual 中的一个练习.

Consider the problem of determining whether a given undirected graph G = (V, E) contains a triangle or cycle of length 3.

(a) Give an O(|V |^3) to find a triangle if one exists.

(b) Improve your algorithm to run in time O(|V |·|E|). You may assume |V | ≤ |E|.

Observe that these bounds gives you time to convert between the adjacency matrix and adjacency list representations of 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。每当找到交叉边时，例如，如果 y-x 是交叉边，那么我将检查是否 parent[y] == parent[x]，如果为真，则三角形是找到了。

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

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

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

Answer 1

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