6.5 本章归纳总结
原书定位
印刷页P267起,对应PDF第279页。下文为目视整理的知识提要;完整内容见原书对照。
用统一的邻接访问接口可复用 BFS、DFS 等算法,但性能仍取决于底层存储及接口实现。邻接表遍历应直接推进边指针,避免每次调用“下一邻点”都从表头重新搜索,导致额外开销。
模拟算法时分清维护量:BFS 是层数,Prim 是接入当前树的最小边权,Dijkstra 是到源点的暂定距离,关键路径的 ve 是前驱约束下的最大到达时间。
删去某个顶点及其关联边后连通分量数增加,该顶点是割点。逐点删除再搜索可直观判定;更高效的做法可在一次 DFS 中维护发现次序与回溯信息。
关联知识
原书对照
展开原书对照截图

