使用具有特定 运行 时间的算法在图中查找三角形
Find a triangle in a graph using an algorithm with a specific run time
我需要找到一种在无向图中找到三角循环的算法。算法的运行时间应该是n^2,81
我真的不知道如何才能做到这一点。如果有人能提供帮助，那就太好了！
谢谢！
您搜索的算法是矩阵乘法。
将邻接矩阵与自身相乘 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 边路径的数量，一个三角形。
另一种方法是使用 Breadth-first search 算法的修改版本。试着想想你可以拥有的简单图形，一个三角形。从具有 BFS 的任何顶点开始并存储谁是父节点以及到根的距离。
每当您遇到一个已经访问过（但未完成的顶点）时，您可以使用简单的颜色灰色，您必须检查距离和父级。
B Start BFS from A: node A has dist=0, parent=Null
/ \ node B has dist=1, parent=A
/ \ node C has dist=1, parent=A
A - - C
比如你现在在C上，B他已经访问过了，A已经结束了（黑色），现在你检查C的相邻，你看到B，检查距离是否相同，是否相同parent，如果为真你就找到了一个三角形，如果没有你遇到了环但不是三角形。
这会比O(n^2)好
这个算法的复杂度（BFS）是顶点数+边数：O(|V| + |E|).
我需要找到一种在无向图中找到三角循环的算法。算法的运行时间应该是n^2,81
我真的不知道如何才能做到这一点。如果有人能提供帮助，那就太好了！
谢谢！
您搜索的算法是矩阵乘法。 将邻接矩阵与自身相乘 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 边路径的数量，一个三角形。
另一种方法是使用 Breadth-first search 算法的修改版本。试着想想你可以拥有的简单图形，一个三角形。从具有 BFS 的任何顶点开始并存储谁是父节点以及到根的距离。 每当您遇到一个已经访问过（但未完成的顶点）时，您可以使用简单的颜色灰色，您必须检查距离和父级。
B Start BFS from A: node A has dist=0, parent=Null
/ \ node B has dist=1, parent=A
/ \ node C has dist=1, parent=A
A - - C
比如你现在在C上，B他已经访问过了，A已经结束了（黑色），现在你检查C的相邻，你看到B，检查距离是否相同，是否相同parent，如果为真你就找到了一个三角形，如果没有你遇到了环但不是三角形。
这会比O(n^2)好
这个算法的复杂度（BFS）是顶点数+边数：O(|V| + |E|).