我遇到了超级麻烦。我真的不知道如何修改代码以打印已找到的每个循环。实际上,如果图形包含循环,下面的代码将返回,但我也想知道所有可能的循环是什么。例如,下图包含三个循环 0->2->0、0->1->2->0 和 3->3,因此您的函数必须返回 true。// A Java Program to detect cycle in a graphimport java.util.ArrayList;import java.util.LinkedList;import java.util.List;class Graph { private final int V; private final List<List<Integer>> adj; public Graph(int V) { this.V = V; adj = new ArrayList<>(V); for (int i = 0; i < V; i++) adj.add(new LinkedList<>()); } // This function is a variation of DFSUytil() in // https://www.geeksforgeeks.org/archives/18212 private boolean isCyclicUtil(int i, boolean[] visited, boolean[] recStack) { // Mark the current node as visited and // part of recursion stack if (recStack[i]) return true; if (visited[i]) return false; visited[i] = true; recStack[i] = true; List<Integer> children = adj.get(i); for (Integer c: children) if (isCyclicUtil(c, visited, recStack)) return true; recStack[i] = false; return false; } private void addEdge(int source, int dest) { adj.get(source).add(dest); } // Returns true if the graph contains a // cycle, else false. // This function is a variation of DFS() in // https://www.geeksforgeeks.org/archives/18212 private boolean isCyclic() { // Mark all the vertices as not visited and // not part of recursion stack boolean[] visited = new boolean[V]; boolean[] recStack = new boolean[V]; // Call the recursive helper function to // detect cycle in different DFS trees for (int i = 0; i < V; i++) if (isCyclicUtil(i, visited, recStack)) return true; return false; }非常感谢。
添加回答
举报
0/150
提交
取消