6.3.1 广度优先搜索

教材导航 · 第6章

原书定位

印刷页P219起,对应PDF第231页。下文为目视整理的知识提要;完整内容见原书对照。

BFS 按距离起点的边数逐层扩展,用队列保存已发现但尚未展开的顶点。顶点发现并入队时立即标记,保证每个顶点最多入队一次。

标记起点并入队
while 队列非空:
    v = 出队
    for v 的每个出邻接点 w:
        if w 未访问:
            标记 w,记录父结点 v,再将 w 入队

树的层序遍历是 BFS 的特殊情形。DFS 使用栈或递归,不能把两者的辅助结构混淆。

广度优先搜索示例图

广度优先搜索示例图,原书P220。

下级知识点

对应练习

6.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P219,PDF第231页

原书对照,原书P220,PDF第232页

原书对照,原书P221,PDF第233页