import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 深度优先图的路径查找
 */public class DepthFirstPath {
    private boolean[] marked;
    private int s;//起点
    private int[] edgeTo;//索引代表顶点，值代表从s到当前顶点路径上的最后一个顶点

    public DepthFirstPath(Graph g, int s) {
        this.s = s;
        edgeTo = new int[g.getV()];
        marked = new boolean[g.getV()];
        dfs(g, this.s);
    }

    /**
     * 深度优先搜索出与v顶点相连的顶点
     *
     * @param graph
     * @param v
     */    public void dfs(Graph graph, int v) {
        marked[v] = true;
        for (Integer w : graph.adj(v)) {
            if (!marked[w]) {
                edgeTo[w] = v;// 到达顶点w的最后一个顶点是v
                dfs(graph, w);
            }
        }

    }

    /**
     * 是否存在路径从s到v
     *
     * @param v
     * @return boolean
     */    public boolean hasPathTo(int v) {
        return marked[v];
    }

    /**
     * 从s到v的路径
     *
     * @param v
     * @return
     */    public Stack<Integer> pathTo(int v) {
        Stack<Integer> pathStack = new Stack<>();
        if (marked[v]) {
            int lastEdge = v;
            while (lastEdge != s) {
                pathStack.push(lastEdge); // 存储上一个节点
                lastEdge = edgeTo[lastEdge];
            }
            pathStack.push(s);
            return pathStack;
        }
        return pathStack;
    }

}