继无向图 深度搜索路径

用栈存路径信息

---

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;

}

}