什么是拓扑排序

我在网上查找了很多例子并观看了 YouTube 视频，但我仍然对拓扑排序是什么有点迷失。据我了解，您应该从已访问和未访问的队列开始，并在访问完节点的所有子节点后获取拓扑排序顺序？

拓扑排序意味着你会得到一份工作列表和先决条件列表，你必须弄清楚工作的顺序。

职位 = [1,2,3] 先决条件 = [[1,2], [1, 3], [3,2]]

result = [1,3,2] 应该是作业执行的顺序。 这里 [1,2] 表示作业 2 在作业 1 完成之前无法启动（作业 1 是先决条件）。

因此，为此，您可以使用简单的深度优先搜索（图遍历算法）。其中您可以有一个以 JobVertex 命名的自定义类

class JobVertex {
   int job;
   List<JobVertex> preRequisites;
   boolean inProgress; 
   boolean visited;}

最初，inProgress 和visited 标志都可以设置为 false。 inProgress 标志用于检测循环（因为要使拓扑排序工作图必须是 DAG）

List<Integer> result = new ArrayList<>();

result 是将添加我们订购的作业的最终列表。 dfs(node, result) 方法可以如下所示，其中您可以从任何节点开始，然后以递归方式遍历其先决条件，并在每次迭代时更新标志。

时间复杂度可以与 dfs (v + e) 的时间复杂度相同，其中 v 对应于顶点，e 分别对应于边。