讲拓扑排序的概念，先来回顾一个大家熟悉的东西：技能树（图）！
因为这个特好理解，玩过暗黑或其他RPG游戏的都应该见过类似的技能树，一句话，就是学习高级技能前需要先学习之前的低级技能。
一个技能树其实是一个简单的图，你可以把它再变化一下就是一张图，即让一些高级技能间也发生联系，使得学习一种高级技能可以通过多种途径，于是这就是一个正儿八经的图了。

拓扑排序就是要排出这样一个线性序列，即“高等技能”一定在“初等技能”的后面，绝不会出现“高等技能”学完后再学“初等技能 ”的情况。

言归正传，学习拓扑排序，需要知道如下几个概念。
1、图：可以理解为网络，一个由点和线组成的网络，线段有方向称为有向图，线段无方向称为无向图。
2、AOV网络：就是 Activity On Vertex network的简称，顶点活动网，它是一个有向无环图。有向：就是指有先后顺序，比如技能树中，学习技能有先后顺序。无环：就是图里面没有首尾相接的“圈”，比如技能树中学完高技能后总不能又回到低技能的学习吧？
3、邻接矩阵：这是一种图的存储方法，用一个二维数组来来存储图的结构。该矩阵里只有0和1，Aij 处为1代表从i到j有一条连线。比如如下二维矩阵，就表示了一个对应的图（这里规定它是有向图）

4、邻接表：这是另一种图的存储方法，稍微复杂一点，利用到了数组和链表还有结构体，和队列、栈、链表类似，邻接表可以看成是一种单独的数据结构。包括一个纵向结构体数组（纵表）和横向链表（横表），它表示了与上面相同的一个图，结构如下所示。

一般我们是通过邻接矩阵来构造邻接表，之后拓扑排序时真正使用的是邻接表，因为它包含了比邻接矩阵更多的信息，并且更便于之后的排序操作。

纵表结构体包含了1个前继数量、一个节点数据和1一个结构体指针。前继表示有多少个其它节点指向了该节点。指针用来指向该节点所对应的横表，横表记录了该节点所有指向节点的位置（用一个索引值表示，即纵表数组下标）。

struct Node                 //纵表结构体
{
     char data;             //存储节点数据
     struct Link *link;     //链接对应的横表，注意，此处不是链接自身结构体类型。
     int count;             //存储前继的个数
}

横表结构体中包含一个节点索引值和一个结构体指针。索引值记录了该节点是纵表中的第几个节点，指针指向下一个横表节点，结构体形式如下。

struct Link                 //横表结构体
{
     char index;            //存储节点在纵表中的索引位置
     struct Link *next;     //链接下一个节点，该指针类型是自身结构体类型。
}

上述4个概念比较重要，特别是邻接表的概念，是数据结构里的一个综合应用，也是下述拓扑排序的主要操作对象。
现在开始排序，这只是一种可能的排序方法，一幅图的拓扑排序能有多种结果。

还是上面所示的图，这个图的一种可能排序为：1 4 3 6 2 5 ，可以验证一下，应该没错，我们输出的就是这个结果。
算法结构如下：
While (能输出) {
1 找一个前继为0的点，输出并置标志（置标志的含义是：表面该纵表节点输出过了，不要重复输出，输出即意味着从图中去掉了一个节点）
2 找对应输出点的链中每一个结点的index,在纵表中对应节点的count减去1，（含义是：上一步去掉了一个节点，这一步要去掉该节点所发出的所有线）
}
当把纵表中的数全部遍历完，输出的顺序即一次拓扑排序。

到此为止，拓扑排序的一般算法就讲完了，接下来说的是提升效率的一点改进。

如何做到算法执行过程中，节点输出不重复且循环次数少？

方法有很多种，不同方法会产生不同输出结果，如果对排序结果没有额外要求的话，这些结果都是正确的拓扑排序。

一种实现方法就是：
将纵表中前继为0的点组成一个栈，每次从栈里取节点，这种方法同样能够遍历整个纵表，并且不需要耗费额外的存储开销（不需要再建立一个链表结构的栈，纵表结构体中的count值可以记录节点在栈中的位置，这是一种数据复用的思想，因为凡是conut值被减为0的节点，该count变量都不再具有其它用途，可以被重复利用来记录节点在栈中的位置）
以上面的邻接表为例：

算法开始时：
1、从纵表开始，找到前继为0的点，压栈，此时栈里只有1，

2、从栈顶取一个节点（弹栈），此时就是1，输出节点值1。
3、将其横表所对应的节点count值减1，凡是count值被减为0的压栈
。
此时，按照操作顺序，纵表中2号节点的count值先被减为0，所以在栈底，随后依次是3号节点和4号节点，至此第一条横表操作完毕，栈结构如下图。

3、再次从栈里弹出一个节点，此时是4，将对应横表节点的Count值减1，减过之后，没有新的count为0的点，所以没有新元素进栈。


4、不断重复，继续弹栈、减去横表对应节点count值、若有0就压栈，直到最后，所有栈元素输出空，即排序完成。
这种方法输出的节点顺序是1-4-3-6-2-5，这也是从栈里弹出的顺序，这种方法好处是遍历次数少、额外存储空间开销少。