拓扑排序

概念

对一个有向无环图G(Directed Acyclic Graph，简称DAG)进行拓扑排序，是将G中所有顶点排列成一个线性序列，使得图G中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。这样的线性序列称为满足拓扑次序的序列，简称为拓扑序列。图的拓扑排序序列往往不唯一。
通常我们将顶点表示活动，边表示活动先后关系的有向图称为顶点活动网(Activity On Vertex Network)简称AOV网，AOV网一定是一个有向无环图

拓扑排序生成步骤

对AOV网生成拓扑排序，主要是循环以下两步，直到不存在入度为0的顶点为止：
1：找任意一个入度为0的点，输出
2：删除该点，并删除边，将该点所指向的所有点的入度减1
循环结束后，判断输出个数是否等于顶点个数，不等说明存在环，无法生成。
因为每次选入度为0的点，都是任意的，所以拓扑序列可能不唯一