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

Question

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

algorithmdata-structuresgraph-theorybreadth-first-search

4

https://algs4.cs.princeton.edu/42digraph/ 来源：

最短有向环。 给定一个有向图，设计一种算法来找到具有最小边数的有向环（或报告该图为无环图）。您的算法在最坏情况下的运行时间应该与 E V 成比例。

解决方案可以在此处找到：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上有很多关于在有向图中找到所有循环的问题，但我假设还有比找到所有循环并比较它们的长度更好的方法。有一些关于查找最短有向循环的问题，但没有一个可以接受的答案。如何在有向加权图中找到最短循环？查找图中的最短循环在有向或无向图中查找最短循环（这是针对无向图的）

我也发现了一个使用BFS的论文，但所提供的伪代码无法用于重构路径，只能用于查找最短循环的长度。

- Abhijit Sarkar

2

这个问题实际上是在Coursera算法第二部分课程中提出的。考虑到该课程和您提供的链接来自同一位作者，这个答案是正确的。我认为这个解决方案的主要思想是：如果你在一个直线图中有一些邻居，并且你可以通过反向图以某种方式到达它，那么它就是一个循环。我认为最相似的算法是Kosaraju算法，它会翻转一个图来查找强连通分量。 - vortexwolf

1

"@vorrtex “这个问题实际上是在Coursera算法第二部分课程中提出的。考虑到该课程和您的链接都来自同一位作者...” 这是否有相关性？这个问题在别处由谁问并不重要吧？" - Abhijit Sarkar

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ruakh · Accepted Answer

G.reverse()是一个有向图，它与G相同，只是每条边的方向被反转了；举例来说，如果G从v到w有一条边，则G.reverse()从w到v有一条边。

由于bfs是从G.reverse()和v中取得的，因此bfs.hasPathTo(w)意味着“是否存在一条从w到v的路径”；bfs.distTo(w)表示“从w到v的路径长度”(如果bfs是从G而不是G.reverse()中取得，则会检测到相反方向的路径)。

因此，它使用的循环查找算法是：对于G中的每条边(v,w)，测试是否G存在一条从w返回v的路径。

拓扑排序并没有涉及。