图的二种遍历-广度优先遍历和深度优先遍历

图的广度优先遍历

1.树的广度优先遍历

这样一个图中，是如何实现广度优先遍历的呢，首先，从1遍历完成之后，在去遍历2,3,4，最后遍历5 ，6 , 7  , 8。这也就是为什么叫做广度优先遍历，是一层一层的往广的遍历

不存在“回路”，搜索相邻的结点时，不可能搜到已经访问过的结点

树的广度优先遍历（层序遍历)

①若树非空，则根节点入队

②若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队

③重复②直到队列为空

2.图的广度优先遍历

图的广度优先和树的广度优先还是非常相似的，首先我们假设我们从 2 号结点开始，然后广度优先遍历 1 ,  6 （这里面1和6的顺序无所谓，但是还是为了保持一定的顺序，一般从小的开始）然后1的话再遍历就是5 ， 6再找相邻的就是 3 和 7 ，于是访问的就是 5 ，3  ，7 。在找到下一层就是 4 ，8 。

广度优先遍历(Breadth-First-Search, BFS)要点:

1．找到与一个顶点相邻的所有顶点·
2、标记哪些顶点被访问过
3．需要一个辅助队列

FirstNeighbor(G,x):求图G中顶点x的第一个邻接点，若有则返回顶点号。若x没有邻接点或图中不存在x，则返回-1。
NextNeighbor(G,x,y)︰假设图G中顶点y是顶点x的一个邻接点，返回除y之外顶点x的下一个邻接点的顶点号，若y是x的最后一个邻接点，则返回-1。
 

代码

bool visited [MAX_VERTEX_NUM];/访问标记数组
 
//广度优先遍历
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>= ;  w=NextNeighbor(G,v,w))
	//检测v所有邻接点
	if( !visited [w] )//w为v的尚未访问的邻接顶点
	{
	   visit(w);//访问顶点w
	   visited [w]=TRUE;//对w做已访问标记
	   EnQueue(Q,w);//顶点w入队列
 
	}
}

按照上面的例子，首先

我们先遍历到 2 ，2 放到队列，如果队列不空，把 1 和 6 放到队尾，然后 1号出队，和 1号邻的为

5和 2 ，由于 2被visit了所以访问未被访问的结点5,5号结点入队，都访问完了，看六号结点，六号结点出队。6号结点相邻的且未被访问的是3 ， 7 。visit 3 和 7 并且都放在队尾，然后看3 ，和3相邻的且未被访问的是4 号，访问4号结点，让4 号结点入队，最后，3号出队，看7号结点，与7号结点相邻的且未被访问的是8号结点。最后所有结点都被访问。

  

 

3.算法存在的问题和解决方案

前面介绍的都是连通图，如果是非连通图，那么上面算法就实现不了。我们可以直接从0号结点开始，遍历所有结点查看是否有未被访问的结点，找到第一个值为false的结点。从这个结点出发调用BFS。

 

代码

bool visited [MAX_VERTEX_NUM] ;   //访问标记数组
void BFSTraverse(Graph G){       //对图G进行广度优先遍历
   for( i=0; i
       visited[i]=FALSE;          //访问标记数组初始化
   InitQueue(Q);                //初始化辅助队列Q
   for( i=0; i//从0号顶点开始遍历
      if( !visited[i])            //对每个连通分量调用一次BFS
         BFS(G,i);               // vi未访问过，从vi开始BFS
}
 
bool visited [MAX_VERTEX_NUM];/访问标记数组
 
//广度优先遍历
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>= ;  w=NextNeighbor(G,v,w))
	//检测v所有邻接点
	if( !visited [w] )//w为v的尚未访问的邻接顶点
	{
	   visit(w);//访问顶点w
	   visited [w]=TRUE;//对w做已访问标记
	   EnQueue(Q,w);//顶点w入队列
 
	}
}

 

4.知识回顾与总结

 

---

 

图的深度优先遍历

1.树的深度优先遍历

树的深度优先遍历有点类似于先根遍历

首先遍历 1 2 5 6 3  4 7 8 ，它的遍历更趋向于先深层的遍历树。

 

2.图的深度优先遍历

首先我们可以先看一下2，和2相邻的是1号结点和6号结点。和2相邻的第一个结点是1，所以先访问1，1号结点未被访问。和1号结点相邻的为2 号和5号，但是2号被访问过了，所以看5号结点。和5号结点相邻的结点点都被访问过。这个顶点的DFS调用完，返回到1号接点调用层，但是1号节点调用都被调用完了，那么就可以返回2号结点调用层，2号结点身边的结点未被访问。即是6号结点。和6号结点相近的且未被访问的是 3和 7号结点，先访问3号结点，下一个应该被访问的是4号结点，和4号相邻的且未被访问的是7号结点，最后8号结点未被访问，访问一下8号结点。

 

代码

bool visited [MAX_VERTEX_NUM] ;//访问标记数组
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) ;
}

 

3.算法存在的问题和解决方案

与广度优先算法一样，如果存在非连通图，那么同样的，我们可以直接从0号结点开始，遍历所有结点查看是否有未被访问的结点，找到第一个值为false的结点。从这个结点出发调用BFS。

最终代码

bool visited [MAX_VERTEX_NUM];//访问标记数组
void DFSTraverse(Graph G){   //对图G进行深度优先遍历
   for( v=0; v
     visited[v]=FALSE;       //初始化已访问标记数据
   for( v=0 ; v//本代码中是从v=0开始遍历
     if( !visited[v])
       DFS(G,v);
}
 
 
bool visited [MAX_VERTEX_NUM] ;//访问标记数组
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) ;
}

4.知识回顾与总结