【数据结构与算法10】拓扑排序

一、概念

定义

拓扑排序，其实就是对一个有向图构造拓扑序列的过程。

AOV 网

在一个表示工程的有向图中，用定点表示活动，用弧表示活动之间的有限关系，这样的有向图为顶点表示活动的网，我们称为AOV 网(Activity On Vertex Network)。

拓扑序列

设 G= (V, E) 设一个具有n 个顶点的有向图， V 中的顶点序列 v₁, v₂, …… v_n，满足若从订单 v_i 到 v_j 有一条路径，则在顶点序列中定点 v_i 必在顶点 v_j 之前。则我们称这样的顶点序列为一个拓扑序列。

二、排序算法

三、流程解析