拓扑排序是在一个有向无环图(Directed Acyclic Graph, DAG)中对顶点的排序, 每个有向无环图可以有一个或者多个拓扑排序. 若图中存在环, 则无法进行排序, 因为环上的两点 (v, w) 相互依赖, 即 v 先于 w, w 也先于 v.

基本概念

一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动(activity)。在整个工程中，有些子工程(活动)必须在其它有关子工程完成之后才能开始，也就是说，一个子工程的开始是以它的所有前序子工程的结束为先决条件的，但有些子工程没有先决条件，可以安排在任何时间开始。

为了形象地反映出整个工程中各个子工程(活动)之间的先后关系，可用一个有向图来表示，图中的顶点代表活动(子工程)，图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。

通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称 AOV 网。

维基百科

在计算机科学领域，有向图的拓扑排序是其顶点的线性排序，使得对于从顶点 u 到顶点 v 的每个有向边uv，u 在排序中都在 v 之前。

例如，图形的顶点可以表示要执行的任务，有向边可以表示一个任务必须在另一个任务之前执行的约束; 在这个应用中，拓扑排序只是一个有效的任务顺序。 当且仅当图中没有循环时，即如果它是有向无环图，则拓扑排序是可能的。 任何 DAG 具有至少一个拓扑排序，并且已知这些算法用于在线性时间内构建任何 DAG 的拓扑排序。

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个 拓扑排序(Topological sorting)

• 每个顶点出现且只出现一次；
• 若A在序列中排在B的前面，则在图中不存在从 B 到 A 的路径。

拓扑排序算法

由 AOV 网构造拓扑序列的拓扑排序算法主要是循环执行以下几步，直到不存在入度为 0 的顶点为止。

1. 初始时, 计算所有顶点的 \(\color{blue}{入度}\), 使用队列记录入度为 0 的顶点
2. 选择一个入度为 0 的顶点出发, 因为这些顶点没有任何先决条件
3. 从网中删除此顶点及所有出边, 更新剩余节点的入度, 并使用队列跟踪入度为 0 的顶点
4. 重复2, 3步骤, 直到队列为空

循环结束后，若输出的顶点数小于网中的顶点数，则说明图中有环路，否则输出的顶点序列就是一种拓扑序列

当使用邻接链表时, 拓扑排序的时间复杂度为 O(|E|+|V|)

拓扑排序的应用

1. 课程选修的先决条件
2. 检测死锁
3. 计算作业的流水线

Course Schedule

您必须参加总共 n 门课程，标记为 0 ~ n-1. 有些课程可能有先决条件，例如要修课程 0，你必须先修课程 1，表示为一对元组：[0, 1], 您可以假设输入先决条件中没有重复的边。

鉴于课程总数和先决条件对列表，您是否可以完成所有课程？

example

Input: 2, [[1, 0]] Output: trueInput: 2, [[1, 0], [0, 1]] Output: false

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;class Solution {public:    bool canFinish(int numCourses, vector
        
         
          >& prerequisites) { vector
          
            indegrees(numCourses, 0); // 入度 unordered_map