Loading... 广度优先搜索(BFS, Breadth-First Search)也是搜索的手段之一。它与深度优先搜索相似,都是从一个状态出发探索所有可以达到的状态。 BFS 和 DFS不同的地方在于搜索的顺序。DFS是不撞南墙不回头,而BFS就像渗透一样从一个点渗透整个面。 ##1.算法思想 广度优先搜索思想:从图中某顶点v出发,在访问了v之后依次访问v的各个未曾访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问,直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问,则需要另选一个未曾被访问过的顶点作为新的起始点,重复上述过程,直至图中所有顶点都被访问到为止。 ##2.算法特点 广度优先搜索类似于树的层次遍历,是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。 ##3.算法过程 ###3.1 无向图的广度优先搜索 以下列无向图为例,采用广度优先搜索过程。 ![BFS_1.jpg](https://blog.domineto.top/usr/uploads/2019/04/2274569170.jpg) 1. 选取A为起始点,输出A,A入队列,标记A,当前位置指向A。 2. 队列头为A,A出队列。A的邻接顶点有B、E,输出B和E,将B和E入队,并标记B、E。当前位置指向A。 3. 队列头为B,B出队列。B的邻接顶点有C、D,输出C、D,将C、D入队列,并标记C、D。当前位置指向B。 4. 队列头为E,E出队列。E的邻接顶点有D、F,但是D已经被标记,因此输出F,将F入队列,并标记F。当前位置指向E。 5. 队列头为C,C出队列。C的邻接顶点有B、D,但B、D均被标记。无元素入队列。当前位置指向C。 6. 队列头为D,D出队列。D的邻接顶点有B、C、E,但是B、C、E均被标记,无元素入队列。当前位置指向D。 7. 队列头为F,F出队列。F的邻接顶点有G、H,输出G、H,将G、H入队列,并标记G、H。当前位置指向F。 8. 队列头为G,G出队列。G的邻接顶点有F,但F已被标记,无元素入队列。当前位置指向G。 9. 队列头为H,H出队列。H的邻接顶点有F,但F已被标记,无元素入队列。当前位置指向H。 10. 队列空,则以A为起始点的遍历结束。若图中仍有未被访问的顶点,则选取未访问的顶点为起始点,继续执行此过程。直至所有顶点均被访问。 ###3.2 有向图的广度优先搜索 以下面的有向图为例 ![BFS_2.jpg](https://blog.domineto.top/usr/uploads/2019/04/1081417763.jpg) 1. 选取A为起始点,输出A,将A入队列,标记A。 2. 队列头为A,A出队列。以A为尾的边有两条,对应的头分别为B、C,则A的邻接顶点有B、C。输出B、C,将B、C入队列,并标记B、C。 3. 队列头为B,B出队列。B的邻接顶点为C,C已经被标记,因此无新元素入队列。 4. 队列头为C,C出队列。C的邻接顶点有E、F。输出E、F,将E、F入队列,并标记E、F。 5. 队列头为E,E出队列。E的邻接顶点有G、H。输出G、H,将G、H入队列,并标记G、H。 6. 队列头为F,F出队列。F无邻接顶点。 7. 队列头为G,G出队列。G无邻接顶点。 8. 队列头为H,H出队列。H邻接顶点为E,但是E已被标记,无新元素入队列。 9. 队列为空,以A为起始点的遍历过程结束,此时图中仍有D未被访问,则以D为起始点继续遍历。选取D为起始点,输出D,将D入队列,标记D。 10. 队列头为D,D出队列,D的邻接顶点为B,B已被标记,无新元素入队列。 11. 队列为空,且所有元素均被访问,广度优先搜索遍历过程结束。广度优先搜索的输出序列为:A->B->E->C->D->F->G->H。 ##4.算法分析 假设图有V个顶点,E条边,广度优先搜索算法需要搜索V个节点,时间消耗是O(V),在搜索过程中,又需要根据边来增加队列的长度,于是这里需要消耗O(E),总得来说,效率大约是O(V+E)。 ##5.经典例题 <button class=" btn m-b-xs btn-primary btn-addon" onclick="window.open('https://www.luogu.org/problemnew/show/P1162','_blank')"><i class="glyphicon glyphicon-hand-right"></i>题目戳我!</button> AC代码(好久之前写的代码,写的不好请轻喷) ```cpp #include <iostream> #include <queue> #include <algorithm> using namespace std; typedef pair<int, int> P; int row[36][36];//存原始图 bool check[36][36];//存连通块 inline int Input() {//输入 int n; cin >> n; for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> row[i][j]; return n; } inline void BFS(int n) {//广搜,n 为起始点 queue<P> q; for (int i = 0; i < n; i++) {//检测周围一圈是否有0,有的话就加入队列 if (!row[0][i]) { check[0][i] = true; q.push(P(0, i)); } if (!row[n - 1][i]) { check[n - 1][i] = true; q.push(P(n - 1, i)); } if (!row[i][0]) { check[i][0] = true; q.push(P(i, 0)); } if (!row[i][n - 1]) { check[i][n - 1] = true; q.push(P(i, n - 1)); } } while (!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); check[x][y] = true;//将起点标记 for (int i = -1; i <= 1; i++) { int mx = x + i, my = y + i; /*检测起点四周是否有符合条件的点,有就加入队列*/ if (mx >= 0 && mx < n && !check[mx][y] && !row[mx][y]) q.push(P(mx, y)); if (my >= 0 && my < n && !check[x][my] && !row[x][my]) q.push(P(x, my)); } } return; } inline void print(int n) {//输出 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (check[i][j] || row[i][j] == 1) cout << row[i][j]; else cout << "2"; if (j != n - 1) cout << " "; } cout << endl; } return; } int main() { int n = Input(); BFS(n); print(n); //system("pause"); return 0; } ``` 参考文章: 《算法竞赛入门经典》 小小吴师兄的文章 最后修改:2019 年 04 月 06 日 © 允许规范转载 赞 如果觉得我的文章对你有用,请随意赞赏