在有向图中寻找最短周期的算法

有一个类似的 SO问题，但是最小循环是不是较小循环的并集的循环。在这里，我只寻找具有最少边数的循环。

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

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

当然，要跟踪到目前为止发现的最短周期，以避免记录边界列表的周期长于此最小值。

A shortest cycle is one with the minimum number of edges.

For example, given a graph:

The shortest cycles are: ACDA, DABD

If I only needed to find one shortest cycle, I would just run BFS on every vertex and keep track of the smallest cycle. But I don't know how to enumerate all smallest cycles.

There is a similar SO question on enumerating minimal cycles in a digraph, but there a minimal cycle is one which is not a union of smaller cycles. Here I am only looking for the cycles with the minimum number of edges.

Run a number of DFS searches as in topological sort: start from a random vertex, and continue running new DFS searches as long as there are some unexplored vertices.

In a search, as soon as you find a back edge, you know that (1) there's a cycle (2) the number of edges in that cycle. If you also need to get a list of edges in the cycle, keep an array for each "currently detected cycle" and fill it as you backtrack in the DFS call graph. If the back-edge was a node A->B, When you'll reach back node B, the array is going to contain all edges in the cycle.

Of course, keep in track the "shortest cycle found so far" to avoid bookkeeping edge lists for cycles that are longer than this minimum.