如何在有向图中找到最短的有向环?
How to find the shortest directed cycle in a directed graph?
来自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的,但是给出的伪代码不能用来重构路径,只能求最短循环的长度
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
.
不涉及拓扑排序
来自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的,但是给出的伪代码不能用来重构路径,只能求最短循环的长度
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
.
不涉及拓扑排序