图的BFS算法

末蓝、 2023-02-20 13:39 19阅读 0赞

# BFS：Breadth-First-Search #

## 介绍 ##

BFS:广度优先搜索

*  类似于树的按层次遍历过程

## 思想 ##

1.  访问起始点v
2.  之后，依次访问v的各个未曾访问过的邻接点
3.  再分别从这些邻接点出发，访问他们的邻接点；并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”。
4.  直至图中所有顶点都被访问过为止

例如：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz_size_16_color_FFFFFF_t_70]  
遍历顺序：A-B-C-D-E-F-G-H-I

## 伪码 ##

bool visited[MAX_VERTEX_NUM];   		//访问标记数组
    void BFSTraverse (Graph G) {
    //对图G进行广度优先遍历，设访问函数为visit()
       for(i=0; i<G.vexnum, ++i)
       	visited[ i]=FALSE;					//访问标记数组初始化
       InitQueue (Q) ;							//初始化辅助队列Q
       for(i=0; i<G.vexnum; ++i )			//从0号顶点开始遍历
       	if(!visited[il)
           	BFS(G, i);					//对每个连通分量调用一次BFS
    }
    
    void BFS(Graph G,int v) {
    // 从顶点v出发， 广度优先遍历图G,算法借助一个辅助队列Q
       visit(v);							//访问初始项点v
       visited[v]=TRUE;					//对v做已访问标记
       Enqueue(Q,v);						//顶点v 入队列
       while(!isEmpty(Q)) {
       	DeQueue(Q,v);					//顶点v 出队列
       	for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w))
       						//检测v所有邻接点
       		if(!visited[w]){ 			//w为v的尚未访问的邻接顶点
       			visit(w);				//访问项点w
       			visited[w]=TRUE;		//对W做已访问标记
       			EnQueue(Q,w); 			//顶点w入队列
       		}//if
       }//while
    }

## 所用场景 ##

### 最短路径 ###

说明：

因为BFS逐层访问特点，也就是从起点由近向远访问节点，所以BFS可以用于寻找最短路径。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200627151737818.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTU5MzAz,size_16,color_FFFFFF,t_70