/**
 * Company
 * Copyright (C) 2014-2017 All Rights Reserved.
 */
package com.cwenao.datastructure.graph;

/**
 * @author cwenao
 * @version $Id DepthFirstSearchByAdjacentList.java, v 0.1 2017-08-13 08:43 cwenao Exp $$
 */
public class DepthFirstSearchByAdjacentList<T extends Comparable> {

    private boolean[] marked; //标识已经走过的路径

    private int count; //标识连接数量

    private Graph<Integer> graph; //输入图

    private int data; //需要查找的顶点

    public DepthFirstSearchByAdjacentList(Graph<Integer> graph,int data) {

        marked = new boolean[graph.getV()];
        checkedVertexs(data);
        this.graph = graph;
        this.data = data;
    }


    public void dfs() {
        dfs(graph, data);
    }

    /**
     * recursion the dfs
     * @param graph
     * @param v
     */
    private void dfs(Graph<Integer> graph, int v) {
        count++;
        marked[v] = true;
        for (int w : graph.adj(v)) {
            if (!isMarked(w)) {
                dfs(graph, w);
            }
        }
    }

    public boolean isMarked(int v) {
        checkedVertexs(v);
        return marked[v];
    }

    public int getCount() {
        return count;
    }

    private void checkedVertexs(int v) {
        if (v < 0 || v > marked.length) {
            throw new IllegalArgumentException("vertex : " + v + "is not between 0 and " + (marked.length - 1));
        }
    }

    public static void main(String[] args) {
        Graph<Integer> graph = new Graph<>(7);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(0, 3);
        graph.addEdge(2, 4);
        graph.addEdge(4, 5);
        graph.addEdge(5, 6);

        DepthFirstSearchByAdjacentList dfs = new DepthFirstSearchByAdjacentList(graph, 0);

        dfs.dfs();

        for(int v = 0;v<graph.getV();v++) {
            if (dfs.isMarked(v)) {
                System.out.println("the vertex is : " +v);
            }
        }

    }

}

@@ -105,16 +105,34 @@
 h;%0A%0A/**%0A
+ * %E5%AE%9E%E7%8E%B0%E5%9F%BA%E4%BA%8E%E9%82%BB%E6%8E%A5%E8%A1%A8%E7%9A%84%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2%0A
  * @auth

add the implements with stack