深度优先遍历

深度就是不断往下渗透，

然后标记是否访问过，如果没有就继续往下渗透，然后再往上回到当初的位置

就和树递归差不多

 

这是一个图

我们从图中可以看到 0有四个连接点 0 1 2 5 6 我们要把遍历出来

遍历流程（红色没有访问过 蓝色是标记 访问 最后都会变成红色 ）

我们从零开始，然后往下渗透到1，没有元素了 然后再往上回溯， 再往2

 

0 1遍历了

然后1 回到0

1颜色变回红色

0 然后再去遍历2

又回到0 颜色变回红色

然后

又去5节点，

5的节点有0 3 4

但是0是蓝色 所以已经遍历过了

所以就不在遍历0 往下继续遍历

下一个是3 我们就遍历她

3有4 5 但是5 已经遍历了 所以我们继续往下遍历 4

 

4遍历了继续往下遍历 在遍历 6

已经遍历完了

 

 

 

最后就是这样的了

 

 

 

联通分量就是 看多少个图

看的是连通性

这就是三个图

需要标记是否被访问过 visited来访问

//图的深度优先遍历
    void dfs(int v){
        
        visited[v]=true;
        id[v]=ccount;
        
        for(int i:G.adj(v)){
            if(!visited[i])
                dfs(i);
        }
    }

package com.binglian.Graph;

//求无权图的联通分量
public class Components {

	Graph G;					//图的引用
	private boolean[] visited;	//记录dfs的过程中节点是否被访问
	private int ccount;			//记录联通分量个数
	private int[] id;			//每个节点对应的联通分量标记
	
	
	//图的深度优先遍历
	void dfs(int v){
		
		visited[v]=true;
		id[v]=ccount;
		
		for(int i:G.adj(v)){
			if(!visited[i])
				dfs(i);
		}
	}
	
	//构造函数，求出无权图的联通分量
	public Components(Graph graph){
		
		//算法初始化
		G=graph;
		visited=new boolean[G.V()];
		id=new int[G.V()];
		ccount=0;
		for(int i=0;i<G.V();i++){
			visited[i]=false;
			id[i]=-1;
		}
		
		//求图的联通分量
		for(int i=0;i<G.V();i++)
			if(!visited[i]){//判断是否访问没有 如果没有访问就进行递归dfs
				dfs(i);
				ccount++;
			}
	}
	
	
	//返回图的联通分量个数
	int count(){
		return ccount;
		
	}
	
	//查询点v和w是否联通
	boolean isConnected(int v,int w){
		assert v>=0 && v<G.V();
		assert w>=0 && w<G.V();
		
		return id[v]==id[w];
	}
	
}