这篇深入的文章将教你如何以递归顺序在有向无环图上实现拓扑排序。本教程分为两个部分。

首先，我们从理论上展开拓扑顺序的结构、应用、范围和排序，以帮助我们的读者建立基础，然后自己执行 Java 代码。

你可能已经猜到了，本文的第二部分是关于有向无环图 (DAG) 的实现。

拓扑排序是图中标注 (n) 的排序。如果在 (u,v) 之间有一条边，那么 u 必须在 v 之前。

在现实世界的场景中，它可以成为构建相互依赖的应用程序的基础。

在我们进行拓扑排序之前，你必须考虑只有有向无环图 (DAG) 才能进行拓扑排序。

要到达那里，你一次只能带一个。假设你走 B 路。在这种情况下，你不会走 A 路。

因此，它不会创建一个绝对循环。因此，拓扑排序也是可能的。

相反，只有一个周期。拓扑顺序很可能被排除。

它类似于深度优先搜索 (DFS) 算法，但有一个额外的堆栈。时间复杂度一般来说是 O(V+E)。

O(V) - 堆栈需要额外的空间。

首先，你应该清楚，如果图是有向无环图 (DAG)，拓扑排序是唯一可行的解​​决方案。另外，请注意，对于给定的有向无环图，可能有几种替代的拓扑排序。

拓扑排序是顶点在数组中的排列。

考虑以下示例：

此 DAG 最多有四种可能的排序解决方案：

如果你理解了缩写，我们希望你也能理解以下对 DAG 的假设描述。值得一提的是，我们的演示只是为了解释通用过程。

如果你对数据结构方面感兴趣，请考虑另一种选择。但是，以下描述足以使用 Java 以递归和迭代顺序对直接图进行排序，以达到所有实际目的。

因此，事不宜迟，请按照以下步骤操作。

如你所见，VA 在上图中的 in-degree 最少。

由于我们得到了两个入度最小的顶点，因此最终可以将图排序为以下两个 n 顺序。

我们将使用这个图来实现。我们的目标是基于图论确定 u 在 v 之前的从属关系。

不用说，这个执行是基于 DAG 和 DFS。我们将使用一种算法对图进行拓扑排序。

请继续阅读每一步以了解更多信息。

让我们以 v15 为例。V15 取决于 v10 和 v5。

V5 依赖于 v10 和 v20。V10 依赖于 v20。

基于依赖关系，v5、v10 和 v20 在拓扑排序中应该排在 v15 之前。

你还应该了解深度优先搜索 (DFS) 以了解此实现。

深度优先搜索，也称为深度优先遍历，是一种递归算法，用于查找图或树数据结构的所有顶点。遍历一个图需要访问它的所有节点。

它将图形的每个顶点分类为两组之一。

另外，请注意 DFS 算法的功能如下：

同时，应重复步骤 2 和 3，直到堆栈为空。

因为拓扑排序包含一个短栈，所以我们不会立即打印顶点。相反，我们将递归地对其所有邻居调用拓扑排序，然后将其推送到堆栈中。

到目前为止，让我们将逻辑流程分解为几个易于理解的部分。

代码：

代码：