算法:拓扑排序(TopologicalSort)

2019-07-19 12:28:04 浏览数 (1)

1. 基本原理

有向无环图(Directed Acyclic Graph, DAG)是有向图的一种。常常被用来表示事件之间的驱动依赖关系,管理任务之间的调度。拓扑排序是对DAG的顶点进行排序,使得对每一条有向边(u, v),均有u(在排序记录中)比v先出现。

图1:正确的拓扑排序示例

图2:错误的拓扑排序示例

2. 代码示例

3. 特性分析

  • 时间复杂度:O(V E);

0 人点赞