使用 Kahn 算法进行拓扑排序
排列依赖其他任务的任务顺序
使用 Kahn 算法进行拓扑排序 是 CoddyKit 上的免费 Coding Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。
什么是拓扑序
拓扑序会列出有向图中的每个节点，使每条边都从较早的节点指向较晚的节点。可以把它理解为：先安排任务，再安排依赖这些任务的任务。
只允许 DAG
这只适用于DAG，也就是有向无环图。如果存在环，就不可能找到一个满足所有依赖关系的有效顺序。
入度的概念
Kahn算法依赖入度：也就是指向某个节点的边数。入度为零的节点没有尚未满足的依赖关系。
统计每个入度
第一遍遍历所有边，并统计每个节点作为终点出现的次数。这就得到了每个节点的入度。
indeg = [0] * n
for u in range(n):
for v in adj[u]:
indeg[v] += 1初始化就绪队列
所有入度为零的节点现在都已经就绪，因此请将它们全部加入队列，作为开始。
from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)处理一个节点
取出一个就绪节点，并将它append到拓扑序中。现在处理它是安全的，因为没有剩余节点依赖它。
u = q.popleft()
order.append(u)释放它的邻居
对于每个邻居，将其入度减一。当某个邻居变为零时，它就准备就绪并加入队列。
for v in adj[u]:
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)重复直到队列为空
不断取出节点并释放其邻居，直到队列为空。拓扑序会一次加入一个安全节点，直到所有节点都被放入。
顺便检测环
如果最终的拓扑序包含的节点少于 n 个，说明剩余节点被一个环困住了。Kahn算法无需额外开销就能检测环。
if len(order) < n:
print('cycle exists')运行时间
每个节点和每条边都只会被访问一次，因此 Kahn算法的运行时间为O(V + E)。即使图中有数百万条边，也能应对。
多个有效顺序
当多个节点同时就绪时，它们中的任意一个都可以下一个处理。因此，DAG通常有许多个有效的拓扑序，而不只是一个。
快速检查
您完成了 Kahn算法，但拓扑序中的节点少于 n 个。这意味着什么？
回顾：Kahn算法
统计入度，将入度为零的节点加入队列，取出一个节点，将邻居的入度减一，然后重复。这就是简洁的拓扑排序，时间复杂度为 O(V+E)。🚀
常见问题解答
「使用 Kahn 算法进行拓扑排序」课时是免费的吗？
是的 — 「使用 Kahn 算法进行拓扑排序」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。
「使用 Kahn 算法进行拓扑排序」这节课中我会学到什么？
排列依赖其他任务的任务顺序 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Coding Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「使用 Kahn 算法进行拓扑排序」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Coding Interview Prep 课中编写并运行代码吗？
能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。