【开卷数据结构 】图的遍历，广搜和深搜（基础）

目录

图的遍历

广度优先搜索

代码演示

深度优先搜索

 代码演示

图的遍历

Q：什么是图的遍历

A：图的遍历是指从图的某一顶点出发，按照某种搜索方式沿着图中的边对图中的所有结点访问一次且仅访问一次。

因为图的任一顶点都可能和其余的顶点相邻接，所以在访问某个顶点后，可能沿着某条路径搜索又回到该项点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点，为此可以设一个辅助数组 visited[] 来标记顶点是否被访问过。图的遍历算法主要有两种：广度优先搜索和深度优先搜索。

广度优先搜索

Q：什么是广度优先搜索

A：广度优先搜索（BFS）类似于二叉树的层序遍历算法。其基本思想是基本思想是：首先访问起始顶点 v，接着由 v 出发，依次访问 v 的各个未访问过的邻接顶 w1，w2，…… wi，然后依次访问 w1，w2，…… wi，的所有未被访问过的邻接顶点。 再从这些访问过的顶点出发，访问它们所有未被访问过的邻接顶点，直至图中所有顶点都被访问过为止。

若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作为始点，重复上述过程，直至图中所有顶点都被访问到为止。

广度优先搜索是一种分层的查找过程，每向前走一步可能访问一此顶点，没有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的下一层顶点。

我们对这张图进行广度优先搜索。假设从 a 结点开始访问，a 先入队。此时队列非空，取出队头元素 a，由于 b，c 与 a 邻接且未被访问过，于是依次访问 b，c，并将 b，c依次入队。队列非空，取出队头元素 b，依次访问与 b 邻接且未被访问的顶点 d，e，并将 d，e 入队（注意：a与b也邻接，但 a 已置访问标记，故不再重复访问）。此时队列非空，取出队头元素 c，访问与 c 邻接且未被访问的顶点 f，g，并将 f，g 入队。此时，取出队头元素 d，但与 d 邻接且未被访问的顶点为空，故不进行任何操作。继续取出队头元素 e，将 h 入队列……最终取出队头元素 h 后，队列为空，从而循环自动跳出。遍历结果为 abcdefgh。

---

代码演示

---

   

    

     

      

     
     

      

       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
      
     
    

     

      

     
     

      
			
       BFS(G,i) ;					
       //v；未访问过，从 v：开始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))
      
     
    

     

      

     
     

      

       		{								
       //检测v所有邻接点 
      
     
    

     

      

     
     

      
			
       if(!visited[w]){			
       //w为v的尚未访问的邻接顶点
      
     
    

     

      

     
     

      
				
       visit(w);				
       //访问顶点w
      
     
    

     

      

     
     

      

       				visited[w]=TRUE;		
       //对w做已访问标记
      
     
    

     

      

     
     

      

       				EnQueue（Q，w）；		 
       //顶点w入队列 
      
     
    

     

      

     
     

      

       			}
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      

       }
      
     
    

     

      

     
     

      
 
      
     
   
  

   
  

深度优先搜索

Q：什么是深度优先搜索

A：深度优先搜索类似于树的先序遍历。如其名称中所暗含的意思一样，这种搜索算法所遵循的搜索策略是尽可能“深”地搜索一个图。它的基本思想如下:首先访问图中某一起始顶点 v，然后由 v 出发，访问与 v 邻接且未被访问的任一顶点  w1​，再访问与 w1 ​邻接且未被访问的任一顶点…重复上述过程。当不能再继续向下访问时，依次退回到最近被访问的顶点，若它还有邻接顶点未被访问过，则从该点开始继续上述搜索过程，直至图中所有顶点均被访问过为止。

我们对这张图进行深度优先搜索。其深度优先遍历的结果为：abdehcfg

---

 代码演示

---

   

    

     

      

     
     

      

       bool visited[MAX_VERTEX_NUM];	
       //访问标记数组
      
     
    

     

      

     
     

      

       //从顶点出发，深度优先遍历图G
      
     
    

     

      

     
     

      

       void DFS(Graph G, int v){
      
     
    

     

      

     
     

      
	
       int w;
      
     
    

     

      

     
     

      
	
       visit(v);	
       //访问顶点
      
     
    

     

      

     
     

      

       	visited[v] = TRUE;	
       //设已访问标记
      
     
    

     

      

     
     

      
	
       //FirstNeighbor(G,v):求图G中顶点v的第一个邻接点，若有则返回顶点号，否则返回-1。
      
     
    

     

      

     
     

      
	
       //NextNeighbor(G,v,w):假设图G中顶点w是顶点v的一个邻接点，返回除w外顶点v
      
     
    

     

      

     
     

      
	
       for(w = 
       FirstNeighbor(G, v); w>=
       0; w=
       NextNeighor(G, v, w)){
      
     
    

     

      

     
     

      
		
       if(!visited[w]){	
       //w为u的尚未访问的邻接顶点
      
     
    

     

      

     
     

      
			
       DFS(G, w);
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      

       }
      
     
    

     

      

     
     

      

       //对图进行深度优先遍历
      
     
    

     

      

     
     

      

       void DFSTraverse(MGraph G){
      
     
    

     

      

     
     

      
	
       int v; 
      
     
    

     

      

     
     

      
	
       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);
      
     
    

     

      

     
     

      

       		}
      
     
    

     

      

     
     

      

       	}
      
     
    

     

      

     
     

      

       }