如果一个有向图不存在环，也就是任意结点都无法通过一些有向边回到自身，那么称这个有向图为有向无环图。英文名叫 Directed Acyclic Graph，缩写是 DAG。
对一个有向无环图 G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v ，若边<u,v> ∈ E(G)，则 u 在线性序列中出现在 v 之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
拓扑排序的性质：
（1）、能拓扑排序的图，一定是有向无环图。
（2）、如果有环，那么环上的任意两个节点在任意序列中都不满足条件了。
（3）、有向无环图，一定能拓扑排序。
如何判定一个图是否是有向无环图呢？检验它是否可以进行 拓扑排序 即可。
拓扑排序有何作用？拓扑排序主要用来解决有向图中的依赖解析（dependency resolution）问题。
游戏升级的先后顺序就是一个拓扑序。
用计算机专业的几门课程的学习次序来描述拓扑关系 ，显然对于一门课来说，必须先学习它的先导课程才能更好地学习这门课程，比如学数据结构必须先学习C语言和离散数学，而且先导课程中不能有环，否则没有尽头了。
拓扑排序的结果不唯一，比如“C语言”和“离散数学”就可以换下顺序，又或者把“计算机导论”向前放在任何一个位置都可以。总结一下就是，如果某一门课没有先导课程或是所有的先导课程都已经学习完毕，那么这门课就可以学习了。
拓扑排序的操作方法：入度表算法（也叫BFS算法或Kahn算法）Kahn算法又叫做入度表算法，算法步骤如下：
1、找出入度为0的点。入度为0，就是没有有任何节点指向它。
2、将这些点的出边删除，也就是这些点指向的目的顶点入度-1，于是就有了新的入度为0的点产生。
3、新的入度为0的点继续执行步骤二，直到不再存在入度为0的点。如果顶点全部被处理完了，那么拓扑排序也就结束了；如果还有顶点没有处理完，那么必定存在环路（所以，拓扑排序也是用来判环的方法）。
拓扑排序的时间复杂度 如果 DAG 网络有 n 个顶点，m 条边，在拓扑排序的过程中，搜索入度为零的顶点所需的时间是 O(n)。在正常情况下，每个顶点进一次队列，出一次队列，所需时间 O(n)。每个顶点入度减 1 的运算共执行了 m 次。所以总的时间复杂为 O(n+m)。因为拓扑排序的结果不唯一，所以题目一般会要求按某种顺序输出，就需要使用优先级队列，这里采取了最小字典序输出。