6.3 图的遍历
原书定位
印刷页P219起,对应PDF第231页。下文为目视整理的知识提要;完整内容见原书对照。
BFS 与 DFS 都需维护访问标记,避免环和多条路径引发重复访问。完整遍历还要扫描全部顶点,从每个尚未访问的顶点重新启动搜索。
邻接表时间为 ,邻接矩阵为 ;访问标记、队列或递归栈的辅助空间最坏 。遍历顺序取决于起点与邻接点的考察顺序。
下级知识点
对应练习
关联知识
原书对照
展开原书对照截图

原书定位
印刷页P219起,对应PDF第231页。下文为目视整理的知识提要;完整内容见原书对照。
BFS 与 DFS 都需维护访问标记,避免环和多条路径引发重复访问。完整遍历还要扫描全部顶点,从每个尚未访问的顶点重新启动搜索。
邻接表时间为 ,邻接矩阵为 ;访问标记、队列或递归栈的辅助空间最坏 。遍历顺序取决于起点与邻接点的考察顺序。
