数据结构之 【拓扑排序】_数据结构 拓扑排序

拓扑排序的概念

一个无环的有向图称为无环图（Directed Acyclic Graph），简称DAG图。

所有工程或者某种流程都可以分为若干个小的工程或者阶段，我们称这些小的工程或阶段为“活动”。

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称之为AOV网（Active On Vertex Network），AOV网不能存在回路。

拓扑序列：设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列V1，V2，....，Vn满足若从顶点Vi到Vj有一条路径，则在顶点序列中顶点Vi必在顶点Vj之前。则我们称这样的顶点序列为一个拓扑序列。

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

拓扑排序算法：

对AOV网进行拓扑排序的方法和步骤如下：

1. 从AOV网中选择一个没有前驱的顶点（该顶点的入度为0）并且输出它；
2. 从网中删去该顶点，并且删去从该顶点出发的全部有向边；
3. 重复上述两步，知道剩余网中不再存在没有前去的顶点为止。