1、什么是拓扑排序，也就是拓扑排序的概念
实际上，拓扑排序是一种图论算法，该算法在《数据结构与算法》一书中有涉猎。引用维基百科的定义：
在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。
（1）每个顶点出现且只出现一次；
（2）若A在序列中排在B的前面，则在图中不存在从B到A的路径。
也可以定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。
是不是觉得看完概念还是很晕的感觉，下面就用一个实例来讲具体的拓扑排序样例。
（a）有向图网（AOV） （b）输出v6后 （c）输出v1后 （d）输出v4后 （e）输出v3后 （f）输出v2后
输出排序结果：v6-v1-v4-v3-v2-v5
此拓扑排序的思想是：
（1）从有向图中选取一个没有前驱的顶点，并输出之；
（2）从有向图中删去此顶点以及所有以它为尾的弧；
重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。没有前驱 – 入度为零，删除顶点及以它为尾的弧– 弧头顶点的入度减1。
何谓入度？
我觉得得先明白什么是度？度（Degree）：一个顶点的度是指与该顶点相关联的边的条数，顶点v的度记作d(v)。
入度：对于有向图来说，一个顶点的度可细分为入度和出度。一个顶点的入度是指与其关联的各边之中，以其为终点的边数。
出度：出度则是相对的概念，指以该顶点为起点的边数。
以v6这个顶点为例，它的入度为0，出度为2。
以v5这个顶点为例，它的入度为3，出度为0。
以v4这个顶点为例，它的入度为2，出度为1。
以v3这个顶点为例，它的入度为1，出度为2。
以v2这个顶点为例，它的入度为2，出度为0。
以v1这个顶点为例，它的入度为0，出度为3。
经验证，一个有向五环图中所有顶点的入度之和(0+3+2+1+2+0=8)等于所有顶点的出度之和(2+0+1+2+0+3=8)。
2、拓扑排序的作用
不禁有人就问了，有很多排序算法啊，快速排序，插值排序，这个排序到底有什么优点呢？平常这种排序又用于哪种场景呢？
我们说快速排序是不稳定的，这是因为最后的快排结果中相同元素的出现顺序和排序前不一致了。如果用偏序的概念可以这样解释这一现象：相同值的元素之间的关系是无法确定的。因此它们在最终的结果中的出现顺序可以是任意的。而对于诸如插入排序这种稳定性排序，它们对于值相同的元素，还有一个潜在的比较方式，即比较它们的出现顺序，出现靠前的元素大于出现后出现的元素。因此通过这一潜在的比较，将偏序关系转换为了全序关系，从而保证了结果的唯一性。而拓扑排序就是一种将偏序转换为全序的一种算法。
这里要补充两个概念，偏序和全序？
偏序：有向图中两个顶点之间不存在环路，至于连通与否，是无所谓的。
全序：就是在偏序的基础之上，有向无环图中的任意一对顶点还需要有明确的关系(反映在图中，就是单向连通的关系，注意不能双向连通，那就成环了)。
意思就是讲，一个不确定的偏序关系经全序后就有一种确定的先后顺序了。
既然有先后，那么在实际生活中的选课问题，比如大一时一定要修完这门课，大二才学第二门课，这种排课问题就是拓扑排序问题。
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
提示：
输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/course-schedule
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution(object): def canFinish(self, N, prerequisites): """ :type N,: int :type prerequisites: List[List[int]] :rtype: bool """ graph = collections.defaultdict(list) indegrees = collections.defaultdict(int) for u, v in prerequisites: graph[v].append(u) indegrees[u] += 1 for i in range(N): zeroDegree = False for j in range(N): if indegrees[j] == 0: zeroDegree = True break if not zeroDegree: return False indegrees[j] = -1 for node in graph[j]: indegrees[node] -= 1 return True