广度和深度优先遍历

 广度优先遍历思想：

        广度优先遍历其实就相当于树的层序遍历呐。广度嘛，简单理解就是一层一层去遍历。比如先从顶点v出发，那么就访问v的所有邻接点（比如v1，v2），是所有邻接点！！然后再访问v1的所有邻接点，v2的邻接点，以此类推，直到所有顶点都访问完。

       是不是和树的层序遍历很像？但是有一点区别，那就是树是没有环的而且自顶向下，也就意味着它是不会重复访问同一个顶点，但是图会啊，它存在这种可能，所以我们需要建立一个访问标记数组并将所有顶点初始化为false表示还没访问过，每访问一次顶点就将它标记为true表示已访问。

void BFSTraverse(Graph G){
	for(int i=0;i<G.vexnum;i++)
		visited[i]=FALSE; //访问标记数组初始化
	InitQueue(Q); //初始化辅助队列
	for(int i=0;i<G.vexnum;i++) //从0开始遍历，考虑非连通图的情况
		if(!visited[i])  //对每个连通分量执行一次BFS 
			BFS(G,i);				 				 
}

//BFS 广度优先遍历
void BFS(Graph G,int v){ //从顶点v出发，广度优先遍历图G 
	visit(v);	//访问初始顶点v 
	visited[v]=TRUE; //对顶点v进行标记
	EnQueue(Q,v); //顶点v入队列Q
	while(!isEmpty(Q)){ //检查队列是否为空
		DeQueue(Q,v); //顶点v出队
		for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){//遍历循环顶点v的所有邻接点
			//检测v的所有邻接点
			if(!visited[w]){
				visit(w);	//访问邻接点w
				visited[w]=TRUE; //对该顶点进行标记
				EnQueue(Q,w);//并入队。 
			} 
		} 	
	}	
} 

对于无向图来说，调用BFS函数的次数=连通分类数

空点复杂度：最坏情况，辅助队列大小为O(|v|)

时间复杂度：

（1）若是邻接矩阵存储的图：访问|v|个顶点需要O(|v|)的时间。查找每个顶点的邻接顶点都需要O(|v|)的时间，而总共有|v|个顶点。所以时间复杂度为O()  ，实则是O(|v|+)，但是时间复杂度只看次数大的，小的可以忽略掉。

（2）若是邻接表存储的图：访问|v|个顶点需要O(|v|)的时间。查找每个顶点的邻接顶点都需要O(|e|)的时间，所以时间复杂度为O(|v|+|e|)。