拓扑排序

对于一个工程，其中的某些子工程必须要在另外一些子工程完成后才能开始。对一个有向无环图（Directed Acyclic Graph, DAG），按照图中的次序关系，将顶点排成一个线性序列，对于其中没有限定次序的并列顶点我们认为添加任意次序，由此得到的线性序列称为拓扑有序序列。

相关概念

• AOV 网（Activity On Vertex Network）：顶点表示活动，边表示活动之间的关系。
• 拓扑序列（Topological Order）：将 AOV 网中的所有顶点排成一个线性序列，满足如果 AOV 网中存在顶点 i 到顶点 j 的路径，那么序列中顶点 i 要在顶点 j 前面。
• 拓扑排序（Topological Sort）：构造 AOV 网的拓扑排序的操作。

基本思想

1. 在有向图中选一个入度为 0 的顶点输出。
2. 从图中删除该顶点及所有它的出边。
3. 重复执行步骤 1 和 2，直到全部顶点均已输出，或图中剩余顶点的入度均不为 0（说明图中存在回路，无法继续拓扑排序）。

简单来说就是找到入度为 0 的点为可执行活动，执行后将该顶点删除去掉该活动的限制，再寻找与其有关的活动是否有可执行的活动。

算法概要

增加一个存放各顶点入度的数组 indegree[]。

1. 扫描 indegree[]，将入度为零的顶点入栈。
2. while (栈非空) {
   • 弹出栈顶顶点并输出。
   • 检查该顶点的出边表，将每条出边 (vᵢ, vⱼ) 的终点 vⱼ 的入度减 1。
   • 若 vⱼ 的入度减至 0，则将 vⱼ 入栈。 }
3. 若输出的顶点数小于 n，则说明”有回路”；否则正常结束。

算法分析

设 AOV 网有 n 个顶点，e 条边。

1. 对 e 条弧求各顶点的入度的时间复杂度是 O(e)。
2. 初始建立入度为 0 的顶点栈，要检查所有顶点一次，执行时间为 O(n)。
3. 排序中，若 AOV 网无回路，则每个顶点入、出栈各一次，每个边表结点被检查一次，执行时间为 O(n + e)。

拓扑排序算法的时间复杂度为 O(n + e)。

特点

1. 一个有向图的拓扑序列不一定唯一。
2. 有向无环图一定存在拓扑序列。
3. 有向有环图不存在拓扑序列。
4. 通过构造拓扑序列，可判定 AOV 网是否存在环。

链接到

• 上一个知识点：7.8 Kruskal算法
• 下一个知识点：7.10 关键路径