BFS-广度优先遍历

[yihan12]

广度优先遍历是一种图的遍历算法，它从图的起始顶点开始，先访问起始顶点的所有邻接顶点，然后再依次访问这些邻接顶点的邻接顶点，以此类推，直到遍历完所有顶点。

广度优先遍历通常使用队列来实现，具体步骤如下：

• 将起始顶点入队；
• 当队列不为空时，取出队列头部的顶点，并将其所有未访问的邻接顶点入队；
• 标记当前顶点为已访问；
• 重复步骤2和步骤3，直到队列为空。

广度优先遍历的特点是能够按层次遍历图的顶点，从而找到起始顶点到其他顶点的最短路径。它适合应用于寻找最短路径、拓扑排序等问题。