拓扑排序
求拓扑排序
第一种方法 利用入度的队列
拓扑排序也可以被看成是广度优先搜索的一种情况：我们先遍历一遍所有节点，把入度为0
的节点（即没有前置课程要求）放在队列中。在每次从队列中获得节点时，我们将该节点放在目
前排序的末尾，并且把它指向的课程的入度各减1；如果在这个过程中有课程的所有前置必修课
都已修完（即入度为0），我们把这个节点加入队列中。当队列的节点都被处理完时，说明所有的
节点都已排好序，或因图中存在循环而无法上完所有课程。
res = []
res = [set of node which indegree = 0]
while len(res) > 0:
handle res.pop.(all next node)
indegree --
if node.indegree == 0:
append to res;
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
graph = [[] for _ in range(numCourses)]
indegree = [0 for _ in range(numCourses)]
for v, u in prerequisites:
graph[u].append(v)
indegree[v] += 1
res = []
q = deque()
for u in range(numCourses):
if indegree[u] == 0:
q.append(u)
while len(q) > 0:
u = q.popleft()
res.append(u)
for v in graph[u]:
indegree[v] -= 1
if indegree[v] == 0:
q.append(v)
# print(res)
# print(indegree)
for iter in indegree:
if iter > 0:
return []
return res
第二种方法 dfs逆序
for node in nodes:
if not visit(node):
dfs(node)
dfs:
dfs every next node;
res.append(curr_node)
下面这种只用visit标记是无法区分有环存在的情况的, 需要先判断有没有环。判断有无环可以使用dfs, 因为是有向的，因此无法使用Uf， dfs也不能用visit，要区分未访问、正在访问中、访问完成，也就是白灰黑那三种颜色。可以判断有无环和逆序dfs融合起来，就是标记
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
res = []
eWhite, eGray, eBlack = 0, 1, 2
color = [eWhite for _ in range(numCourses)]
graph = [[] for _ in range(numCourses)]
for prerequisite in prerequisites:
v, u = prerequisite[0], prerequisite[1]
graph[u].append(v)
isPossible = True
def dfs(u):
nonlocal isPossible
if not isPossible:
return
if color[u] != eWhite:
return
nonlocal res
color[u] = eGray
for v in graph[u]:
c = color[v]
if c == eGray:
isPossible = False
return
elif c == eWhite:
dfs(v)
color[u] = eBlack
res.append(u)
for u in range(numCourses):
if color[u] == eWhite:
dfs(u)
return res[::-1] if isPossible else []
应用：
- 求安排次序
- 210. Course Schedule II (Medium) 求课程安排顺序，拓扑排序，如果是dfs，记得要判断是否有环, 通过white, gray, black判断。
- 求拓扑排序的高度，就是层次多源BFS
310. 最小高度树 可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
题解：拓扑排序的bfs, 最开始是出入度为1的节点，然后每次扩增，影响的节点的出入度减一，如果出入度变成1，加到遍历队列里，每次遍历都是层次遍历，最后的那层就是最终的结果。
329. 矩阵中的最长递增路径 找出其中 最长递增路径 的长度。 按拓扑排序层次遍历，最开始是出度为0，因为是递增，保证了无环，如果可能成环，加个visit记录下是否访问过。
求出拓扑次序后，再DP?
拓扑排序可以按入度拓扑排序，也可以按出度拓扑排序。
- 比如按出度的拓扑排序： 802. 找到最终的安全状态 对于一个起始节点，如果从该节点出发，无论每一步选择沿哪条有向边行走，最后必然在有限步内到达终点，则将该起始节点称作是 安全 的。返回一个由图中所有安全的起始节点组成的数组作为答案
拓扑排序判断是否有环，不存在无前驱的顶点时，就是找不到开始的头了，剩下的就是个环。当前图中有节点未访问同时不存在无前驱的顶点时，后一种情况说明有向图中必然存在环。
判断是否有环
dfs+visit数组是不可以的，比如(1,2),(2,1),(2,3), 1和2成环，当先遍历3 时，visit[3]=True, 遍历到2时如果检查visit数组这种判断是错误的。因此要用黑灰白三种颜色来判断。
1、拓扑排序
1.1、无向图
使用拓扑排序可以判断一个无向图中是否存在环，具体步骤如下：
- 求出图中所有结点的度。
- 将所有度 <= 1 的结点入队。（独立结点的度为 0）
- 当队列不空时，弹出队首元素，把与队首元素相邻节点的度减一。如果相邻节点的度变为一，则将相邻结点入队。
- 循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过，无环；反之，则有环。
1.2、有向图
使用拓扑排序判断无向图和有向图中是否存在环的区别在于：
- 在判断无向图中是否存在环时，是将所有度 <= 1 的结点入队；
- 在判断有向图中是否存在环时，是将所有入度 = 0 的结点入队。
# graph用edges表示 如果有环 返回TRUE
def is_cyclic_1(self, graph, n):
# key=parant value=childs
pa_child=defaultdict(list)
in_degree=defaultdict(int)
for u, v in graph:
pa_child[u].append(v)
in_degree[v]+=1
# 找到当前入度为0的点
que_zero=[]
for i in range(1,n+1):
if in_degree[i]==0: que_zero.append(i)
# 拓扑排序
# 1.弹出当前入度为0的节点 2.弹出节点的子节点入度-1 3.如-1后入度=0则加入que_zero
cnt=0 # 用来记录拓扑排序遍历过程中弹出的点的数目 如果cnt最终=n 则无环
while que_zero:
node=que_zero.pop(0)
cnt+=1
#print('node={} cnt={}'.format(node,cnt))
for ch in pa_child[node]:
in_degree[ch]-=1
if in_degree[ch]==0:
que_zero.append(ch)
return cnt!=n
2、DFS
使用 DFS 可以判断一个无向图和有向中是否存在环。深度优先遍历图，如果在遍历的过程中，发现某个结点有一条边指向已访问过的结点，并且这个已访问过的结点不是上一步访问的结点，则表示存在环。
我们不能仅仅使用一个 bool 数组来表示结点是否访问过。规定每个结点都拥有三种状态，白、灰、黑。开始时所有结点都是白色，当访问过某个结点后，该结点变为灰色，当该结点的所有邻接点都访问完，该节点变为黑色。
那么我们的算法可以表示为：如果在遍历的过程中，发现某个结点有一条边指向灰色节点，并且这个灰色结点不是上一步访问的结点，那么存在环。
代码可参考拓扑排序中判断是否有环逻辑。
3、Union-Find Set
我们可以使用并查集来判断一个图中是否存在环：
对于无向图来说，在遍历边（u-v）时，如果结点 u 和结点 v 的“父亲”相同，那么结点 u 和结点 v 在同一个环中。
对于有向图来说，在遍历边（u->v）时，如果结点 u 的“父亲”是结点 v，那么结点 u 和结点 v 在同一个环中。
题目
- 685. 冗余连接 II 返回一条能删除的边，使得剩下的图是有
n个节点的有根树。先看有没有节点两个父亲，如果有，肯定就在这两条边内，如果没有，就是有环，并查集找最后一个引起环的边。