如何在有向图中找到最短的有向环？

Question

来自https://algs4.cs.princeton.edu/42digraph/

Shortest directed cycle. Given a digraph, design an algorithm to find a directed cycle with the minimum number of edges (or report that the graph is acyclic). The running time of your algorithm should be proportional to E V in the worst case.

解决方法在这里：https://algs4.cs.princeton.edu/42digraph/ShortestDirectedCycle.java.html

public ShortestDirectedCycle(Digraph G) {
    Digraph R = G.reverse();
    length = G.V() + 1;
    for (int v = 0; v < G.V(); v++) {
        BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(R, v);
        for (int w : G.adj(v)) {
            if (bfs.hasPathTo(w) && (bfs.distTo(w) + 1) < length) {
                length = bfs.distTo(w) + 1;
                cycle = new Stack<Integer>();
                for (int x : bfs.pathTo(w))
                    cycle.push(x);
                cycle.push(v);
            }
        }
    }
}

这个解决方案对我来说很有意义，除了第一行 G.reverse()。为什么？跟拓扑排序有关系吗？

SO 上有很多关于在有向图中查找所有循环的问题，但我假设有比查找所有循环并比较它们的长度更好的方法。有一些关于寻找最短有向循环的问题，但 none 有一个可以接受的答案。

How can I find the shortest cycle in a Directed, Weighted Graph?

Finding shortest cycles in directed or undirected graph（这个用于无向图）

我也找到了一个paper使用BFS的，但是给出的伪代码不能用来重构路径，只能求最短循环的长度

Answer 1

G.reverse() 是与 G 相同的有向图，除了 每个边都反转；因此，举例来说，如果 G 有一条从 v 到 w 的边，那么 G.reverse() 就有一条从 w 到 v 的边。

由于bfs取自G.reverse()和v，bfs.hasPathTo(w)表示"whether G has a path from w to v"，bfs.distTo(w)表示"the length of G's path from w to v" . （如果 bfs 取自 G 而不是 G.reverse()，它会检测到相反方向的路径。）

所以它使用的循环查找算法是：对于 G 中的每条边 (v,w)，测试 G 是否有从 w 回到 v.

不涉及拓扑排序

如何在有向图中找到最短的有向环？

How to find the shortest directed cycle in a directed graph?

algorithm

data-structures

graph-theory

breadth-first-search