algorithm - 在有向图中寻找最短循环的算法

Question

最短循环是具有最少边数的循环。

例如，给定一个图形：

最短周期为：ACDA、DABD

如果我只需要找到一个最短的循环，我会在每个顶点上运行 BFS 并跟踪最小的循环。但我不知道如何枚举所有最小的周期。

关于枚举有向图中的最小循环有一个类似的SO 问题，但是最小循环不是较小循环的联合。在这里，我只寻找边数最少的循环。

Answer 1

像拓扑排序一样运行许多 DFS 搜索：从一个随机顶点开始，只要有一些未探索的顶点，就继续运行新的 DFS 搜索。

在搜索中，一旦找到后边缘，您就知道 (1) 有一个循环 (2) 该循环中的边数。如果您还需要获取循环中的边列表，请为每个“当前检测到的循环”保留一个数组，并在 DFS 调用图中回溯时填充它。如果后边是节点 A->B，当您到达节点 B 时，数组将包含循环中的所有边。

当然，要跟踪“迄今为止发现的最短周期”，以避免记录比此最小值更长的周期的边缘列表。