使用 DFS 计算有向图中的循环数

Question

我想计算有向图中可用的有向循环总数（只需要计数）。

您可以假设图形是作为邻接矩阵给出的。

我知道DFS但无法为这个问题制定一个有效的算法。

请提供一些使用DFS.

Answer 1

让我们考虑一下，我们用三种类型的颜色对节点进行着色。如果节点尚未被发现，则其颜色为白色。如果该节点已被发现，但其任何后代尚未被发现，则其颜色为灰色。否则其颜色为黑色。现在，在进行 DFS 时，如果我们遇到这样的情况，两个灰色节点之间有一条边，那么图就有环。循环总数将是我们遇到上述情况的总次数，即我们在两个灰色节点之间找到一条边。