algorithm - 有向图 : checking for cycle in adjacency matrix

Question

关于 DFS 算法是否有另一种方法来检查用邻接矩阵表示的有向图中是否存在循环？

我找到了关于矩阵属性的零碎信息。也许我可以将矩阵 A 自身乘以 n 次，并检查每个结果矩阵中是否存在非零对角线。

虽然这种方法可能是正确的，但我如何才能显式提取表示循环的顶点列表？这个假设算法的复杂度如何？

预先感谢您的帮助。

Answer 1

假设在 n 次迭代之后，您有一个矩阵，其中 i 行和 j 列的单元格是 M[n ][i][j]

根据定义 M[n][i][j] = k 的总和 (M[n - 1][i][k] * A[k][j])。假设 M[13][5][5] > 0，这意味着它有一个长度为 13 的循环，从 5 开始到 5 结束。要有 M[13][5] [5] > 0，必须有一些 k 使得 M[12][5][k] * A[k][5] > 0。假设 k = 6，现在您知道循环 (6) 中的另一个节点。它还遵循 M[12][5][6] > 0 和 A[6][5] > 0

要使 M[12][5][6] > 0，必须有一些 k 使得 M[11][5][ k] * A[k][6] > 0。假设 k = 9，现在，您知道循环 (9) 中的另一个节点。它还遵循 M[11][5][9] > 0 和 A[9][6] > 0

然后，您可以重复执行相同的操作以找到循环中的其他节点。