数据结构——图——广度优先遍历

秒速五厘米 2023-01-11 08:43 111阅读 0赞

## 数据结构——图——广度优先遍历 ##

广度优先遍历(Breadth\_First\_Search)，又称为广度优先搜索，简称 BFS。还是以找钥匙的例子为例。小孩子不太可能把钥匙丢到大衣柜顶上或厨房的油烟机里去，深度优先遍历意味着要彻底查找完一个房间才查找下一个房间，这未必是最佳方案。所以不妨先把家里的所有房间简单看一遍，看看钥匙是不是就放在很显眼的位置，如果全走一遍没有，再把小孩在每个房间玩得最多的地方或各个家俱的下面找一找，如果还是没有，那看一下每个房间的抽屉，这样一步步扩大查找的范围，直到找到为止。事实上，我在全屋查找的第二遍时就在抽水马桶后面的地板上找到了。

如果说图的深度优先遍历类似树的前序遍历，那么图的广度优先遍历就类似于树的层序遍历了。我们将图7-5-3的第一幅图稍微变形，变形原则是顶点A放置在最上第一层，让与它有边的顶点B、F为第二层，再让与B和F有边的顶点C、I、G、E为第三层，再将这四个顶点有边的D、H放在第四层，如图7-5-3的第二幅图所示。此时在视觉上感觉图的形状发生了变化，其实顶点和边的关系还是完全相同的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]  
有了这个讲解，我们来看代码就非常容易了。以下是邻接矩阵结构的广度优先遍历算法。

/*邻接矩阵的结构*/
    typedef char VertexType;  /*顶点类型应由用户定义*/
    
    typedef int EdgeType; /*边上的权值类型应由用户定义*/
    
    #define MAXVEX 100   /*最大顶点数，应由用户定义*/
    
    #define INFINITY 65535  /*用65535来代表*/
    
    typedef struct
    {
        
    	VertexType vexs[MAXVEX];   /*顶点表*/
    	EdgeType arc[MAXVEX][MAXVEX];  /*领边矩阵，可看作边表*/
    
    	int numVertexes, numEdges;    /*图中当前的顶点数和边数*/
    } MGraph;
    
    #define TRUE 1
    #define FALSE 0
    typedef int Boolean; /*Boolean 是布尔类型， 其值是TRUE 或 FALSE*/
    
    Boolean visited[MAXVEX]; /*访问标志的数组*/
    
    /*邻接矩阵的广度遍历算法*/
    void BFSTraverse(MGraph G)
    {
        
    	int i,j;
    	Queue  Q;
    	for (i=0;i<G.numVertexes;i++)
    	{
        
    		visited[i] = FALSE;
    	}
    
    	InitQueue(&Q);   /*初始化一辅助用的队列*/
    
    	for (i=0;i<G.numVertexes;i++) /*对每一个顶点做循环*/
    	{
        
    		if (!visited[i])   /*若是未访问过就处理*/
    		{
        
    			visited[i] = TRUE;      /*设置当前顶点访问过*/
    			printf("%c", G.vexs[i]);/*打印顶点，也可以其他操作*/
    			EnQueue(&Q,i);          /*将顶点入队列*/
    			while (!QueueEmpty(Q))  /*若当前队列不为空*/
    			{
        
    				DeQueue(&Q,&i);    /*将队中元素出队列，赋值给i*/
    				for (j=0;j<G.numVertexes;j++)
    				{
        
    					/*判断其他顶点若与当前顶点存在边且未访问过*/
    					if (G.arc[i][j]==1&&!visited[j])
    					{
        
    						visited[j] = TRUE; /*将找到的此顶点标记为已访问*/
    						printf("%c",G.vexs[j]);/*打印顶点*/
    						EnQueue(&Q,j);/*将找到的此顶点入队列*/
    					}
    				}
    			}
    		}
    	}
    }

对于邻接表的广度优先遍历，代码与邻接矩阵差异不大，代码如下。

/*邻接表结构*/
    #define MAXVEX 100   /*最大顶点数，应由用户定义*/
    typedef char VertexType;  /*顶点类型应由用户定义*/
    
    typedef int EdgeType;  /*边上的权值类型应由用户定义*/
    
    typedef struct EdgeNode  /*边表结点*/
    {
        
    	int adjvex;  /*邻接点域，存储该顶点对应的下标*/
    	EdgeType weight; /*用于存储权值，对于非网图可以不需要*/
    	struct EdgeNode* next;  /*链域，指向下一个邻接点*/
    } EdgeNode;
    
    typedef struct vertexNode/*顶点表结点*/
    {
        
    	VertexType data;   /*顶点域，存储顶点信息*/
    	EdgeNode* firstedge;   /*边表头指针*/
    
    }vertexNode, AdjList[MAXVEX];
    
    typedef struct
    {
        
    	AdjList adjList;
    	int numvertexes, numEdges;/*图中当前顶点数和边数*/
    
    } GraphAdjList;
    
    #define TRUE 1
    #define FALSE 0
    typedef int Boolean; /*Boolean 是布尔类型， 其值是TRUE 或 FALSE*/
    
    Boolean visited[MAXVEX]; /*访问标志的数组*/
    
    /*邻接表的广度遍历算法*/
    void BFSTraverse(GraphAdjList* GL)
    {
        
    	int i;
    	EdgeNode* p;
    
    	Queue Q;
    
    	for (i = 0; i < GL->numvertexes; i++)
    	{
        
    		if (!visited[i])
    		{
        
    			visited[i] = TRUE;
    			printf("%c", GL->adjList[i].data);/*打印顶点，也可以其他操作*/
    
    			EnQueue(&Q, i);
    
    			while (!QueueEmpty(Q))
    			{
        
    				DeQueue(&Q, &i);
    
    				p->GL->adjList[i].firstedge;/*找到当前顶点边表链表头指针*/
    				while (p)
    				{
        
    					if (!visited[p->adjvex])   /*若此顶点未被访问*/
    					{
        
    						visited[p->adjvex] = TRUE;
    						printf("%c", GL->adjList[p->adjvex].data);
    						EnQueue(&Q, p->adjvex);/*将此顶点入队列*/
    					}
    					p = p->next;  /*指针指向下一个邻接点*/
    				}
    			}
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70]: /images/20221119/0fb76dc2558045248b6157714c66f953.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210126103116185.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk0NTQ3MQ==,size_16,color_FFFFFF,t_70