概念
有向无环图（Directed Acyclic Graph）:一个无环的有向图简称DAG图
拓扑排序（Topological Sort）将一个有向无环图G中所有顶点排成一个线性序列使得对图中任意一对顶点u和v若＜uv＞∈E(G)则u在线性序列中出现在v之前
拓扑序列将一个有向无环图进行拓扑排序得到的线性序列称为满足拓扑次序（Topological Order）的序列
拓扑排序是对于有向无环图才可以排序成功的若图中存在有向环则该拓扑序列不存在
拓扑排序两种方法
无前趋的顶点优先
步骤
() 在有向图中选一个没有前驱的顶点且输出之
() 从图中删除该顶点且删除以它为尾的所有弧
() 重复上述两步直至全部顶点均已输出或者图中不存在无前驱的顶点为止后一种情况则说明有向图中存在环
无后继的顶点优先
根据这个算法每一步输出的是当前无后继(出度为)的顶点要将其序列逆序后才是拓扑序列可以用一个栈来保存输出结果
当采用DFS算法进行拓扑排序时若给定的图是一个非DAG也就是图中存在有向环时它不能正常工作这是因为在DFS遍历中凡访问过的结点均不会再次被访问因此这个算法将忽略图中的有向环的存在从而造成错误在前其它算法中若存在有向环则输出结点数总小于顶点总数因此能够被发现
