有向无环图及其应用一个无环的有向图称做有向无环图,简称DAG图。DAG图是一类较有向树更一般的特殊有向图。拓扑排序通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动。这些活动完成时，整个工程也就完成了。例，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的活动。顶点表示活动，有向边表示活动的先后关系的网简称为AOV网。AOV网中不能有环，否则工程无法顺利进行。在AOV网中，若不存在回路，则所有活动可排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological