在 ）文章介绍了深度优先搜索算法的理论和实践。本文将介绍与其原理类似的广度优先搜索算法。
广度优先搜索（也称宽度优先搜索，缩写 BFS，以下采用广度来描述）是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra 单源最短路径算法和 Prim 最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫 BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。基本过程，BFS 是从根节点开始，沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问，则算法中止。一般用队列数据结构来辅助实现 BFS 算法。
对于下面的树而言，BFS 方法首先从根节点1开始，其搜索节点顺序是 1,2,3,4,5,6,7,8。
BFS 使用队列 (queue) 来实施算法过程，队列 (queue) 有着先进先出 FIFO (First Input First Output)的特性，
BFS 操作步骤如下：
- 把起始点放入 queue；
- 重复下述2步骤，直到 queue 为空为止：
-
- 从queue中取出队列头的点；
（2）从queue中取出队列头的节点1，找出与节点1邻接的节点2,3，标记为已遍历，然后放入queue中。
（3）从queue中取出队列头的节点2，找出与节点2邻接的节点1,4,5，由于节点1已遍历，排除；标记4,5为已遍历，然后放入queue中。
（4）从queue中取出队列头的节点3，找出与节点3邻接的节点1,6,7，由于节点1已遍历，排除；标记6,7为已遍历，然后放入queue中。
（5）从queue中取出队列头的节点4，找出与节点4邻接的节点2,8，2属于已遍历点，排除；因此标记节点8为已遍历，然后放入queue中。
（6）从queue中取出队列头的节点5，找出与节点5邻接的节点2,8，2,8均属于已遍历点，不作下一步操作。
（7）从queue中取出队列头的节点6，找出与节点6邻接的节点3,8,9，3,8属于已遍历点，排除；因此标记节点9为已遍历，然后放入queue中。
（8）从queue中取出队列头的节点7，找出与节点7邻接的节点3, 9，3,9属于已遍历点，不作下一步操作。
（9）从queue中取出队列头的节点8，找出与节点8邻接的节点4,5,6，4,5,6属于已遍历点，不作下一步操作。
（10）从queue中取出队列头的节点9，找出与节点9邻接的节点6,7，6,7属于已遍历点，不作下一步操作。
（11）queue 为空，则遍历结束
上面过程可以用下面的代码来表示：
其通用框架可以概括为：
下面来总结下写出 BFS 算法规则：
通过这个 bfs 框架可以看出该方法主要有以下几个规律：
- 起点条件。从哪个点开始访问？是否每个点都需要当作起点？第一次 bfs 调用至关重要。
- 邻接点。如何去获取邻接点？通过起点可到达的点。如何保存邻接点？先进先出。一般采用队列。
- 循环参数。队列不为空。一个点的所有邻接点都是在一个 while 里面进行添加的，才会进入
- 访问标志。为了避免重复访问，需要对已经访问过的节点加上标记，避免重复访问。
讲完了理论，下面开始进入实战。
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
示例 2:
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
题目解答如下：
给定一个包含了一些 0 和 1 的非空二维数组 grid 。
一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)
示例 1:
对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。
示例 2:
对于上面这个给定的矩阵, 返回 0。
注意: 给定的矩阵grid 的长度和宽度都不超过 50。
这道题目和上面的很类似。题目解答如下：
广度优先遍历（BFS ）（转）
到此这篇广度优先搜索是什么过程（广度优先搜索的原理）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/bcyy/28546.html