用栈存路径信息
public class DepthFirstPaths {
private boolean[] marked;
private int[] edgeTo;//当前节点下一节点信息
private final int s;
public DepthFirstPath(Grath G, int s) {
marked = new boolean[G.V()];
edgeTo = new int[G.V()];
this.s = s;
dfs(G, s)
}
private void dfs(Grath G, int v) {
marked[v] = true;
for(int w : G.adj(v)) {
if(!marked[w]) {
edgeTo[w] = v;
bfs(G, w);
}
}
public boolean hasPathTo(int v) { return marked[v]; }
public Iterable pathTo (int v) {
if(!hasPathTo(v) return null; 经过深度搜索后未访问过该节点
Stack<Integer> path = new Stack<>();
for(int x = v; x != s; x = edgeTo(x))
path.push(x);
path.push(s);
return path;
}
}
网友评论