广度优先搜索

图算法

广度优先搜索是一种图遍历算法,它从图的某一顶点开始遍历,先访问这个顶点的所有邻接点,然后再按照同样的方法访问这些邻接点的邻接点,依此类推。

时间复杂度:最佳 O(V + E) | 平均 O(V + E) | 最差 O(V + E)
空间复杂度:O(V)
图类型:无向图

应用场景/前提条件

  • 适用于查找最短路径
  • 适用于层级遍历

算法讲解

广度优先搜索(BFS)算法 - 图遍历教程

介绍

广度优先搜索(Breadth-First Search, BFS)是一种图遍历算法,它从图的某一顶点开始,先访问该顶点的所有相邻顶点,然后再按照同样的方式访问这些相邻顶点的相邻顶点,层层推进,直到访问完图中所有可达顶点。BFS的特点是"先进先出",即优先访问距离起始顶点最近的顶点。

算法步骤

  1. 选择图中的一个起始顶点,将其标记为已访问,并放入队列中
  2. 从队列中取出队首顶点,访问该顶点
  3. 将该顶点的所有未访问过的相邻顶点标记为已访问,并放入队列中
  4. 重复步骤2和3,直到队列为空

算法详解

比如有一个包含8个顶点(0-7)的无向图,边的关系如下:

  • 0与1、2相邻
  • 1与0、3、4相邻
  • 2与0、5、6相邻
  • 3与1、7相邻
  • 4与1相邻
  • 5与2相邻
  • 6与2相邻

...