无向图----深度优先搜索

public class DepthFirstPaths {
	private boolean[] marked;    //标记已经访问过的结点
	private int count;
	
	public DepthFirstPaths(Graph G,int s) {//以s作为起始顶点深度优先遍历无向图G
		marked = new boolean[G.V()];
		dfs(G,s);  //调用真正的深度优先遍历方法
	}
	//深度优先遍历
	private void dfs(Graph G,int v) {
		marked[v] = true;//标记当前顶点
		count++;
		for(int w: G.adj(v))
			if(!marked[w])	dfs(G,w);//递归访问它所有没有标记过的相邻顶点
	}
	
	public boolean marked(int w) {return marked[w];}
	public int count() {return count;}
}

private void dfs(Graph G,int v){
    marked[v] = true;
    for(int w : G.adj(v))
        if(!marked[w]){
            edgeTo[w] = v;    //只是多了这一条语句，保存路径中当前节点的上一节点
            dfs(G,w);
        }
}

public Iterable<Integer> pathTo(int v){
    if(!hasPathTo(v)) return null;
    Stack<Integer> path = new Stack<Integer>();//用栈保存路径
    for( int x = v; x!=s;x = edgeTo[x])  //从顶点向下搜索
        path.push(x);    //路径上的结点进栈
    path.push(s); 
    return path;
}

public CC(Graph G){
    marked = new boolean[G.V()];
    id = new int[G.V()];
    for(int s = 0; s<G.V(); s++)
        if(!marked[s]){
            dfs(G,s); 
            count++;    //连通分量个数加一
        }
}

private void dfs(Graph G, int v){
    marked[v] = true;
    id[v] = count;    //同一个连通分量下id[]值相同
    for(int w:G.adj(v)
        if(!marked[w])
            dfs(G,w);
}