topologicalSort

拓扑排序 - 对有向无环图(DAG)进行拓扑排序。

输入配置

节点数量

依赖关系 (JSON格式: [[课程,前置课程]])[[1,0],[2,0],[3,1],[3,2]]

执行过程

步骤 1 / 14

构建图和入度数组

0

入度: 0

1

入度: 1

2

入度: 1

3

入度: 2

队列状态

空

拓扑排序结果

空

速度:慢速正常快速超快

当前处理

队列中

已处理

算法说明

拓扑排序：使用Kahn算法(BFS)，将入度为0的节点加入队列，依次处理并减少邻接节点入度。时间复杂度O(V+E)。

函数签名

function topologicalSort(
  numCourses: number,
  prerequisites: number[][]
): TopologicalSortResult

function topologicalSortDFS(
  numCourses: number,
  prerequisites: number[][]
): TopologicalSortResult

interface TopologicalSortResult {
  canFinish: boolean
  order: number[]
}

参数

参数名	类型	必填	说明
numCourses	number	是	节点数量
prerequisites	number[][]	是	边的数组,[a,b]表示a依赖b

返回值

类型	说明
TopologicalSortResult	包含是否可完成和拓扑序

工作原理

Kahn算法(BFS)

1. 构建邻接表和入度数组
2. 将所有入度为0的节点入队
3. 每次取出一个节点,将其邻居的入度-1
4. 如果邻居入度变为0,加入队列
5. 如果处理了所有节点,说明无环

时间复杂度: O(V+E)
空间复杂度: O(V+E)

DFS版本

使用visiting数组检测环。

应用: 课程调度、任务排序、编译顺序