1.图环路检测
- 列表法。可以通过列表list记录己走过的路径，判断当前节点是否在已走过路径中
-
字典法。可以通过一个字典记录所有节点的状态。要访问某节点时，先查字典看该节点是否已被访问
字典法相对更优，墙裂推荐
2.有向无环图的拓扑排序
2.1有向无环图
有向无环图，常常被用来表示若干事件之间的前后依赖关系，用来规划任务的排期和调度
2.2什么是拓扑排序
给定一个包含 n 个节点的有向图 G，我们给出它的节点编号的一种排列，如果满足：
对于图 G 中的任意一条有向边 (u, v)，u 在排列中都出现在 v 的前面
那么称该排列是图 G 的「拓扑排序」
【例如】
如图所示，排列ABFCDE为该图的一个拓扑排序，其中F的位置可以随意改变。拓扑排序是满足各个节点前后依赖关系的一种管理组织方式
2.3如何求解拓扑排序
求解拓扑排序，必须满足图中每个结点必须出现在其所有邻接结点的前面
对于图，通用的解法包括2种
- DFS方法
2.3.1 DFS方法
DFS方法（深度优先搜索）只会访问每个顶点一次，又分为前中后序，这里肯定不用中序。前序和后序，选哪个？
上面提到，必须满足图中每个结点必须出现在其所有邻接结点的前面，这是啥？我们反过来看，让每个结点必须出现在其所有邻接结点的后面，这不就是后序遍历吗！我们把后序遍历的结果翻转过来，就是所求的拓扑排序
总结：一副有向无环图的拓扑排序即为所有顶点的逆后序排列
因此，在DFS后序遍历实现拓扑排序时，选用栈来保存顶点序列；保证在某顶点入栈前，其所有邻接点已入栈。假设我们当前搜索到了节点 u，如果它的所有邻节点都已经入栈，我们就可以把 u 入栈
DFS方法可视化：https://www.cs.usfca.edu/~galles/visualization/TopoSortDFS.html
-
BFS方法
将入度为0的点称为顶点。顶点不会有任何入边，即没有任何前置依赖，我们可以直接选择加入结果集中。当我们将一个顶点加入答案中后，就可以马上移除它的所有出边，代表着它的相邻节点的该前置依赖解除。对剩下的图结构，重复上面的操作即可
3.例题
leetcode#### 210. 课程表 II
给2个参数，
numCourses，表示课程（图结点）数量
prerequisites, 如[[1,0],[2,0],[3,1],[3,2]]。二维数组中的每个元素可以表示为一条【有向边】，[1,0] 表示 0->1
求这个图的一个拓扑排序
思路：
1.DFS方法。使用【字典法】标记节点状态查看是否有环，使用【逆后序遍历】求拓扑排序
class Solution:
def __init__(self):
self.visited = set()
self.stack = list()
self.has_circle = False
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# 如果数组有环，则不可能完成
# numCourses，表示课程（结点）数量
# prerequisites, [[1,0],[2,0],[3,1],[3,2]]。二维数组中的每个元素可以表示为一条【有向边】
# [1,0] 表示 0->1
# 创建边字典, edges[i]表示起点为i的有向边，如{1:[2,3,4]}表示1的邻结点是2/3/4
edges = dict()
for i in range(numCourses):
edges[i] = []
# 填充边字典
for bian in prerequisites:
edges[bian[1]].append(bian[0])
# 初始化状态字典
state_dict = dict()
for i in range(numCourses):
state_dict[i] = 0
for course in edges:
if not self.has_circle:
self.DFS(course, edges, state_dict)
else:
return []
return self.stack[::-1]
# 后序遍历
def DFS(self, node, edges, state_dict):
# 0表示未访问，1表示访问中，2表示访问完毕
# 该节点未访问
if state_dict[node] == 0:
# 修改为访问中
state_dict[node] = 1
# 依次访问邻接节点
for neibor in edges[node]:
# 有环
if state_dict[neibor] == 1:
self.has_circle = True
return
elif state_dict[neibor] == 0:
self.DFS(neibor, edges, state_dict)
# 注意，在每次循环最后检查是否有环
if self.has_circle:
return
# 邻接节点都搜索入栈完毕后，自己入栈
self.stack.append(node)
state_dict[node] = 2
2.使用BFS方法
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# 如果数组有环，则不可能完成
# numCourses，表示课程（结点）数量
# prerequisites, [[1,0],[2,0],[3,1],[3,2]]。二维数组中的每个元素可以表示为一条【有向边】
# [1,0] 表示 0->1
# 入度字典
indegree = dict()
for i in range(numCourses):
indegree[i] = 0
# 填充入度字典
for edge in prerequisites:
indegree[edge[0]] += 1
# 邻接字典
neibor_dict = dict()
for i in range(numCourses):
neibor_dict[i] = []
# 填充邻接点字典
for edge in prerequisites:
neibor_dict[edge[1]].append(edge[0])
# 根据入度，求顶点
head_nodes = list()
for node in indegree:
if indegree[node] == 0:
head_nodes.append(node)
res = []
# 当图有入度为0的顶点存在时
while head_nodes:
head = head_nodes.pop()
res.append(head)
# head邻接点的入度都-1
for nb in neibor_dict[head]:
indegree[nb] -= 1
if indegree[nb] == 0:
head_nodes.append(nb)
# 通过比较res的长度和节点数量来判断是否有环
return res if len(res) == numCourses else []
