问题背景：
工作流程图到工作次序的排序的算法，称为拓扑排序算法
问题解决思路：
- 将工作次序变为图，图的顶点代表每项任务，顶点之间的有向线段代表依赖关系
- 调用DFS算法，得出每项工作的起始时间与结束时间
- 按结束时间从大到小排序，输出这个次序下的顶点列表
问题算法：
class DFSGraph(Graph):
def __init__(self):
super().__init__()
self.time = 0
def dfs(self):
# 初始化每一个顶点
for aVertex in self:
aVertex.setColor('white')
aVertex.setPred(-1)
# 开始探索顶点
for aVertex in self:
if aVertex.getColor() == 'white':
self.dfsvisit(aVertex)
def dfsvisit(self, startVertex):
startVertex.setColor('gray')
self.time += 1
# 设置起始时间
startVertex.setDiscovery(self.time)
for nextVertex in startVertex.getConnecctions():
if nextVertex.getColor() == 'white':
nextVertex.setPred(startVertex)
self.dfsvisit(nextVertex)
startVertex.setColor('black')
self.time += 1
# 设置结束时间
startVertex.setFinish(self.time)
image.png
附一道拓扑排序的题目：
Leetcode 207：
课程表
现在你总共有n门课需要选，记为0到n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
如[[0,1],[1,0]]便无法完成
'''
做这题之前需要明确下列概念：
1. 入度的概念： 表示该顶点箭头被指向的数目：如a→b，其中a入度为0，b入度为1；出度的概念则相反，表示弧尾。
2. 形成环的概念，如果拓扑排序中，当去掉所有入度为零的节点后，如果有两个及两个以上节点入度不为零，则存在环。
遍历列表，统计每个节点的入度和接邻节点，当去掉一个入度为零的节点时，相应的接邻节点的入度减一，循环，直到列表为空或者全不为零。此种情况下不成环
3. 判断是否有环是此题的关键
'''
def canFinish(n, pre):
# 各顶点入度数，列表第N个数字代表第N个顶点的入度数
in_degree = [0 for i in range(n)]
# 表示第N个顶点所指向数，由顶点出发（出度），集合中的顶点表示被指(入度）
adj = [set() for i in range(n)]
for indegree, outdegree in pre:
in_degree[indegree] += 1
adj[outdegree].add(indegree)
# 将顶点入度数为0的顶点编号放入列队
queue = []
for i in range(n):
if in_degree[i] == 0:
queue.append(i)
# 把入度为0的结点的所有后继结点的入度减去1，如果发现入度为0 ，就把这个后继结点添加到队列中
count = 0
while queue:
top = queue.pop(0)
count += 1
for successor in adj[top]:
in_degree[successor] -= 1
if in_degree[successor] == 0:
queue.append(successor)
return count == n
n = int(input())
pre = eval(input())
print(canFinish(n, pre))
