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