基于邻接矩阵存储的图的广度优先搜索遍历算法的实现（附C++实现代码）

清疚 2023-07-01 08:50 9阅读 0赞

#### 广度优先搜索算法（BFS） ####

**概念：** **广度优先搜素算法（BFS）** 的实现类似树的层次遍历，我们在实现他的时候一般借助一个队列来进行实现，利用**队列的先进先出的特点来对图进行广度优先搜索算法的实现。**

**具体实现思路：**  
1、 同样，先创建一个**visited\_BFS**标记数组来**判断顶点是否已经访问过**了，并且**初始化**visited\_BFS数组为false，表示图的所有顶点还没有访问。  
2、 **借助队列来实现广度优先遍历算法，队列的实现**  
3、 首先打印起点，然后将 **起点v**加入到队列中  
4、 然后起点v在邻接矩阵的所在行，读取整一行，**判断与起点相连的其他顶点是否已经访问完毕了，如果还没有访问（即visited为false）并且和起点的权值不为无穷大**，那么就将这个顶点加入到队列中，然后打印**并且标记**为已经访问  
5、 然后读取完这一整行之后，队列进行**出队**操作，**取队头元素作为新的“起点”**，**依次类推**，进行迭代，**停止的条件**是当队列为空时，**即结束**迭代。

**具体的细节代码已经详细解释！**

**具体实现代码如下：**

void BFS(MyGraph mygraph, char v) {//广度优先搜索算法
    
    	LinkQueue* linkQueue = new LinkQueue();//定义一个队列linkQueue
    	linkQueue->initQueue();//队列进行初始化
    	linkQueue->push(locateVex(mygraph,v));//将起点v压入队列中
    
    	while (linkQueue->isEmpty() != true) {//队列不为空的时候
    	
    		int temp_index = linkQueue->top();//取队头元素，作为起点
    		
    		if (visited_BFS[temp_index] != true) {
    			cout << mygraph.vexs[temp_index] << " ";
    		}
    		visited_BFS[temp_index] = true;//并且标记为已经访问
    
    		for (int i = 0; i < mygraph.curVexNum; i++) {//寻找visited为false并且和起点v的距离不为默认值的点，加入到队列中
    		
    			if (mygraph.arcs[temp_index][i] != de_num && visited_BFS[i] != true) {
    				linkQueue->push(i);//加入到队列中
    			}
    		}
    		linkQueue->pop();//将队头元素出队
    	}
    	delete[] linkQueue;//算法结束，将队列删除
    }

**如有错误，欢迎指正。谢谢**