数据结构-拓扑排序解决调度问题

优先级限制下的调度问题：给定一组需要完成的任务，以及一组关于任务完成的先后次序的优先级限制。在满足限制条件的前提下应该如何安排并完成所有任务？

拓扑排序：给定一幅有向图，将所有顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素（或者说明无法做到这一点）。

优先级限制下不应该存在有向环，一个优先级限制的问题如果存在有向环，那么这个问题 肯定是无解的。

先来解决有向环检测问题：

采用深度优先遍历来解决这个问题：用一个栈表示“当前”正在遍历的有向路径上的顶点。一旦找到一条有向边v->w，并且w已经存在于栈中，那么就找到了一个环；如果没有找到这条边，那么就是无环图。

实现：

Java

其实，将有向无环图的深度优先遍历的路径记录下来就是一种拓扑排序！遍历的顺序取决于数据结构的性质以及是在递归调用之前还是之后保存。一般有三种排列排序：

前序：在递归调用之前将顶点加入队列

后序：在递归调用之后将顶点加入队列

逆后序：在递归调用之后将顶点压入栈

基于深度优先搜索的顶点排序：

首先定义三个数据结构：

Java

然后改写dfs()方法：

Java

最后实现拓扑排序：

Java

一幅有向无环图的拓扑排序即为所有顶点的逆后序排序。

使用深度优先搜索对有向无环图进行 拓扑排序需要的时间和V+E成正比。