6.4.4 拓扑排序
原书定位
印刷页P238起,对应PDF第250页。下文为目视整理的知识提要;完整内容见原书对照。
AOV 网以顶点表示活动,弧 表示 必须先于 。拓扑序中每条弧的起点都排在终点之前。
反复取入度为 0 的顶点输出,删除其出边并更新后继入度;邻接表实现 。若输出少于 个顶点,图中有环。多个可选零入度顶点会带来多个拓扑序;每步恰有一个可选顶点时序列唯一。
逆拓扑序可通过反复删出度 0 的顶点获得,DFS 的完成次序也可用于构造。按拓扑次序编号后,弧从较小编号指向较大编号,邻接矩阵的非零元位于上三角。

拓扑排序及入度变化,原书P238。

拓扑排序逐轮删除顶点,原书P239。
对应练习
关联知识
原书对照
展开原书对照截图


