Loading... 广度优先搜索(BFS, Breadth-First Search)也是搜索的手段之一。它与深度优先搜索相似，都是从一个状态出发探索所有可以达到的状态。 BFS 和 DFS不同的地方在于搜索的顺序。DFS是不撞南墙不回头，而BFS就像渗透一样从一个点渗透整个面。 ##1.算法思想 广度优先搜索思想：从图中某顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问，直至图中所有已被访问的顶点的邻接点都被访问到。如果此时图中尚有顶点未被访问，则需要另选一个未曾被访问过的顶点作为新的起始点，重复上述过程，直至图中所有顶点都被访问到为止。 ##2.算法特点 广度优先搜索类似于树的层次遍历，是按照一种由近及远的方式访问图的顶点。在进行广度优先搜索时需要使用队列存储顶点信息。 ##3.算法过程 ###3.1 无向图的广度优先搜索 以下列无向图为例，采用广度优先搜索过程。  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 有向图的广度优先搜索 以下面的有向图为例  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 日 © 允许规范转载 赞 如果觉得我的文章对你有用，请随意赞赏