Coding Interview Prep · 课时

Kahn 算法：BFS 拓扑排序

Q: 「Kahn 算法：BFS 拓扑排序」课时是免费的吗？

是的 — 「Kahn 算法：BFS 拓扑排序」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

Q: 「Kahn 算法：BFS 拓扑排序」这节课中我会学到什么？

计算所有节点的入度，将入度为零的节点加入队列，并处理队列以生成拓扑序，同时检测环。 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

Q: 学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。

Q: 「Kahn 算法：BFS 拓扑排序」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

Q: 我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

计算所有节点的入度，将入度为零的节点加入队列，并处理队列以生成拓扑序，同时检测环。

Kahn 算法：BFS 拓扑排序 是 CoddyKit 上的免费 Coding Interview Prep 课时。这是第 1 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

什么是拓扑排序

有向无环图（DAG）的拓扑排序是一种节点排列，使得每条有向边 u → v 都表示 u 在该排列中位于 v 之前。它表示一种满足依赖关系的有效执行顺序，例如构建系统、课程安排或包管理。只有 DAG 才具有有效的拓扑排序；环会使这种排序无法实现。

卡恩算法：核心思想

卡恩算法是一种基于 BFS 的拓扑排序方法。其核心思想是：入度为 0 的节点（没有前置条件）可以首先放入排序结果。放入该节点后，将其移除，并将其邻居的入度减 1。新的零入度节点就会变得可用。重复此过程，直到所有节点都被放入结果，或者检测到环（仍有节点的入度不为 0）。

入度计算

首先建立邻接表，并计算每个节点的入度（指向该节点的边的数量）。入度为 0 的节点是起点，因为它们没有依赖关系。对于边为 [(0,1),(0,2),(1,3),(2,3)] 的图，入度为：0→0，1→1，2→1，3→2。只有节点 0 的初始入度为 0。

from collections import deque, defaultdict

def compute_in_degree(n, edges):
    in_degree = [0] * n
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    return graph, in_degree

graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind)  # [0, 1, 1, 2]

卡恩算法实现

将所有零入度节点加入队列。处理每个节点时，先将其加入结果，然后对每个邻居的入度减 1；如果某个邻居的入度变为 0，就将其加入队列。如果结果列表中的节点数少于图中的节点数，则说明存在环——某些节点始终无法出队。

from collections import deque, defaultdict

def kahn_topological_sort(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    if len(order) == n:
        return order   # valid topological sort
    return []          # cycle detected

print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))

使用卡恩算法检测环

卡恩算法提供了无需额外代价的环检测：如果 len(order) < n，则有些节点从未加入队列，因为它们的入度始终没有变为 0——这些节点属于某个环。这比维护带颜色标记的访问数组更加简洁。如果存在环，请返回空列表。

# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result)  # [] (cycle detected)

# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result)  # [0, 1, 2]

时间与空间复杂度

卡恩算法会处理每个节点一次（每个节点只出队一次），也会处理每条边一次（每条边只导致一次入度递减）。时间复杂度为：O(V + E)。空间复杂度为：邻接表和入度数组需要 O(V + E)，队列需要 O(V)。这是最优的，因为至少必须读取所有节点和边，才能生成有效的排序结果。

字典序最小的拓扑排序

使用最小堆而不是队列运行卡恩算法，可以生成字典序最小的拓扑排序。请将 deque 替换为 heapq：将 (node) 压入堆，并始终优先处理当前可用节点中最小的节点。这样可以保证在所有可能的拓扑排序中得到字典序最小的有效排序。

import heapq
from collections import defaultdict

def kahn_lex_order(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    heap = [i for i in range(n) if in_degree[i] == 0]
    heapq.heapify(heap)
    order = []
    
    while heap:
        node = heapq.heappop(heap)
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                heapq.heappush(heap, nxt)
    
    return order if len(order) == n else []

print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))

应用：课程表 I

课程表（LeetCode 207）：给定 n 门课程及其先修课程，您能否完成所有课程？请将先修关系建模为有向边，并检查是否存在有效的拓扑排序（即不存在环）。如果卡恩算法生成的排序长度为 n，则返回真；如果检测到环，则返回假。

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:   # b must be taken before a
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return count == numCourses

print(canFinish(2, [[1,0]]))       # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)

应用：课程表 II

课程表 II（LeetCode 210）：返回实际的选课顺序。与上题相同，但请返回 order 列表，而不是布尔值。如果存在环，则返回空列表。这里可以直接将卡恩算法的输出作为答案。

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return order if len(order) == numCourses else []

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

并行任务调度

一种更高级的应用是：给定具有依赖关系的任务，求出在无依赖任务可以并行运行的情况下所需的最少“轮次”。请像 BFS 的逐层遍历一样，逐层处理卡恩算法：将所有零入度节点加入队列，把当前整个队列作为一轮处理，然后将新获得执行条件的节点加入队列，作为下一轮处理。最后统计轮次数。

from collections import deque, defaultdict

def min_rounds(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    rounds = 0
    while queue:
        rounds += 1
        for _ in range(len(queue)):  # process current level
            node = queue.popleft()
            for nxt in graph[node]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    queue.append(nxt)
    return rounds

print(min_rounds(4, [(0,2),(1,2),(2,3)]))  # 3

DAG 上的拓扑排序与 DP

拓扑排序可以实现DAG 上的动态规划：按照拓扑顺序处理节点；计算某个节点的动态规划值时，它所有前驱节点的动态规划值都已经确定。拓扑排序与 DP 结合后，可以解决 DAG 中的最长路径、到达所有节点的最小代价，或依赖链上的最大收益等问题。该顺序保证每个节点都在所有依赖项处理完毕后，仅计算一次动态规划值。

from collections import deque, defaultdict

def longest_path_dag(V, edges):
    graph = defaultdict(list)
    in_degree = [0] * V
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1
    queue = deque(i for i in range(V) if in_degree[i] == 0)
    dp = [0] * V
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            dp[v] = max(dp[v], dp[u] + w)
            in_degree[v] -= 1
            if in_degree[v] == 0: queue.append(v)
    return max(dp)

print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)]))  # 7

快速检查

请测试您对本课中数据结构与算法——编程面试准备相关概念的理解。

课程回顾

在本课中，您学到了：卡恩算法通过使用 BFS 反复移除零入度节点来计算拓扑排序；环检测无需额外代价——如果结果数量小于 n，则存在环；以及将队列替换为最小堆可以得到字典序最小的拓扑排序。接下来，我们将探索基于 DFS 的后序拓扑排序，了解它作为卡恩算法的另一种选择。

常见问题解答