拓扑排序（Kahn算法）

1. 概念及规则

• 对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

• 规则：图中每个顶点只出现一次A在B前面，则不存在B在A前面的路径。(否则就会形成环)顶点的顺序是保证所有指向它的下个节点在被指节点前面例如A—>B—>C那么A一定在B前面，B一定在C前面这个核心规则下只要满足即可，所以拓扑排序序列不一定唯一

2. 应用

• 工厂里产品的生产线上,一个产品由若干个零部件组成。零部件生产时,也存在这两种关系:先后关系,即一个部件必须在完成后才能生产另一个部件;部件间无先后关系,即这两个部件可以同时生产

• 大学里某个专业的课程学习,有些课程是基础课,它们可独立于其他课程,即无前导课程; 有些课程必须在某些基础课学完之后才能开始

3. 算法及实现

• 实现步骤：维护一个入度为0的顶点的集合(栈、队列、优先队列皆可)每次从该集合中取出一个顶点u(栈顶)遍历u的邻接点v,v的入度rd[v]--,如果rd[v]==0,v进栈队列为空，出栈数小于n，存在环

• 时间复杂度：由于每个点入栈出栈一次，每条边扫描一次，时间复杂度为O(n + e)

• 图示：