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

2021年6月26日 1点热度 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;//算法结束,将队列删除
}

如有错误,欢迎指正。谢谢

    原文作者:一座城。
    原文地址: https://blog.csdn.net/One_castle/article/details/104053961
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。