拓扑排序算法

图算法

拓扑排序是对有向无环图(DAG)的顶点进行排序,使得对于图中任意一条有向边(u, v),顶点u在排序中都出现在顶点v之前。

时间复杂度:最佳 O(V + E) | 平均 O(V + E) | 最差 O(V + E)
空间复杂度:O(V)
图类型:有向图

应用场景/前提条件

  • 只适用于有向无环图(DAG)

算法讲解

拓扑排序算法

介绍

拓扑排序(Topological Sort)是一种用于有向无环图(DAG, Directed Acyclic Graph)的排序算法,它将图中的所有顶点排成一个线性序列,使得对于图中的每一条有向边(u, v),顶点u在这个序列中都出现在顶点v之前。拓扑排序常用于解决依赖关系问题,例如任务调度、课程安排、软件包的安装顺序等。

算法步骤

  1. 计算图中所有顶点的入度(指向该顶点的边的数量)
  2. 将所有入度为0的顶点加入队列
  3. 当队列非空时,重复以下步骤:
    • 从队列中取出一个顶点,将其加入结果序列
    • 对该顶点的所有邻接顶点,将其入度减1
    • 如果某个邻接顶点的入度变为0,则将其加入队列

算法详解

假设有一个有向无环图,包含6个顶点(0-5),边的关系如下:

  • 5 → 0
  • 5 → 2
  • 4 → 0
  • 4 → 1
  • 2 → 3

...