6.3.1.2 广度优先生成树

教材导航 · 第6章

原书定位

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

将每个顶点首次发现时使用的边保留下来,得到 BFS 搜索树;无向非连通图得到生成森林。同一起点的 BFS 树给出各顶点的最少边数路径,树高等于从该根出发的最大有限距离。

同图可以有不同 BFS 树;确定起点和邻接扫描次序后算法输出才确定。矩阵存储本身不意味着所有可能的 BFS 树唯一。

广度优先生成树

广度优先生成树,原书P221。

对应练习

6.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

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