algorithm - 使用具有特定运行时间的算法在图中查找三角形

Question

我需要找到一种在无向图中找到三角循环的算法。算法的运行时间应该是n^2,81

我真的不知道如何才能做到这一点。如果有人能提供帮助，那就太好了!

谢谢!

Answer 1

您搜索的算法是矩阵乘法。将邻接矩阵与自身相乘 3 次，并在主对角线上搜索非零条目。矩阵乘法是 O(N^2.81): https://en.wikipedia.org/wiki/Matrix_multiplication_algorithm

编辑:

回想一下，在邻接矩阵的第 i 行中，每个连接到 i 的顶点都为“1”，列也是如此。

当您将矩阵与自身相乘时，(M^2)ij = sum (Mik*Mkj)。换句话说，(M^2)ij 是从 i 到 j 的 2 边路径的数量。

现在，如果您再次乘以得到 M^3，则在每个单元格 (M^3)ij 中，将有从 i 到 j 的 3 边路径的数量。所以在主对角线 (M^3)ii 中会有从 i 到 i 的 3 边路径的数量，一个三角形。