拓扑排序

对一个有向无环图 (Directed Acyclic Graph 简称 DAG) G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v，若边 (u,v) ∈ E(G)，则 u 在线性序列中出现在 v 之前。

拓扑排序对应施工的流程图具有特别重要的作用，它可以决定哪些子工程必须要先执行，哪些子工程要在某些工程执行后才可以执行。为了形象地反映出整个工程中各个子工程（活动）之间的先后关系，可用一个有向图来表示，图中的顶点代表活动（子工程），图中的有向边代表活动的先后关系，即有向边的起点的活动是终点活动的前序活动，只有当起点活动完成之后，其终点活动才能进行。通常，我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网（Activity On Vertex network），简称 AOV 网。
一个 AOV 网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行（对于数据流来说就是死循环）。在 AOV 网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列 (Topological order)，由 AOV 网构造拓扑序列的过程叫做拓扑排序 (Topological sorting)。AOV 网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。

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

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

拓扑排序算法

任何无回路的顶点活动网（AOV网）G 都可以做出拓扑序列：

从 G 中选出一个入度为 0 的顶点作为序列的下一顶点。
从 G 网中删除所选顶点及其所有的出边。

反复执行上面两个步骤，知道已经选出了图中的所有顶点，或者再也找不到入度为非0的顶点时算法结束。
如果剩下入度非0的顶点，就说明N中有回路，不存在拓扑排序。
存在回路，意味着某些活动的开始要以其自己的完成作为先决条件，这种现象成为活动之间的死锁。一种常见的顶点活动网实例是大学课程的先修课程。课程知识有前后练习，一门课可能以其他课程的知识为基础，学生想选修这门课程时，要看是否已修过所有先修课程。如果存在一个回路的话，那就意味着进入了一个循环，那么该同学就毕不了业了。

因此可以说拓扑排序算法是为了做出满足制约关系的工作安排。
下面我们操作一个实例，如下图是一个有向无环图：

from collections import defaultdict 
 
class Graph: 
    def __init__(self,vertices): 
        self.graph = defaultdict(list) 
        self.V = vertices
  
    def addEdge(self,u,v): 
        self.graph[u].append(v) 
  
    def topologicalSortUtil(self,v,visited,stack): 
  
        visited[v] = True
       
        for i in self.graph[v]: 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        stack.insert(0,v) 
  
    def topologicalSort(self): 
        visited = [False]*self.V 
        stack =[] 
  
        for i in range(self.V): 
            if visited[i] == False: 
                self.topologicalSortUtil(i,visited,stack) 
  
        print (stack) 
  
g = Graph(6) 
g.addEdge(5, 2); 
g.addEdge(5, 0); 
g.addEdge(4, 0); 
g.addEdge(4, 1); 
g.addEdge(2, 3); 
g.addEdge(3, 1); 
print(g.graph)
# defaultdict(<class 'list'>, {5: [2, 0], 4: [0, 1], 2: [3], 3: [1]})

print ("拓扑排序结果：")
g.topologicalSort()
# [5, 4, 2, 3, 1, 0]

拓扑排序，以及什么是拓扑排序？
根据上面的分析，我们发现，最简单的安全点就是无路可走的终点（也即出度为 0 的节点）。而拓展到一般情况，如果一个节点所指向的点均为安全点，那么这个点也是安全点。如何提取出这些安全点呢？我们需要避开图中的环路，提到环路，我们会自然地想到拓扑排序，我们试试拓扑排序能否完成这道题。
拓扑排序：从给定的图的所有边中「提取出该图的某一个拓扑序列」的过程，拓扑序列是一条满足图中有向边前后关系的序列，任一有向边起点在序列中一定早于终点出现。如果图中有环，则无法提取出拓扑序列。所以拓扑排序的一个重要应用是在给定的有向图中判定是否存在环路。

拓扑排序是找到图中入度为 00 的节点，以及仅由入度为 00 节点所指向的节点。，而本题是找到图中**出度为 00 的节点，以及仅指向出度为 00 节点的节点。**刚好是相反的情况，所以，我们将题目给定的有向图变为反图（也即有向边的起点、终点互换），那么所有安全点便可以通过拓扑排序来求解了。

接下来，我们简述一下拓扑排序的思想，并证明一下我们算法的有效性：
（1）将所有入度为 00 的点（原图中出度为 00 的点，也就是终点，最简单的安全点）加入队列。
（2）每次循环访问位于队头的节点（安全点）；
（3）遍历以该节点为起点的所有有向边，将其从图中去掉，也即将将该点指向的所有点的入度减一。
（4）若某被指向点入度变为 00（意味着指向这个点的点均曾经被加入过队列，说明均为安全点），则将此点入队
（5）重复步骤（2）、（3）、（4）直至队空。

拓扑排序的例子（帮助大家理解拓扑排序，如已掌握可跳过）
Tips：下面的图示和说明可以帮大家更好的理解拓扑排序的过程

在这里插入图片描述

首先，给定图中仅有节点 11 入度为 00，我们将其加入队列。

