它是如何工作的?
Coddy 广度优先搜索:图算法 课程的第 3 课,共 9 课。
BFS 会为每个顶点保留一个 已访问标记,并维护一个用于处理顶点的队列。
分步流程:
- 将起点标记为已访问,并将其加入队列。
- 从队列首部取出一个顶点,并将其记录在访问顺序中。
- 对每个尚未访问的邻居(按升序排列),将其标记为已访问并加入队列。在入队时进行标记,可以避免同一个顶点被添加两次。
- 重复上述步骤,直到队列为空。
示例:顶点为 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])。
亲手试试
这节课没有代码挑战。
这节课包含一个小测验。开始学习即可作答,并记录你的进度。
广度优先搜索:图算法中的所有课
自己练习: C 在线编译器