跳到主要内容

BFS

定义​

BFS（Breadth First Search，广度优先搜索）是一种图的遍历算法，从起始顶点出发，逐层访问所有邻接顶点，先访问距离近的顶点。

算法思想​

  1. 访问起始顶点，标记为已访问，入队
  2. 队首顶点出队，访问其所有未访问的邻接顶点，标记并入队
  3. 重复步骤 2，直到队列为空

实现​

通常使用队列实现。

时间复杂度​

  • 邻接矩阵：O(V2)O(V^2)
  • 邻接表：O(V+E)O(V + E)

应用​

  • 最短路径（无权图）
  • 连通分量检测
  • 层次遍历
  • 最小生成树（Prim 算法的辅助）