本文主要是介绍【数据结构与算法】广度优先搜索(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 w1,w2,w3...wn。
- 再从被访问过的 w 1 , w 2 , w 3 . . , w n w_1,w_2,w_3..,w_n w1,w2,w3..,wn出发,执行步骤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 w1,w2,w3...wn。
- 再从被访问过的 w 1 , w 2 , w 3 . . , w n w_1,w_2,w_3..,w_n w1,w2,w3..,wn出发,执行步骤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);}}}
}
全篇至此结束,感谢阅读!
这篇关于【数据结构与算法】广度优先搜索(BFS)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!