教程目录

想要实际看看算法是如何工作的吗?

通过交互式可视化深入理解算法运行过程

查看算法可视化

拓扑排序算法

介绍

拓扑排序(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

...

目录