3.图的遍历

广度优先搜索

类似于二叉树的层序遍历，不同点是二叉树的只需要遍历一次就能全部遍历完，图的遍历完后如果还有顶点没有遍历到就选一个没遍历的结点接着遍历，算法需要截距一个辅助队列，记录正在访问结点的下一层顶点，同时还需要一个辅助数组visvited[ ]标记顶点是否被访问过

bool visited[MAX VERTEX NUM]; //访问标记数组
void BFSTraverse(Graph G){ //对图G进行广度优先遍历
for (i=0;i<G.vexnum;++i)
	visited[i]=FALSE; //访问标记数组初始化
InitQueue (Q); //初始化辅助队列Q
for (i=0;i<G.vexnum;++i)//从0号顶点开始遍历
	if(!visited[i])//对每个连通分量调用一次BFS
		BES(G,i); //vi未访问过，从vi开始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所有邻接点

			if(！visited[w]){ //W为ⅴ的尚未访问的邻接顶点
 
				visit (w); //访问顶点w

				visited[w]=TRUE;//对w做已访问标记
				EnQueue(Q,w);//J顶点w入队列
			}//if
	}//while
}

BFS算法的性能分析

1. 邻接矩阵存储的图时间复杂度$O(\mid V\mid^2)$
2. 邻接表存储的图时间复杂度$O(\mid V\mid+\mid E\mid)$
3. 无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q,n个顶点均需入队一次，在最坏的情况下，空间复杂度为$O(\mid V\mid)$

深度优先搜索

图的深度优先搜索类似于树的先序遍历

它的基本思想如下：首先访问图中某一起始顶点，然后由v出发，访问与v邻接且未被访问的任意一个顶点w1,再访问与w,邻接且未被访问的任意一个顶点w2…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

bool visited [MAX VERTEX NUM]; //访问标记数组
void DFSTraverse(Graph G){ //对图G进行深度优先遍历
	for(V=0;V<G.vexnum;++v)
		visited [v]=FALSE; //初始化已访问标记数据
	for(V=0;V<G.vexnum;++v) //本代码中是从V=0开始遍历
		if(!visited [v])
			DFS(G,V);
}
void DFS(Graph G,int v){ //从顶点V出发，深度优先遍历图G
	visit(v); //访问顶点V
	visited [v]=TRUE; //设已访问标记
	for(w=FirstNeighbor(G,V)W>=0;W=NextNeighor(G,v,W))
		if(!visited [w]){ //W为U的尚未访问的邻接顶点
			DFS(G,W);
		} //if
}

DFS算法的性能分析

1. 邻接矩阵存储的图时间复杂度$O(\mid V\mid^2)$
2. 邻接表存储的图时间复杂度$O(\mid V\mid+\mid E\mid)$
3. 无论是邻接表还是邻接矩阵的存储方式，DFS算法都需要借助一个辅助队列Q,n个顶点均需入队一次，在最坏的情况下，空间复杂度为$O(\mid V\mid)$

图的遍历与图的连通性

• 对无向图进行BFS/DFS遍历调用BFS/DFS函数的次数=连通分量数,对于连通图，只需调用1次BFS/DFS
• 对有向图进行BFS/DFS遍历调用BFS/DFS函数的次数要具体问题具体分析,若起始顶点到其他各顶点都有路径，则只需调用1次BFS/DFS函数,对于强连通图，从任一结点出发都只需调用1次BFS/DFS