图论算法论题有向无回路图又称为dag
对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G包含(u,v)，则在序列中u出现在v之前（如果图是有回路的就不可能存在这样的线性序列）
一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右
因此，拓扑排序不同于通常意义上对于线性表的排序
有向无回路图经常用于说明事件发生的先后次序，图1给出一个实例说明早晨穿衣的过程
必须先穿某一衣物才能再穿其他衣物（如先穿袜子后穿鞋），也有一些衣物可以按任意次序穿戴（如袜子和短裤）
图1中说明经拓扑排序的结点以与其完成时刻相反的顺序出现
因为深度优先搜索的运行时间为θ(V+E)，每一个v中结点插入链表需占用的时间为θ(1)，因此进行拓扑排序的运行时间θ(V+E)
为了证明算法的正确性，我们运用了下面有关有向无回路图的重要引理
以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。
