6.4.4 拓扑排序

教材导航 · 第6章

原书定位

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

AOV 网以顶点表示活动,弧 u→vu\to v 表示 uu 必须先于 vv。拓扑序中每条弧的起点都排在终点之前。

反复取入度为 0 的顶点输出,删除其出边并更新后继入度;邻接表实现 O(n+m)O(n+m)。若输出少于 nn 个顶点,图中有环。多个可选零入度顶点会带来多个拓扑序;每步恰有一个可选顶点时序列唯一。

逆拓扑序可通过反复删出度 0 的顶点获得,DFS 的完成次序也可用于构造。按拓扑次序编号后,弧从较小编号指向较大编号,邻接矩阵的非零元位于上三角。

拓扑排序及入度变化

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

拓扑排序逐轮删除顶点

拓扑排序逐轮删除顶点,原书P239。

对应练习

6.4 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P238,PDF第250页

原书对照,原书P239,PDF第251页

原书对照,原书P240,PDF第252页