广度优先搜索（Breadth-First Search，简称BFS）是一种用于遍历或搜索图数据结构的算法。它从图中的某个节点开始，按照从近到远的顺序逐层访问所有节点。具体来说，BFS使用一个先进先出（FIFO）队列来存储待访问的节点，每次从队列中取出一个节点并访问其所有未被访问过的相邻节点，然后将这些相邻节点加入队列中，直到队列为空。
BFS的基本思想是先访问起始节点，然后依次访问起始节点的所有相邻节点，再访问这些相邻节点的所有未被访问过的相邻节点，如此逐层进行，直到访问完所有节点。这种搜索策略确保了从起始节点到其他任何节点的路径都是最短路径，即边数最少的路径。
在实现中，BFS通常会记录每个节点的父节点信息，以便在需要时可以回溯找到从起始节点到目标节点的路径。
广度优先搜索不仅适用于无向图，也适用于有向图，并且可以用于解决多种图问题，如判断图是否连通、计算图的连通分量以及寻找最短路径等
声明：文章来源于网络，如有侵权请联系删除！