java">public class DepthFirstPaths {
    private boolean marked[];// 用于存放被标记过的顶点
    private int edgeTo[];// 数组内的元素表示某顶点，其索引表示某顶点的相邻顶点。
    private final int s;// 起点
    private int count;// 已遍历顶点的数量

    public DepthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G, s);
    }


    public void dfs(Graph G, int s) {
        marked[s] = true;
        count++;
        for (int w : G.adj(s)) {
            if (!marked[w]) {
                edgeTo[w] = s;
                dfs(G, w);
            }
        }
    }
    public boolean hasPathTo(int v) {
        return marked[v];
    }
    /**
     * 返回到达顶点v的路径
     *edgeTo[]数组内的元素表示某顶点，其索引表示某顶点的相邻顶点。pathto方法用于将edgeTo数组转换为一个stack，而该stack则表示一条从顶点w到顶点v的路径
     * @param v
     * @return stack
     */
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v))
            return null;
        Stack<Integer> stack = new Stack<Integer>();
        for (int x = v; x != s; x = edgeTo[x])
            stack.push(x);
        stack.push(s);
        return stack;
    }
}

Queue

java">import java.util.Iterator;

public class Stack<Item> implements Iterable<Item> {
    private Node first;// 头结点
    private int N; // 栈中元素个数
    private class Node {
        Item item;
        Node next;
    }
    public void push(Item item) {
        Node oldfirst = first;
        first = new Node();
        first.item = item;
        first.next = oldfirst;
        N++;
    }
    public Item pop() {
        Item item = first.item;
        first = first.next;
        N--;
        return item;
    }
    public boolean isEmpty() {
        return N == 0;
    }
    public int size() {
        return N;
    }
    public Iterator<Item> iterator() {
        return new listIterator();
    }
    private class listIterator implements Iterator<Item> {
        private Node current = first;
        public boolean hasNext() {
            return current != null;
        }
        // 获取头结点
        public Item next() {
            Item item = current.item;
            current = current.next;
            return item;
        }
    }
}