6.3.3 图的遍历与图的连通性

教材导航 · 第6章

原书定位

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

无向图中,一次 BFS 或 DFS 访问起点所在的全部连通分量;完整遍历中外层启动次数等于连通分量数。可据此判断连通性,并结合边数 m=n−1m=n-1 判断是否为树。

有向图的一次搜索访问的是起点沿有向边可达的顶点。外层启动次数依赖起点顺序,不能直接当作强连通分量数;从某点能到所有点也不代表任意两点互相可达。

有向图一次搜索的可达范围

有向图一次搜索的可达范围,原书P223。

对应练习

6.3 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P223,PDF第235页