我正在使用算法第4版来稍微改进我的图论.这些书附带了大量的图形处理代码.
目前,我遇到了以下问题:如何在无向图中找到所有周期?我想修改现有的循环检测代码来做到这一点.
这是重要的部分:
private void dfs(Graph G, int u, int v) { marked[v] = true; for (int w : G.adj(v)) { // short circuit if cycle already found if (cycle != null) return; if (!marked[w]) { edgeTo[w] = v; dfs(G, v, w); } // check for cycle (but disregard reverse of edge leading to v) else if (w != u) { cycle = new Stack(); for (int x = v; x != w; x = edgeTo[x]) { cycle.push(x); } cycle.push(w); cycle.push(v); } } }
现在,如果我要找到所有循环,我应该删除在找到循环时返回的行,并且每次创建一个循环时我都会存储它.我无法弄清楚的部分是:算法什么时候停止?我怎么能确定我找到了所有周期?
以上代码甚至可以通过某种方式修改,以便我找到所有循环?