拓扑排序算法
介绍
拓扑排序(Topological Sort)是一种用于有向无环图(DAG, Directed Acyclic Graph)的排序算法,它将图中的所有顶点排成一个线性序列,使得对于图中的每一条有向边(u, v),顶点u在这个序列中都出现在顶点v之前。拓扑排序常用于解决依赖关系问题,例如任务调度、课程安排、软件包的安装顺序等。
算法步骤
- 计算图中所有顶点的入度(指向该顶点的边的数量)
- 将所有入度为0的顶点加入队列
- 当队列非空时,重复以下步骤:
- 从队列中取出一个顶点,将其加入结果序列
- 对该顶点的所有邻接顶点,将其入度减1
- 如果某个邻接顶点的入度变为0,则将其加入队列
算法详解
假设有一个有向无环图,包含6个顶点(0-5),边的关系如下:
- 5 → 0
- 5 → 2
- 4 → 0
- 4 → 1
- 2 → 3
...