n*******e
发帖数: 37 | 1 给一个directed graph，要求打印出所有的环。
不知道我的Java code可行吗? 我用DFS traverse, 同时记住现在的path, 当侦测到
back edge时, 就打印出path中的cycle部分。
public void printCyclesInDirectedGraph(int n, int[] edges) {
List> graph = new ArrayList>(n);
for (int i = 0; i < n; i++)
graph.add(new LinkedList());
for (int [] e : edges)
graph.get(e[0]).add(e[1]);
int[] visited = new int[n];
for (int i = 0; i < n; i++) {
if (visited[i] == 0) {
List path = new ArrayList(n);
dfs(i, visited, graph, path);
}
}
}
private void dfs(int node, int[] visited,
List> graph, List path) {
path.add(node);
// mark the node as visited and on the current path.
visited[node] = 2;
for (int child : graph.get(node)) {
if (visited[child] == 2) {
// if the child is on the current path,
// then we found a back edge.
// so print the cycle.
print(child, path);
} else if (visited[child] == 0) {
// the child is not visited yet.
dfs(child, visited, graph, path);
}
}
// mark the node as visited, but not on the path.
visited[node] = 1;
path.remove(path.size() - 1);
}
private print(int node, List path) {
// print the cycle in the path.
// start from the node, and stop when encounter the same node.
System.out.println(node);
for (int i = path.size() - 1; path.get(i) != node; i--) {
System.out.println(", " + path.get(i));
}
} |
|
