6.5 本章归纳总结

教材导航 · 第6章

原书定位

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

用统一的邻接访问接口可复用 BFS、DFS 等算法,但性能仍取决于底层存储及接口实现。邻接表遍历应直接推进边指针,避免每次调用“下一邻点”都从表头重新搜索,导致额外开销。

模拟算法时分清维护量:BFS 是层数,Prim 是接入当前树的最小边权,Dijkstra 是到源点的暂定距离,关键路径的 ve 是前驱约束下的最大到达时间。

删去某个顶点及其关联边后连通分量数增加,该顶点是割点。逐点删除再搜索可直观判定;更高效的做法可在一次 DFS 中维护发现次序与回溯信息。

关联知识

原书对照

展开原书对照截图

原书对照,原书P267,PDF第279页

原书对照,原书P268,PDF第280页