@@ -0,0 +1,2645 @@
+package me.alivecode.algs4;%0A%0Aimport edu.princeton.cs.algs4.In;%0Aimport edu.princeton.cs.algs4.StdOut;%0A%0A/**%0A * The %7B@code DepthFirstPaths%7D represents a data type for finding paths%0A * from source vertex to every other vertices in undirected graph.%0A */%0Apublic class DepthFirstPaths %7B%0A    private int%5B%5D edgeTo; // edgeTo%5Bv%5D = last edge on s-v path.%0A    private boolean%5B%5D marked; // marked%5Bv%5D = is there a s-v path?%0A    private final int s; // the source vertex;%0A%0A    public DepthFirstPaths(Graph G, int s) %7B%0A        edgeTo = new int%5BG.V()%5D;%0A        marked = new boolean%5BG.V()%5D;%0A        this.s = s;%0A        validateVertex(s);%0A        dfs(G, s);%0A    %7D%0A%0A    /**%0A     * computes paths from v to ervery vertices in G%0A     * %3Cem%3Ethe order of vertices in path v-s is same as the order that %0A     * initializing the graph G.%3C/em%3E%0A     */%0A    private void dfs(Graph G, int v) %7B%0A        validateVertex(v);%0A        marked%5Bv%5D = true;%0A        for(int w : G.adj(v)) %7B%0A            if (!marked%5Bw%5D) %7B%0A                edgeTo%5Bw%5D = v;%0A                dfs(G, w);%0A            %7D%0A        %7D%0A    %7D%0A%0A    private void validateVertex(int v) %7B%0A        int V = marked.length;%0A        if (v %3C 0 %7C%7C v %3E= V) %0A            throw new IllegalArgumentException(v + %22 is not between 0 and %22 + (V-1));%0A    %7D%0A    %0A    /**%0A     * Is there a path from s to v?%0A     */%0A    public boolean hasPathTo(int v) %7B%0A        validateVertex(v);%0A        return marked%5Bv%5D;%0A    %7D%0A%0A    /**%0A     * Returns the path from s to v if s connected to v.%0A     */%0A    public Iterable%3CInteger%3E pathTo(int v) %7B%0A        validateVertex(v);%0A        if (!hasPathTo(v)) return null;%0A%0A        Stack%3CInteger%3E path = new Stack%3CInteger%3E();%0A        for(int x = v; x != s; x = edgeTo%5Bx%5D) %7B%0A            path.push(x);%0A        %7D%0A        path.push(s);%0A        return path;%0A    %7D%0A%0A    // unit test code%0A    // Execute: java me.alivecode.algs4.DepthFirstPaths input.txt 0%0A    public static void main(String%5B%5D args) %7B%0A        In in = new In(args%5B0%5D);%0A        Graph G = new Graph(in);%0A        int s = Integer.parseInt(args%5B1%5D);%0A        DepthFirstPaths path = new DepthFirstPaths(G, s);%0A%0A        for(int v = 0; v %3C G.V(); v++) %7B%0A            if (path.hasPathTo(v)) %7B%0A                StdOut.print(s + %22 to %22 + v + %22: %22);%0A                for(int x : path.pathTo(v)) %7B%0A                    if (s == x) %7B%0A                        StdOut.print(x);%0A                    %7D%0A                    else %7B%0A                        StdOut.print(%22-%22 + x);%0A                    %7D%0A                %7D%0A                StdOut.println();%0A            %7D%0A            else %7B%0A                StdOut.printf(%22%25d not connected to %25d.%5Cn%22, s, v);%0A            %7D%0A        %7D%0A    %7D%0A%7D%0A

Add DepthFirstPaths, a data type for finding paths from source vertex to every other vertices in the graph.