交互式Python实验室

Topological Sort (Kahn's)

Playground在加载时自动运行。点击运行我的代码来追踪你的Python代码 — 每一步实时动画展示。

解释·逐行

回放·逐步

挑战·引导式提示

XP·...

数据流水线

mastery 路径

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

解释

Line 3

topo_sort(5, edges) called. Graph: 0→1, 0→2, 1→3, 2→3, 3→4.

为什么用这种方法？

We have a DAG with 5 nodes. A topological sort orders them so every edge points from earlier to later in the sequence — prerequisite before dependent.

Structured Explanation

Overview

拓扑排序将DAG(有向无环图)的节点按依赖关系排序。

Analogy

就像确定选课顺序——先修必修课再上进阶课。

Step-by-step

计算每个节点的入度
将所有入度=0的节点加入队列
出队节点，将邻居的入度减1
入度变0的加入队列，若未处理完所有节点则有环

Visual

1→2→4 ↓ 3→4 Topo: [1,2,3,4]

Common mistakes

只能用于有向图
不检测环

Practice questions

从依赖列表生成有效课程表
比较Kahn算法和DFS在课程管理中的应用

Time

O(V + E)

Space

O(V)

复杂度

时间

O(V + E)

空间

O(V)

复杂度概览

O(1)

O(log n)

O(n)时间

O(n log n)

O(n²)

n = 8范围 1-20

当 N = 8 时

复杂度	操作
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

挑战

对以下关系进行拓扑排序: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1。

提示

使用Kahn算法：计算入度，将入度为0的节点入队，处理队列。

代码工作室

Topological Sort (Kahn's)

Monaco就绪

Python就绪

lesson.pyline 3

Loading editor...

输出控制台

1 lines

❯ [0, 1, 2, 3, 4]

现实世界应用

1

NPM/Yarn package installs

2

Vite / Webpack module bundling builds

3

Database foreign-key creation schemas

Comments

Loading comments...