【笔记】基于链式前向星的图论算法(三) 拓扑排序


有向无环图(DAG)可用来表示各种事物的顺序。比如以各项工作为顶点,用有向边来表示工作顺序。

如果对这种表示顺序关系的DAG进行拓扑排序, 我们便能得到一个恰当的工作顺序。

拓扑排序不是用于将n个数从小到大排序,而是对于一个DAG,对图上的点进行排序,使得对于图上的任意一条有向边(u, v),在排序后的序列中,u出现在v之前。

如何进行拓扑排序:

  • 用边表存下边,记录下每个点的入度 (即有多少条边以该点为终点)
  • 先将所有入度为0的点加入操作队列
    • 在操作队列中
    • 将队头设为操作点,并弹出队头
    • 将操作点相连的边从图中删除
    (实际实现中我们只需要将该点能到达的点的入度减一)
    • 查看该点能到达的点是否有入度为0的点,有的话将其加入队列
    • 此时点进入队列时的标号就是一种可行的拓扑排序

Author: thyzzs
Reprint policy: All articles in this blog are used except for special statements CC BY-SA 4.0 reprint policy. If reproduced, please indicate source thyzzs !
  TOC