这是一个练习算法设计手册 http://www.algorist.com/.
考虑判断给定的无向图 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|) 中做到这一点？
一个可能的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
检查所有边缘, and not所有顶点对 - 与形成三角形的另一个顶点 - 有足够的信息来确定边和顶点是否形成可行的解决方案。
BFS解决方案的反例：
A
/ | \
/ | \
B C D
| | |
| | |
F---G---H
| |
---------
(F, H) is also an edge
注意father[F] != father[G] != father[H]，因此算法将返回 false - 但尽管如此，(F, G, H) 是一个可行的解决方案！
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
