Menu
CoddyTech

它是如何工作的?

Coddy 广度优先搜索:图算法 课程的第 3 课,共 9 课。

BFS 会为每个顶点保留一个 已访问标记,并维护一个用于处理顶点的队列。

分步流程:

  1. 将起点标记为已访问,并将其加入队列。
  2. 从队列首部取出一个顶点,并将其记录在访问顺序中。
  3. 对每个尚未访问的邻居(按升序排列),将其标记为已访问并加入队列。在入队时进行标记,可以避免同一个顶点被添加两次。
  4. 重复上述步骤,直到队列为空。

示例:顶点为 0..3,边为 [0,1, 0,2, 1,3, 2,3],从 0 开始:

  • 访问 0,将 1 和 2 加入队列;访问 1,将 3 加入队列;访问 2;访问 3。
  • 访问顺序:[0, 1, 2, 3](与 DFS 对比:[0, 1, 3, 2])。

亲手试试

这节课没有代码挑战。

quiz icon自我测试

这节课包含一个小测验。开始学习即可作答,并记录你的进度。

广度优先搜索:图算法中的所有课

自己练习: C 在线编译器