6.3 图的遍历

教材导航 · 第6章

原书定位

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

BFS 与 DFS 都需维护访问标记,避免环和多条路径引发重复访问。完整遍历还要扫描全部顶点,从每个尚未访问的顶点重新启动搜索。

邻接表时间为 O(n+m)O(n+m),邻接矩阵为 O(n2)O(n^2);访问标记、队列或递归栈的辅助空间最坏 O(n)O(n)。遍历顺序取决于起点与邻接点的考察顺序。

下级知识点

对应练习

6.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

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