我们将节点 11 为起点的有向边均删掉（在图中变为橙色），更新这些有向边终点的入度，节点 2,3,42,3,4 入度均减一，变为 [0,1,1][0,1,1]。由于节点 22 的入度变为了 00，我们将其加入队列。

我们将节点 22 为起点的有向边均删掉，更新这些有向边终点的入度，节点 33 入度减一，变为 [0][0]。我们将其加入队列。

我们将节点 33 为起点的有向边均删掉，更新这些有向边终点的入度，节点 4,54,5 入度均减一，变为 [0,1][0,1]。由于节点 44 的入度变为了 00，我们将其加入队列。

我们将节点 44 为起点的有向边均删掉，更新这些有向边终点的入度，节点 55 入度减一，变为 [0][0]。由于节点 55 的入度变为了 00，我们将其加入队列。

我们将节点 55 为起点的有向边均删掉，此时全图已经遍历完毕，没有新的节点被加入队列。

队列为空，拓扑排序结束。

拓扑排序

设点数为 n，边数为 m。

在图论中，一个有向无环图必然存在至少一个拓扑序与之对应，反之亦然。

简单来说，就是将图中的所有节点展开成一维序列，对于序列中任意的节点 (u, v)，如果在序列中 u 在 v 的前面，则说明在图中存在从 u 出发达到 v 的通路，即 u 排在 v 的前面。反之亦然。

「入度」和「出度」的概念：

入度：有多少条边直接指向该节点；
出度：由该节点指出边的有多少条。

BFS 方式：

起始时，将所有入度为 0 的节点进行入队（入度为 0，说明没有边指向这些节点，将它们放到拓扑排序的首部，不会违反拓扑序定义）；
从队列中进行节点出队操作，出队序列就是对应我们输出的拓扑序。
对于当前弹出的节点 x，遍历 x 的所有出度，即遍历所有由 x 直接指向的节点 y，对 y 做入度减一操作（因为 x 节点已经从队列中弹出，被添加到拓扑序中，等价于从 x 节点从有向图中被移除，相应的由 x 发出的边也应当被删除，带来的影响是与 x 相连的节点 y 的入度减一）；
对 y 进行入度减一之后，检查 y 的入度是否为 0，如果为 0 则将 y 入队（当 y 的入度为 0，说明有向图中在 y 前面的所有的节点均被添加到拓扑序中，此时 y 可以作为拓扑序的某个片段的首部被添加，而不是违反拓扑序的定义）；
循环流程 2、3 直到队列为空。

证明
上述 BFS 方法能够求得「某个有向无环图的拓扑序」的前提是：我们必然能够找到（至少）一个「入度为 00 的点」，在起始时将其入队。

这可以使用反证法进行证明：假设有向无环图的拓扑序不存在入度为 00 的点。

那么从图中的任意节点 xx 进行出发，沿着边进行反向检索，由于不存在入度为 00 的节点，因此每个点都能够找到上一个节点。

当我们找到一条长度为 n + 1n+1 的反向路径时，由于我们图中只有 nn 个节点，因此必然有至少一个节点在该路径中重复出现，即该反向路径中存在环，与我们「有向无环图」的起始条件冲突。

得证「有向无环图的拓扑序」必然存在（至少）一个「入度为 00 的点」。

即按照上述的 BFS 方法，我们能够按照流程迭代下去，直到将有向无环图的所有节点从队列中弹出。

反之，如果一个图不是「有向无环图」的话，我们是无法将所有节点入队的，因此能够通过入队节点数量是否为 nn 来判断是否为有向无环图。

反向图 + 拓扑排序
回到本题，根据题目对「安全节点」的定义，我们知道如果一个节点无法进入「环」的话则是安全的，否则是不安全的。

另外我们发现，如果想要判断某个节点数 xx 是否安全，起始时将 xx 进行入队，并跑一遍拓扑排序是不足够的。

因为我们无法事先确保 xx 满足入度为 00 的要求，所以当我们处理到与 xx 相连的节点 yy 时，可能会存在 yy 节点入度无法减到 00 的情况，即我们无法输出真实拓扑序中，从 xx 节点开始到结尾的完整部分。

但是根据我们「证明」部分的启发，我们可以将所有边进行反向，这时候「入度」和「出度」翻转了。

对于那些反向图中「入度」为 00 的点集 xx，其实就是原图中「出度」为 00 的节点，它们「出度」为 00，根本没指向任何节点，必然无法进入环，是安全的；同时由它们在反向图中指向的节点（在原图中只指向它们的节点），必然也是无法进入环的，对应到反向图中，就是那些减去 xx 对应的入度之后，入度为 00 的节点。

因此整个过程就是将图进行反向，再跑一遍拓扑排序，如果某个节点出现在拓扑序列，说明其进入过队列，说明其入度为 00，其是安全的，其余节点则是在环内非安全节点。

另外，这里的存图方式还是使用前几天一直使用的「链式前向星」，关于几个数组的定义以及其他的存图方式，如果还是有不熟悉的小伙伴可以在这里查阅，本次不再赘述。

在这里插入图片描述