我最近一直在练习图形问题。
https://leetcode.com/problems/course-schedule-ii/
https://leetcode.com/problems/alien-dictionary/
我目前检测循环的方法是使用两个哈希集。一个用于访问节点，一个用于完全访问的节点。然后我用DFS遍历将结果推送到堆栈中。
如果我访问了当前位于访问集中的节点，那么它就是一个循环。
代码非常冗长，而且长度很长。
有人能解释一下我如何使用更标准的顶部排序算法(Kahn’s(来检测循环并生成顶部排序序列吗？
我只想让我的方法退出或设置一些全局变量，标记已经检测到循环。
非常感谢。
Khan循环检测算法(综述(
-
步骤1：计算度数：首先，我们为每个节点的度数创建一个查找。在这个特殊的Leetcode问题中，每个节点都有一个唯一的整数标识符，因此我们可以简单地使用
indegree[i]告诉我们节点i的阶数的列表来存储所有的阶数值 -
步骤2：跟踪所有度数为零的节点：如果一个节点的度数为零，则意味着这是我们现在可以学习的课程。它不依赖于其他课程。我们创建了一个由所有这些节点组成的队列
q，这些节点的度为零。在Khan算法的任何步骤中，如果一个节点在q中，则保证它是"q"；安全地选修这门课程"；因为它不依赖于任何课程；我们还没有采取"> -
步骤3：删除节点和边，然后重复：我们从队列
q中选择一个特殊的安全过程x，并在概念上将所有内容视为从图g中删除了节点x及其所有传出边。在实践中，我们不需要更新图g，对于Khan的算法，只更新其邻居的in-degree值就足以反映该节点不再存在
这一步基本上就像一个人参加并通过了课程x，现在我们想更新其他课程的依赖关系以表明他们不再需要担心CCD_ 11 -
步骤4：重复：当我们从
x中去除这些边时，我们正在降低x的邻居的入度；这可以引入更多具有零度的节点。在该步骤中，如果更多节点的入度变为零，则将它们添加到q。我们重复步骤3来处理这些节点。每次我们从q中移除一个节点时，我们都会将其添加到最终拓扑排序列表result中 -
步骤5。使用Khan算法检测循环：如果图中存在循环，则
result将不包括图中的所有节点，result将仅返回部分节点。要检查是否存在循环，只需要检查result的长度是否等于图中的节点数n。- 为什么这样做：假设图中有一个循环：x1->x2->->；xn->x1，则这些节点中没有一个将出现在列表中，因为在Khan的算法期间它们的进入度将不会达到0。循环中的每个节点xi不能被放入队列
q中，因为总是存在具有从x_(i-1(到xi的边缘的一些其他前代节点x_
- 为什么这样做：假设图中有一个循环：x1->x2->->；xn->x1，则这些节点中没有一个将出现在列表中，因为在Khan的算法期间它们的进入度将不会达到0。循环中的每个节点xi不能被放入队列
Python3:中Leetcode课程时间表ii的完整解决方案
from collections import defaultdict
def build_graph(edges, n):
g = defaultdict(list)
for i in range(n):
g[i] = []
for a, b in edges:
g[b].append(a)
return g
def topsort(g, n):
# -- Step 1 --
indeg = [0] * n
for u in g:
for v in g[u]:
indeg[v] += 1
# -- Step 2 --
q = []
for i in range(n):
if indeg[i] == 0:
q.append(i)
# -- Step 3 and 4 --
result = []
while q:
x = q.pop()
result.append(x)
for y in g[x]:
indeg[y] -= 1
if indeg[y] == 0:
q.append(y)
return result
def courses(n, edges):
g = build_graph(edges, n)
ordering = topsort(g, n)
# -- Step 5 --
has_cycle = len(ordering) < n
return [] if has_cycle else ordering