@@ -0,0 +1,2556 @@
+/**%0A * Company%0A * Copyright (C) 2014-2017 All Rights Reserved.%0A */%0Apackage com.cwenao.datastructure.graph;%0A%0Aimport org.slf4j.Logger;%0Aimport org.slf4j.LoggerFactory;%0A%0Aimport java.util.Stack;%0A%0A/**%0A * @author cwenao%0A * @version $Id DepthFirstPaths.java, v 0.1 2017-08-20 08:24 cwenao Exp $$%0A */%0Apublic class DepthFirstPaths %7B%0A    %0A    private static final Logger LOG = LoggerFactory.getLogger(DepthFirstPaths.class);%0A    %0A    private boolean%5B%5D marked;%0A    private int%5B%5D edgeTo;%0A%0A    private Graph%3CInteger%3E graph;%0A    private int source;%0A%0A    public DepthFirstPaths(Graph%3CInteger%3E graph, int source) %7B%0A        marked = new boolean%5Bgraph.getV()%5D;%0A        edgeTo = new int%5Bgraph.getV()%5D;%0A        checkedVertex(source);%0A        this.graph = graph;%0A        this.source = source;%0A    %7D%0A%0A    public void dfs() %7B%0A        dfs(graph,source);%0A    %7D%0A%0A    private void dfs(Graph%3CInteger%3E graph, int source) %7B%0A        marked%5Bsource%5D = true;%0A        for (int w : graph.adj(source)) %7B%0A            if (!marked%5Bw%5D) %7B%0A                edgeTo%5Bw%5D = source;%0A                dfs(graph, w);%0A            %7D%0A        %7D%0A    %7D%0A%0A    public boolean hasPathTo(int v) %7B%0A        checkedVertex(v);%0A        return marked%5Bv%5D;%0A    %7D%0A%0A    public Iterable%3CInteger%3E pathTo(int v) %7B%0A        checkedVertex(v);%0A        if (!hasPathTo(v)) %7B%0A            return null;%0A        %7D%0A%0A        Stack%3CInteger%3E stack = new Stack%3C%3E();%0A        for (int x = v; x !=source;x = edgeTo%5Bx%5D) %7B%0A            stack.push(x);%0A        %7D%0A        stack.push(source);%0A%0A        return stack;%0A    %7D%0A%0A    private void checkedVertex(int v) %7B%0A        if (v %3C 0 %7C%7C v %3E marked.length) %7B%0A            throw new IllegalArgumentException(%22the vertex is must between 0 and %22 + (marked.length - 1));%0A        %7D%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Graph%3CInteger%3E graph = new Graph%3C%3E(7);%0A        graph.addEdge(0, 1);%0A        graph.addEdge(0, 2);%0A        graph.addEdge(0, 3);%0A        graph.addEdge(2, 4);%0A        graph.addEdge(4, 5);%0A        graph.addEdge(5, 6);%0A%0A        int source = 0;%0A        DepthFirstPaths depthFirstPaths = new DepthFirstPaths(graph, source);%0A        depthFirstPaths.dfs();%0A%0A        for (int v=0;v%3Cgraph.getV();v++) %7B%0A            if (depthFirstPaths.hasPathTo(v)) %7B%0A                LOG.info(%22%7B%7D to %7B%7D : %22, source, v);%0A                for (int x : depthFirstPaths.pathTo(v)) %7B%0A                    if (x == source) %7B%0A                        LOG.info(%22%7B%7D%22, x);%0A                    %7D else %7B%0A                        LOG.info(%22-%7B%7D%22, x);%0A                    %7D%0A                %7D%0A            %7D%0A        %7D%0A    %7D%0A%0A%7D%0A

add the depth first path