6.3.1 广度优先搜索
原书定位
印刷页P219起,对应PDF第231页。下文为目视整理的知识提要;完整内容见原书对照。
BFS 按距离起点的边数逐层扩展,用队列保存已发现但尚未展开的顶点。顶点发现并入队时立即标记,保证每个顶点最多入队一次。
标记起点并入队
while 队列非空:
v = 出队
for v 的每个出邻接点 w:
if w 未访问:
标记 w,记录父结点 v,再将 w 入队
树的层序遍历是 BFS 的特殊情形。DFS 使用栈或递归,不能把两者的辅助结构混淆。

广度优先搜索示例图,原书P220。
下级知识点
对应练习
关联知识
- 3.2 队列
- 3.3.4 队列在层次遍历中的应用
- 5.3.1.4 层次遍历
- 6.2.1 邻接矩阵法
- 6.2.2 邻接表法
- 6.3 图的遍历
- 6.3.1.1 BFS 求无权图最短路径
- 6.3.1.2 广度优先生成树
- 6.3.2 深度优先搜索
- 6.3.3 图的遍历与图的连通性
原书对照
展开原书对照截图


