摘要：
1，广度优先搜索介绍
2，广度优先搜索的解题步骤
3，广度优先搜索的代码实现
1，广度优先搜索介绍
广度优先搜索(Breadth-first search，BFS)，又称宽度优先搜索，简单的说，它是从一个点开始，始终访问离他最近的点，直到所有点都被访问，则算法终止。
BFS属于一种盲目搜寻算法，它不会考虑结果的可能位置，而是彻底搜索整个数据结构，直到找到结果为止。
BFS 一般用于树，矩阵和图的遍历，对于树来说就是从根节点开始，从上到下一层一层的遍历。对于矩阵来说就是从某一个点开始沿着它的上下左右四个方向遍历(如果题要求可以访问斜对角，就需要沿着该点的 8 个方向遍历)。前两个我们不做介绍，这里我们主要讲下图的BFS。
因为每次都是搜索离起始点最近的点，我们可以把搜索过的点添加到队列中，当队列中的点出队的时候，我们继续搜索和它相邻的点。
这里要注意，一个点不能重复搜索，否则会形成死循环，所以当一个点被访问完之后还需把它标记一下。
2，BFS的解题步骤
1，创建一个队列，把搜索的起始点添加到队列中，接着在创建一个数组visited，记录被访问过的顶点。
2，队列元素出队，访问与出队元素相连的所有没被访问过的顶点，把他们都加入到队列中。
3，重复步骤 2 ，直到队列为空则算法停止。
如下图所示，假如从顶点 0 开始搜索，搜索步骤如下：
所以我们发现BFS搜索的首先是离他最近的顶点，如下图所示，先搜索通过一条边和它相连的点，在搜索通过两条边和它相连的点……，由近及远。
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/rgzn-sdxx/25086.html