1. 什么是拓扑排序
   拓扑排序（Topological Order），很多人听说过，但是不了解的一种算法。或许很多人只知道它是图论的一种排序，至于干什么的不清楚。又或许很多人可能还会认为它是一种啥排序。

而实质上它只是将DAG图的顶点排成一个线性序列，得到一个顶点的全序集合。其排序的顺序依据就是节点的指向关系。比如前言的DAG图：

…
节点5在节点4和节点3的后面
节点9在节点6和节点7的后面
…
那么最后得到的节点的线性序列结果,也一定要满足上面的指向顺序。

每一个节点都拥有入度（有多少点导向它，也就是开始它有多少前提）和出度（它导向多少点，也就是它是多少其他节点开始的前提）。例如节点5的入度为3和4，出度为7。

拓扑排序的结果不是唯一的，只要符合上面的条件，那么它就是拓扑序列，比如1 2 4 3 6 5 7 9和2 1 3 4 5 6 7 9，这两个结果都是可行的。

官方一点的定义：将有向图中的节点以线性方式进行排序。即对于任何连接自节点u到节点v的有向边uv，在最后的排序结果中，节点u总是在节点v的前面。
2. 现实案例
看了上面关于拓扑排序的概念如果还觉得十分抽象的话，那么不妨考虑一个非常非常经典的例子——选课。

假设我非常想学习一门《jsp入门》的课程，但是在修这么课程之前，我们必须要学习一些基础课程，比如《JAVA语言程序设计》，《HTML指南》等等。那么这个制定选修课程顺序的过程，实际上就是一个拓扑排序的过程，每门课程相当于有向图中的一个顶点，而连接顶点之间的有向边就是课程学习的先后关系。

只不过这个过程不是那么复杂，从而很自然的在我们的大脑中完成了。将这个过程以算法的形式描述出来的结果，就是拓扑排序。

image

可以看到，上图中的学习顺序，就是拓扑序列，其不止一个结果。

拓扑排序算法在工程学中十分重要。

节点成环的图，无法被拓扑排序，因为这在工程上本身没有意义，比如A——>B——>C——>A，那么这个工程永远无法被开始。
3. 算法实现
拓扑排序的最优时间复杂度是O(m+n),其中m和n是DAG图中节点数和边数。因为拓扑排序至少要对DAG图的节点和边进行一次完整的遍历。

拓扑排序的最优空间复杂度是O(m+n),其中m和n是DAG图中节点数和边数。我们一般使用邻接表来存储DAG图，因此空间复杂度是O(m+n)。

拓扑排序

一个无环的有向图称作有向无环图。简称DAG图。

有向无环图是描述含有公共子式的表达式的有效工具。可以利用有向无环图，则可以实现对相同子式的共享，从而节省存储空间。

AOV网（顶点表示活动的网）：在一个(用DAG图)表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系。

拓扑序列：由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
拓扑排序是一个有向无环图（DAG）的所有顶点的线性序列。且该序列必须满足下面两个条件：

1. 每个顶点出现且只出现一次。

2. 若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。

拓扑排序是对一个有向图构造拓扑序列的过程。

DAG图拓扑排序的算法思想：

1. 在有向图中选择一个没有前驱的顶点且输出之。
2. 在图中删除该顶点和它射出的所有弧。
3. 重复上述两步，直到全部顶点均已全部输出，或者当前图中不存在没有前驱的顶点为止。
   ◆ 后一种情况说明有向图中肯定存在环

DAG图拓扑排序的算法步骤：

1. 将邻接表中所有入度为0的顶点进栈
2. 栈非空时，弹出栈顶元素Vj
   ◆ 在邻接表中查找Vj的直接后继Vk，将Vk的入度减1
   ◆ 若Vk的入度为0则进栈
3. 重复上述操作直至栈空为止
   ◆ 若栈空时输出的顶点个数不是n，则有向图有环

拓扑排序：如果图中有一条从u到v的路径，则顶点v必须出现在顶点u之后。找出顶点活动网中的拓扑序列称“拓扑排序”。

拓扑排序的过程：

邻接表：

由以上步骤得拓扑有序序列为0，1，3，2，5，4，6。

拓扑排序既可用深度优先搜索，也可用广度优先搜索实现。

时间复杂度为O(n+e)

关键路径

AOE网(活动在边上)： AOE网是一个带权的有向无环图。其中顶点表示事件，弧表示活动，权表示活动持续的时间。

AOE网与AOV网的相同点：

• 都是有向无环图。

AOE网与AOV网的不同点：

• AOE网的边表示活动，边有权值，边代表活动持续时间；顶点表示事件，事件是图中新活动开始或者旧活动结束的标志。
• AOV网的顶点表示活动，边无权值，边代表活动之间的先后关系。

AOE图的性质：

• 所有AOE-网只有一个源点（入度为0的点)和一个汇点（出度为0的点）。
  例如：V1表示整个工程开始，V9表示整个工程结束。
• 只有进入某顶点的各个活动结束，该顶点所代表的事件才能发生；
  只有某顶点所代表的事件发生， 从该顶点出发的各个活动才能开始（例如：顶点V5）。

关键路径
定义：在AOE网中，从源点从汇点的所有路径中，具有最大路径长度的路径称为关键路径。

假设开始点是V1，从V1到Vi的最长路径长度叫做事件Vi的最早发生事件。(这个事件决定了所有以Vi为尾的弧所表示的活动的最早开始时间。)

• e(i)表示活动ai的最早开始的时间
• l(i)表示活动ai的最迟的开始时间；
• 两者之差l(i)-e(i)意味着完成活动ai的时间余量。
• 关键活动：l(i)=e(i)
  

概念：
假设：活动ai由弧<j , k>表示，持续时间为dut（<j , k>）

• ① 事件Vj的最早发生时间ve(j) ：源点到Vj 最长路径的长度
  ◆ 典例：事件V5的最早发生时间（正(源点往后)推为7）

假设：活动ai由弧<j , k>表示，持续时间为dut（<j , k>）

• ② 活动ai的最早开始时间e(i)： 由性质2，e(i)决定了
  所有以Vj为尾的弧，所表示活动的最早开始时间
  ◆ 典例 ：活动a7和a8的最早开始时间（7，由定义可知）
  ◆ 性质3： e(i)=ve(j)
  ◆ e(i)=ve(j)的意义：活动最早开始时间由射出结点决定
  

假设：活动ai由弧<j , k>表示，持续时间为dut（<j , k>）

• ③ 事件Vk的最迟发生时间vl(k) ：Vk到汇点最长路径的长度
  ◆ 典例：事件V8的最迟发生时间（倒推为14）
  
  假设：活动ai由弧<j , k>表示，持续时间为dut（<j , k>）
• ④ 活动ai的最迟开始时间l(i)：由vl(k)倒推
  ◆ 典例：活动a9的最迟开始时间（倒推为10）
  ◆ 性质4： l(i)=vl(k)- dut（<j , k>）
  ◆ 利用性质 l(i)=vl(k)- dut（<j , k>
• ⑤ 定义：完成活动ai的时间余量： l(i)-e(i)
  ◆ 定义：l(i)=e(i)的活动称为关键路径/非关键路径的含义

• 归纳：重要性质

⑴ 性质3： e(i)=ve(j)
⑵ 性质4： l(i)=vl(k)- dut（<j , k>）
意义：将e和l的求解转换为ve和vl的求解
⑶ 关键路径算法

关键路径是指设计中从输入到输出经过的延时最长的逻辑路径。