使用卡恩算法检测拓扑排序中的循环（入度/出度）

Question

最近一直在练习图表题。

https://leetcode.com/problems/course-schedule-ii/

https://leetcode.com/problems/alien-dictionary/

我当前检测循环的方法是使用两个哈希集。一种用于访问节点，一种用于完全访问节点。然后我通过 DFS 遍历将结果推送到堆栈上。

如果我访问过当前位于访问集中的节点，那么这就是一个循环。

代码相当冗长，而且长度也很长。

谁能解释一下我如何使用更标准的顶排序算法（卡恩的）来检测循环并生成顶排序序列？

我只是想让我的方法退出或设置一些全局变量来标记已检测到循环。

非常感谢。

Answer 1

Khan 的循环检测算法（摘要）

• 步骤 1：计算入度：首先，我们为每个节点的入度创建计算查找。在这个特定的 Leetcode 问题中，每个节点都有一个唯一的整数标识符，因此我们可以使用一个列表来简单地存储所有入度值，其中indegree[i]告诉我们节点 的入度i。
• 步骤 2：跟踪所有入度为零的节点：如果一个节点的入度为零，则意味着它是我们现在可以采取的课程。它没有依赖其他课程。我们创建一个q由所有这些入度为零的节点组成的队列。在 Khan 算法的任何一步，如果一个节点位于 q 中，则可以保证“学习这门课程是安全的”，因为它不依赖于任何“我们尚未学习的课程”。
• 步骤 3：删除节点和边，然后重复x：我们从队列中取出这些特殊的安全课程之一q，并从概念上将所有内容视为我们已从x图中删除了该节点及其所有传出边g。在实践中，我们不需要更新图g，对于 Khan 算法来说，只需更新in-degree其邻居的值以反映该节点不再存在就足够了。
  这一步基本上就好像一个人参加并通过了课程考试x，现在我们要更新其他课程依赖项以表明他们不再需要担心x。
• 步骤 4：重复：当我们从 中删除这些边时，我们正在减少 的邻居x的入度；x这可以引入更多入度为零的节点。在此步骤中，如果有更多节点的入度变为零，则将它们添加到q。我们重复步骤3来处理这些节点。每次我们从中删除一个节点时，q我们都会将其添加到最终的拓扑排序列表中result。
• 步骤 5. 使用 Khan 算法检测循环：如果图中存在循环，则result不会包含图中的所有节点，只会result返回部分节点。要检查是否存在环，只需检查 的长度是否result等于图中的节点数n。
  • 为什么这有效？：假设图中存在一个循环：x1 -> x2 -> ... -> xn -> x1，那么这些节点都不会出现在列表中，因为在 Khan 算法中它们的入度不会达到 0。循环中的每个节点 xi 都无法放入队列中q，因为总有一些其他前驱节点 x_(i-1) 具有从 x_(i-1) 到 xi 的边，从而阻止这种情况发生。

Python 3 中Leetcode course-schedule-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