《数据结构与算法》——图的遍历之广度优先搜索（BFS）总结

向右看齐 2024-04-18 16:27 46阅读 0赞

# 《数据结构与算法》——图的遍历之广度优先搜索（BFS）总结 #

由于今天做题遇到了个麻烦问题，所以就先把**广搜**和**深搜**复习一下，也算是换个脑子吧，毕竟“一杯茶，一包烟，一道积分算一天”的生活太单调了（我不抽烟，只是为了押韵）。

定义

图的存储结构及方法

伪代码实现

性能分析及应用

性能分析

应用

参考文献

--------------------

## 定义 ##

什么是广度优先搜索？我们前面在树的部分已经复习过树的遍历算法，其中有一种遍历算法被称为“**层次遍历**”，其大体操作就是对于一个具有n个子树的根节点a来讲，访问根节点a后依次访问n个子树的根结点，即先访问a，然后依次访问a的直接子结点，直至将整棵树全部遍历结束。

而广度优先搜索的操作与层次遍历很类似，其基本思想是：从图的一个顶点W出发，首先先访问其邻接结点v1、v2、v3…，随后再将v1、v2、v3…等结点看做顶点w，依次访问未被访问过的邻接顶点，直至将所有的顶点全部遍历结束。

## 图的存储结构及方法 ##

关于图的存储结构这一块已经在[上一篇博客][Link 1]中进行了总结，这里便不再进行赘述。

而这个宽度遍历算法可以根据树的[层次遍历][Link 2]作为先验知识进行辅助理解。

## 伪代码实现 ##

/*****************************
    Description: 图的宽度优先搜索/广度优先搜索
    ******************************/
    #define MAX_VERTEX_NUM 100 
    bool visited[MAX_VERTEX_NUM];//访问标记数组
    void BFSTraverse(Graph G){
    	//对图进行广度优先遍历，设访问函数为visit()
    	for(int i = 0;i<G.vexnum;i++)//对标记数组进行初始化 
    		visited[i]=0; 
    	InitQueu(Q);//辅助队列Q初始化
    	for(int i = 0;i<G.vexnum;i++)
    		if(!visited[i])
    			BFS(G,i);
    }
    
    void BFS(Graph G,int v){
    	visit(v);
    	visited[v]=1;
    	Enqueue(Q,v);
    	while(!isEmpty(Q)){//队列不空 
    		Dequeue(Q,v); //队头出队
    		for(w=FirstNeighbor(G,v);w!=-1;w=NextNeighbor(G,v,w))//访问v的子结点 
    			if(!visited[w]){
    				visit(w);
    				visited[w]=1;
    				Enqueue(Q,w);	
    			}//if 	
    	}//while	
    }//BFS

## 性能分析及应用 ##

### 性能分析 ###

空间复杂度：

需要借助一个队列Q，n个结点均需要入队一次，所以空间复杂度为o(|V|)。

时间复杂度：

对于邻接矩阵法，需要将整个矩阵遍历一次，所以时间复杂度为o(|V|^2);

对于邻接表来讲，需要将每个顶点和顶点下的边表结点访问一次，所以时间复杂度为o(|V|+|E|)。

### 应用 ###

1.可以用来求非带权图单源最短路径，这种方法是根据中间点的个数所求的。拓展：若求带权图单源最短路径可以使用[迪杰斯特拉算法][Link 3]（权值必须为正），各顶点间的最短路径可以使用[弗洛伊德算法][Link 4]（可带负权值）。因为后两种复杂情况均有实现，所以求非带权图单源最短路径的算法不进行实现了。

2.可以用来求广度优先生成树，**若存储方式是邻接矩阵则生成树唯一，若存储方式是邻接表则生成树不唯一。**

## 参考文献 ##

严蔚敏，吴伟民. 数据结构（C语言版）\[M\]. 北京： 清华大学出版社，2013.

王道论坛 2019年数据结构考研复习指导\[M\]. 北京： 电子工业出版社，2018.

**如有错误，还请朋友不吝指正。**

[Link 1]: https://blog.csdn.net/Kwzc4/article/details/100655291
[Link 2]: https://blog.csdn.net/Kwzc4/article/details/99234258
[Link 3]: https://blog.csdn.net/Kwzc4/article/details/96161586
[Link 4]: https://blog.csdn.net/Kwzc4/article/details/96432488