6.3.3 图的遍历与图的连通性
原书定位
印刷页P223起,对应PDF第235页。下文为目视整理的知识提要;完整内容见原书对照。
无向图中,一次 BFS 或 DFS 访问起点所在的全部连通分量;完整遍历中外层启动次数等于连通分量数。可据此判断连通性,并结合边数 判断是否为树。
有向图的一次搜索访问的是起点沿有向边可达的顶点。外层启动次数依赖起点顺序,不能直接当作强连通分量数;从某点能到所有点也不代表任意两点互相可达。

有向图一次搜索的可达范围,原书P223。
对应练习
关联知识
原书对照
展开原书对照截图
