图的表示与遍历

稠密图用矩阵、稀疏图用表；BFS 给出最短跳数与层次，DFS 给出拓扑序、连通分量与环检测。本章讲两种遍历的递归/迭代实现与时间戳技巧。

本章要点

• CSR 格式是大图的标准压缩表示
• DFS 的发现/完成时间戳能回答很多结构问题
• 拓扑排序 = DFS 完成时间的逆序

相关阅读

• 图的基本算法

写作状态

本章目前为提纲，正文待撰写。