【数据结构与算法】广度优先搜索（BFS）

本文主要是介绍【数据结构与算法】广度优先搜索（BFS），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

广度优先搜索（BFS）
- 前言
- 基本思路
- 基本实现
BFS的应用
- 判断图的连通性
- 图的遍历
- 求单源最短路径

广度优先搜索（BFS）

前言

对于考研人来说，BFS和DFS指的是图的两种遍历算法。

但是严格意义上说，BFS和DFS是两种搜索策略。

BFS代表算法在执行时，会像树的层次遍历那样，从属于同一个结点的后继的访问顺序相邻。
DFS代表算法在执行时，会像树的先序遍历那样，沿着某条路径走到终点，再返回走另外一条路径。

基本思路

广度优先搜索的实现思路大致如下：

访问起始节点 v。
从v出发，访问其未被访问的邻接结点 $w_1,w_2,w_3...w_n$ 。
再从被访问过的 $w_1,w_2,w_3..,w_n$ 出发，执行步骤2。
重复步骤2、3，直至与v连通的所有的结点都被访问。

例如，现在有一个有向图：

那么按照BFS的思路：

假设从1开始搜索，那么先访问 1。

再执行步骤2，访问 2、4。

执行步骤3：对2，可访问3。对4，3已被2访问过了，跳过。

再对3，1、2都已被访问过了，跳过。

此时得到的搜索序列为：1 2 4 3。

基本实现

这里基于邻接矩阵实现，如果有感兴趣的同学，可以实现一下基于邻接表的BFS算法。

// C++#include <queue>const int MAX_SIZE = 100;   // 最大容量struct Graph{int vex[MAX_SIZE];   // 顶点集int edge[MAX_SIZE][MAX_SIZE]; // 边集int v_num;  // 当前顶点个数
};bool visited[MAX_SIZE]; // 访问标记/*** 访问结点*/
void visit(int i){// 标记已被访问visited[i] = true;// ... 访问动作
}/*** BFS算法* * 按照广度优先搜索策略访问与起始结点 i 连通的所有结点。* * @param {Graph} G 图* @param {int} i 起始顶点*/
void BFS(Graph G, int i){// 初始化for(int j = 0; j< G.v_num; j++){visited[j] = false;}// 访问起始节点visit(i);// 这里借助队列来实现同一个结点后继的访问相邻。std::queue<int> q;q.push(i);while(!q.empty()){int cur = q.front();q.pop();for(int j=0; j< G.v_num; j++){// 如果边存在，且未被访问，则访问并加入队列q。if(!visited[j] && G.edge[cur][j] == 1) {visit(j);q.push(j);}}}
}

BFS的应用

判断图的连通性

对于无向图来说，若图是连通的，那么从任意一个结点出发，执行一遍BFS搜索即可访问到图中的所有结点。

对于有向图来说，若图是强连通的，那么和无向图一样，从任意一个结点出发，执行一遍BFS也能够访问到图中的所有结点。

因此BFS可以用来判断图的连通性，从任意一个结点出发执行一遍BFS，统计访问到的结点个数，与图中所有结点的个数进行比较，即可实现判断。

图的遍历

由于并不是所有的图都是连通图，因此，在BFS的基础上，我们还需要保证图中的每一个结点都被访问到。

因此，我们还需要添加一个操作，来实现遍历图中的每一个结点：

图的广度优先遍历的思路如下：

访问起始节点 v。
从v出发，访问其未被访问的邻接结点 $w_1,w_2,w_3...w_n$ 。
再从被访问过的 $w_1,w_2,w_3..,w_n$ 出发，执行步骤2。
重复步骤2、3，直至与v的连通的所有的结点都被访问。
从剩余未被访问的结点中任选一个结点，执行操作1到4，直至所有结点都被访问。

/*** @param {Graph} G 需要遍历的图*/
void BFSTraverse(Graph G){// 初始化for(int j = 0; j< G.v_num; j++){visited[j] = false;}// 操作5for(int i = 0;i<G.v_num; i++){if(!visited[i]) BFS(G, i);}
}/*** BFS算法* * 按照广度优先搜索策略访问与起始结点 i 连通的所有结点。* * @param {Graph} G 图* @param {int} i 起始顶点*/
void BFS(Graph G, int i){// 初始化// for(int j = 0; j< G.v_num; j++){//     visited[j] = false;// }// 访问起始节点visit(i);// 这里借助队列来实现同一个结点后继的访问相邻。std::queue<int> q;q.push(i);while(!q.empty()){int cur = q.front();q.pop();for(int j=0; j< G.v_num; j++){// 如果边存在，且未被访问，则访问并加入队列q。if(!visited[j] && G.edge[cur][j] == 1) {visit(j);q.push(j);}}}
}

求单源最短路径

在前言中我们提到，BFS代表算法在执行时，会像树的层次遍历那样，从属于同一个结点的后继的访问顺序相邻。

这一特性就使得在首次访问到终点时，从起点到达终点的路径必然是最短的。

例如：

从 1 -> 4的路径有

1 -> 2 -> 4
1 -> 2 -> 3 ->4
1 -> 3 -> 4
1 -> 3 -> 5 -> 7 -> 4
1 -> 3 -> 5 -> 6 -> 7 -> 4

按照BFS的遍历顺序，那么在对2执行操作2时，就会第一次遇到4号结点，它们之间的路径是2。

代码实现

int dis[MAX_SIZE];/*** BFS计算从u结点出发到图中任意结点的最短路径* * @param {Graph} G* @param {int} u*/
void get_min_distance(Graph G, int u)
{// 初始化for (int i = 0; i < G.v_num; i++){dis[i] = -1;visited[i] = false;}visited[u] = true;dis[u] = 0;std::queue<int> q;q.push(u);while (!q.empty()){int cur = q.front();q.pop();for (int j = 0; j < G.v_num; j++){if (!visited[j] && G.edge[cur][j] == 1){visited[j] = true;dis[j] = dis[cur] + 1;q.push(j);}}}
}