知识点总结
拓扑排序并非一种排序算法，它能得到一个 AOV 网络的拓扑序列，用于判断有向无环图中是否有环，即可以判断一系列活动是否有循环依赖；
解决一个工程中的任务是否能够顺利完成，判断是否出现环。（补充：还有一种判断图中是否有环的数据结构是“并查集”）。
具体例子：去店里吃饭的问题：顾客要求先吃饭再付钱，商家要求先收钱再做菜，这就是循环依赖，拓扑排序就可以帮助我们判断是否形成环。算法4那本书里面就有拓扑排序。
步骤：找无前驱的结点（即入度为 的结点），一个一个地删去（使用队列或者栈），删的时候，把邻居结点的入度（即度 -1 ）。借助队列实现。
“拓扑排序”用于对有先后顺序的任务的输出，如果先后顺序形成一个环，那么就表示这些任务头尾依赖，就永远不能完成。
因此“拓扑排序”还可以用于检测一个图中是否有环。
LeetCode 上拓扑排序目前（截止 2019 年 2 月 16 日早）一共有 5 题。
我们就做两题。
LeetCode 第 207 题：课程表
传送门：207. 课程表。
现在你总共有 n 门课需要选，记为
0到n-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。这是不可能的。说明:
- 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
提示:
- 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
- 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
- 拓扑排序也可以通过 BFS 完成。
思路1：Kahn 算法，即拓扑排序。构建的邻接表就是我们通常认识的邻接表，每一个结点存放的是后继结点的集合。
该方法的每一步总是输出当前无前趋（即入度为零）的顶点。为避免每次选入度为 的顶点时扫描整个存储空间，可设置一个队列暂存所有入度为
的顶点。
具体做法如下：
1、在开始排序前，扫描对应的存储空间，将入度为 的顶点均入队列。
2、只要队列非空，就从队首取出入度为 的顶点，将这个顶点输出到结果集中，并且将这个顶点的所有邻接点的入度减
，在减
以后，发现这个邻接点的入度为
，就继续入队。
最后检查结果集中的顶点个数是否和课程数相同即可。
Python 代码：
class Solution(object):
# 思想：该方法的每一步总是输出当前无前趋（即入度为零）的顶点
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int 课程门数
:type prerequisites: List[List[int]] 课程与课程之间的关系
:rtype: bool
"""
# 课程的长度
clen = len(prerequisites)
if clen == 0:
# 没有课程，当然可以完成课程的学习
return True
# 步骤1：统计每个顶点的入度
# 入度数组，一开始全部为 0
in_degrees = [0 for _ in range(numCourses)]
# 邻接表
adj = [set() for _ in range(numCourses)]
# 想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
# [0,1] 表示 1 在先，0 在后
# 注意：邻接表存放的是后继 successor 结点的集合
for second, first in prerequisites:
in_degrees[second] += 1
adj[first].add(second)
# print("in_degrees", in_degrees)
# 首先遍历一遍，把所有入度为 0 的结点加入队列
res = []
queue = []
# 步骤2：拓扑排序开始之前，先把所有入度为 0 的结点加入到一个队列中
for i in range(numCourses):
if in_degrees[i] == 0:
queue.append(i)
counter = 0
while queue:
top = queue.pop(0)
counter += 1
# 步骤3：把这个结点的所有后继结点的入度减去 1，如果发现入度为 0 ，就马上添加到队列中
for successor in adj[top]:
in_degrees[successor] -= 1
if in_degrees[successor] == 0:
queue.append(successor)
return counter == numCourses
思路2：构建逆邻接表，实现深度优先遍历。思路其实也很简单，其实就是检测这个有向图中有没有环，只要存在环，课程就不能完成。
第 1 步：构造逆邻接表；
第 2 步：递归处理每一个还没有被访问的结点；核心思想是：对于一个顶点 vertex 来说，我们先输出了指向它的所有顶点，然后再输出自己，就是这么简单。
第 3 步：如果这个顶点没有被遍历过，就递归遍历它，把所有指向它的结点都输出了，再输出自己。
注意：这个深度优先遍历得通过逆邻接表实现，当访问一个结点的时候，应该递归访问它的前驱结点，直至前驱结点没有前驱结点为止。
Python 代码：
# 207. 课程表
# 现在你总共有 n 门课需要选，记为 0 到 n-1。
# 在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
# 给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
class Solution(object):
# 这里使用逆邻接表
def canFinish(self, numCourses, prerequisites):
"""
:type numCourses: int 课程门数
:type prerequisites: List[List[int]] 课程与课程之间的关系
:rtype: bool
"""
# 课程的长度
clen = len(prerequisites)
if clen == 0:
# 没有课程，当然可以完成课程的学习
return True
# 深度优先遍历，判断结点是否访问过
# 这里要设置 3 个状态
# 0 就对应 False ，表示结点没有访问过
# 1 就对应 True ，表示结点已经访问过，在深度优先遍历结束以后才置为 1
# 2 表示当前正在遍历的结点，如果在深度优先遍历的过程中，
# 有遇到状态为 2 的结点，就表示这个图中存在环
visited = [0 for _ in range(numCourses)]
# 逆邻接表，存的是每个结点的前驱结点的集合
# 想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
# 1 在前，0 在后
inverse_adj = [set() for _ in range(numCourses)]
for second, first in prerequisites:
inverse_adj[second].add(first)
for i in range(numCourses):
# 在遍历的过程中，如果发现有环，就退出
if self.__dfs(i, inverse_adj, visited):
return False
return True
def __dfs(self, vertex, inverse_adj, visited):
"""
注意：这个递归方法的返回值是返回是否有环
:param vertex: 结点的索引
:param inverse_adj: 逆邻接表，记录的是当前结点的前驱结点的集合
:param visited: 记录了结点是否被访问过，2 表示当前正在 DFS 这个结点
:return: 是否有环
"""
# 2 表示这个结点正在访问
if visited[vertex] == 2:
# 表示遇到环
return True
if visited[vertex] == 1:
return False
visited[vertex] = 2
for precursor in inverse_adj[vertex]:
# 如果有环，就返回 True 表示有环
if self.__dfs(precursor, inverse_adj, visited):
return True
# 1 表示访问结束
# 先把 vertex 这个结点的所有前驱结点都输出之后，再输出自己
visited[vertex] = 1
return False
这两种思路都可以完成 LeetCode 第 210 题。
LeetCode 第 210 题：课程表 II
传送门：210. 课程表 II。
现在你总共有 n 门课需要选，记为
0到n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们:
[0,1]给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]] 输出: [0,1] 解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]] 输出: [0,1,2,3] or [0,2,1,3] 解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。说明:
- 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
提示:
- 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
- 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
- 拓扑排序也可以通过 BFS 完成。
思路1：拓扑排序。
Python 代码：
class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int 课程门数
:type prerequisites: List[List[int]] 课程与课程之间的关系
:rtype: bool
"""
# 课程的长度
clen = len(prerequisites)
if clen == 0:
# 没有课程，当然可以完成课程的学习
return [i for i in range(numCourses)]
# 入度数组，一开始全部为 0
in_degrees = [0 for _ in range(numCourses)]
# 邻接表
adj = [set() for _ in range(numCourses)]
# 想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
# 1 -> 0，这里要注意：不要弄反了
for second, first in prerequisites:
in_degrees[second] += 1
adj[first].add(second)
# print("in_degrees", in_degrees)
# 首先遍历一遍，把所有入度为 0 的结点加入队列
res = []
queue = []
for i in range(numCourses):
if in_degrees[i] == 0:
queue.append(i)
while queue:
top = queue.pop(0)
res.append(top)
for successor in adj[top]:
in_degrees[successor] -= 1
if in_degrees[successor] == 0:
queue.append(successor)
if len(res) != numCourses:
return []
return res
思路2：基于逆邻接表的深度优先遍历。
Python 代码：
class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int 课程门数
:type prerequisites: List[List[int]] 课程与课程之间的关系
:rtype: bool
"""
# 课程的长度
clen = len(prerequisites)
if clen == 0:
# 没有课程，当然可以完成课程的学习
return [i for i in range(numCourses)]
# 逆邻接表
inverse_adj = [set() for _ in range(numCourses)]
# 想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
# 1 -> 0，这里要注意：不要弄反了
for second, first in prerequisites:
inverse_adj[second].add(first)
visited = [0 for _ in range(numCourses)]
# print("in_degrees", in_degrees)
# 首先遍历一遍，把所有入度为 0 的结点加入队列
res = []
for i in range(numCourses):
if self.__dfs(i,inverse_adj, visited, res):
return []
return res
def __dfs(self, vertex, inverse_adj, visited, res):
"""
注意：这个递归方法的返回值是返回是否有环
:param vertex: 结点的索引
:param inverse_adj: 逆邻接表，记录的是当前结点的前驱结点的集合
:param visited: 记录了结点是否被访问过，2 表示当前正在 DFS 这个结点
:return: 是否有环
"""
# 2 表示这个结点正在访问
if visited[vertex] == 2:
# DFS 的时候如果遇到一样的结点，就表示图中有环，课程任务便不能完成
return True
if visited[vertex] == 1:
return False
# 表示正在访问这个结点
visited[vertex] = 2
# 递归访问前驱结点
for precursor in inverse_adj[vertex]:
# 如果没有环，就返回 False，
# 执行以后，逆拓扑序列就存在 res 中
if self.__dfs(precursor, inverse_adj, visited, res):
return True
# 能走到这里，说明所有的前驱结点都访问完了，所以可以输出了
# 并且将这个结点状态置为 1
visited[vertex] = 1
# 先把 vertex 这个结点的所有前驱结点都输出之后，再输出自己
res.append(vertex)
# 最后不要忘记返回 False 表示无环
return False
（本节完）
二、关键路径
重要的概念：（1）关键路径（理解为什么是权值最大的）（2）关键活动
参考资料：
1、《大话数据结构》
2、极客时间《算法与数据结构之美》，作者：王争
3、自己以前写的题解：
LeetCode 题解之 207. Course Schedule（拓扑排序模板题 1 ）
https://blog.csdn.net/lw_power/article/details/80795288
LeetCode 题解之 210. Course Schedule II（拓扑排序模板题 2 ）
https://blog.csdn.net/lw_power/article/details/80795355
4、深入理解拓扑排序（Topological sort)
https://www.jianshu.com/p/3347f54a3187
拓扑排序和 dfs
解决一个有依赖的工程是否能够完成。
拓扑排序和关键路径问题。
1、AOV 网：与顶点相关。图中不允许有回路。
2、AOE 网：与边相关。整个任务是否能够完成取决于最长的关键路径。
使用拓扑排序判断 DAG 是否有回路。
LeetCode 第 207 题：课程表
参考资料：https://blog.csdn.net/ljiabin/article/details/45846837
拓扑排序的原理：在一个有向图中，每次找到一个没有前驱节点的结点（也就是入度为 0 的结点），然后把它指向的结点的边都去掉，==重复这个过程（BFS）==，直到所有结点已被找到，或者没有符合条件的节点（如果图中有环存在）。
回顾一下图的三种表示方式：
1、边表示法（即题目中表示方法）；
2、邻接表法；
3、邻接矩阵表示法。
用邻接表存储图比较方便寻找入度为 的节点。
拓扑排序以及拓扑排序的伪代码：
拓扑排序的写法：
https://blog.csdn.net/qq508618087/article/details/50748965
LeetCode 第 210 题：课程表 II
要求返回一种拓扑排序的结果。
参考资料：http://zxi.mytechroad.com/blog/graph/leetcode-210-course-schedule-ii/
dfs 的做法：Java 的写法以被指向的课程作为键。
注意：下面这个 dfs 的方法，有向图的表示以先行课程作为键。
