有向无环图(DAG)可用来表示各种事物的顺序。比如以各项工作为顶点,用有向边来表示工作顺序。
如果对这种表示顺序关系的DAG进行拓扑排序, 我们便能得到一个恰当的工作顺序。
拓扑排序不是用于将n个数从小到大排序,而是对于一个DAG,对图上的点进行排序,使得对于图上的任意一条有向边(u, v),在排序后的序列中,u出现在v之前。
如何进行拓扑排序:
- 用边表存下边,记录下每个点的入度 (即有多少条边以该点为终点)
- 先将所有入度为0的点加入操作队列
• 在操作队列中
• 将队头设为操作点,并弹出队头
• 将操作点相连的边从图中删除
(实际实现中我们只需要将该点能到达的点的入度减一)
• 查看该点能到达的点是否有入度为0的点,有的话将其加入队列
• 此时点进入队列时的标号就是一种可行的拓扑排序