拓扑排序两种实现的代码示例

有些算法我们可能会写，也用过，但就是不记得关于它的“专业术语”了。

比如昨天有网友留言：拓扑排序...

看到这个词我就慌了，这是啥玩意？可不能让网友知道我不知道他说的啥。

今天就通过两个示例来理解这个术语：拓扑排序。

一、拓扑排序的核心概念

拓扑排序（Topological Sorting）是一种对有向无环图（DAG, Directed Acyclic Graph）节点进行排序的算法。

它的目标是将图中的节点排列成一个线性顺序，使得对于每条有向边 (u, v)，节点 u 都排在节点 v 的前面。这种排序广泛应用于任务调度、编译依赖分析等场景。

拓扑排序的前提是图中没有环，即图是一个有向无环图。如果图中存在环，那么就无法对节点进行拓扑排序，因为环中的节点无法满足先后顺序的要求。

拓扑排序的输出通常是一个线性序列，表示节点的一个合法的处理顺序。对于一个有多个依赖关系的任务集合，拓扑排序可以帮助确定一个可行的执行顺序。

关键词：有向、无环、图。

比如下面这个图：

在这个图中，节点 1 指向节点 2 和节点 3。

节点 2 和节点 3 都指向节点 4。

节点 4 没有指向其他节点。

节点1的入度为0，也就是说1前面没有节点了。节点2和3的入度为1。节点4的入度为2。

二、拓扑排序的实现方法

拓扑排序有两种主要的实现方法：Kahn 算法（基于入度）和深度优先搜索（DFS）。

1、基于入度的 Kahn 算法

Kahn 算法的核心思想是使用入度（indegree），即每个节点的入边数量。我们将入度为 0 的节点放入队列中，因为它们没有依赖关系，可以首先处理。

算法步骤如下：

计算图中每个节点的入度。

将所有入度为 0 的节点加入队列。

当队列不为空时，取出队列中的节点，将其加入拓扑排序结果中。

遍历该节点的所有邻居节点，将它们的入度减 1，如果某个邻居节点的入度变为 0，则将其加入队列。

重复步骤 3 和 4，直到队列为空。

如果拓扑排序结果中的节点数量等于图中的节点数量，说明排序成功；否则，图中存在环。

下面是 Kahn 算法的 Java 代码实现：

import java.util.*;

/**

* Kahn 算法

*

*/

public class TopologicalSort {

public static List<Integer> kahnTopologicalSort(Map<Integer, List<Integer>> graph, int numNodes) {

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

// 1、记录每个节点的入度

int[] indegree = new int[numNodes + 1];

// 2、计算每个节点的入度

for (List<Integer> neighbors : graph.values()) {

for (int neighbor : neighbors) {

indegree[neighbor]++;

}

}

// 3、将所有入度为 0 的节点加入队列

Queue<Integer> queue = new LinkedList<>();

for (int i = 1; i <= numNodes; i++) {

if (indegree[i] == 0) {

queue.offer(i);

}

}

// 5、执行 Kahn 算法

while (!queue.isEmpty()) {

int node = queue.poll();

result.add(node);

for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {

// 4、将它们的入度减 1，如果某个邻居节点的入度变为 0，则将其加入队列

indegree[neighbor]--;

if (indegree[neighbor] == 0) {

queue.offer(neighbor);

}

}

}

// 6、检查是否存在环

if (result.size() != numNodes) {

throw new IllegalStateException("图中存在环，无法进行拓扑排序！");

}

return result;

}

public static void main(String[] args) {

// 示例图：邻接列表表示

Map<Integer, List<Integer>> graph = new HashMap<>();

graph.put(1, Arrays.asList(2, 3));

graph.put(2, Arrays.asList(4));

graph.put(3, Arrays.asList(4));

graph.put(4, Arrays.asList());

// 图的顶点数量

int numNodes = 4;

List<Integer> topologicalOrder = kahnTopologicalSort(graph, numNodes);

System.out.println("拓扑排序顺序: " + topologicalOrder);

}

}

在这个代码中：

indegree 数组记录每个节点的入度。

queue 用于存储入度为 0 的节点，按顺序处理。

如果最终 result 的长度不等于节点数量，说明图中有环，无法进行拓扑排序。

运行结果：

拓扑排序顺序: [1, 2, 3, 4]

2、基于 DFS 的拓扑排序

使用 DFS 实现拓扑排序的思路是：对每个节点进行 DFS 遍历，在递归完成时将节点加入栈中。最终栈中的节点顺序即为拓扑排序的顺序。

算法步骤如下：

对每个未访问的节点进行 DFS。

在访问节点的所有邻居节点后，将该节点加入栈。

最终，栈的逆序即为拓扑排序的结果。

下面是 DFS 实现的 Java 代码：

import java.util.*;

/**

* DFS

*/

public class TopologicalSortDFS {

public static void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited, Stack<Integer> stack) {

// 标记节点为已访问

visited.add(node);

for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {

// 不包含的节点

if (!visited.contains(neighbor)) {

// 循环访问

dfs(neighbor, graph, visited, stack);

}

}

// 2、所有邻居访问完后，将节点加入栈

stack.push(node);

}

public static List<Integer> topologicalSortDFS(Map<Integer, List<Integer>> graph, int numNodes) {

// 已访问集合

Set<Integer> visited = new HashSet<>();

Stack<Integer> stack = new Stack<>();

for (int i = 1; i <= numNodes; i++) {

// 1、对每个未访问的节点进行 DFS

if (!visited.contains(i)) {

dfs(i, graph, visited, stack);

}

}

// 排序结果集合

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

while (!stack.isEmpty()) {

// 栈逆序即为拓扑排序结果

result.add(stack.pop());

}

// 3、返回排序后的结果集

return result;

}

public static void main(String[] args) {

// 示例图：邻接列表表示

Map<Integer, List<Integer>> graph = new HashMap<>();

graph.put(1, Arrays.asList(2, 3));

graph.put(2, Arrays.asList(4));

graph.put(3, Arrays.asList(4));

graph.put(4, Arrays.asList());

// 图的顶点数量

int numNodes = 4;

List<Integer> topologicalOrder = topologicalSortDFS(graph, numNodes);

System.out.println("拓扑排序顺序: " + topologicalOrder);

}

}

在这个代码中：

visited 集合用于记录已访问的节点，避免重复访问。

stack 存储节点，最终逆序输出得到拓扑排序。

运行结果：

拓扑排序顺序: [1, 3, 2, 4]

Kahn 算法使用LinkedList的队列实现，DFS使用Stack栈实现，队列是先进先出，栈是后进先出，需要注意的是，它俩排序的结果是不一样的，这个还需要看业务场景。

三、拓扑排序的应用场景

拓扑排序在很多实际场景中都很有用，尤其是在任务调度和依赖管理方面：

任务调度：在项目管理中，如果任务之间有先后依赖关系（例如任务 B 依赖于任务 A 完成），可以使用拓扑排序找到任务的执行顺序。

编译依赖管理：在编译大型软件时，源代码文件通常有依赖关系。拓扑排序可以帮助确定文件的编译顺序。

课程安排：在学术课程安排中，某些课程需要先修其他课程，拓扑排序可以用于生成课程的学习顺序。

四、拓扑排序的时间复杂度和空间复杂度

假设图的节点数为 V，边数为 E，则：

时间复杂度：O(V + E)，因为每个节点和边最多访问一次。

空间复杂度：O(V)，因为需要存储入度数组（Kahn 算法）或递归栈和 visited 集合（DFS）。

五、拓扑排序的注意事项

拓扑排序只适用于有向无环图。如果图中有环，则无法进行拓扑排序。

拓扑排序的结果可能不唯一，如果图中存在多个顺序都满足要求，拓扑排序结果也会不同。

六、最后总结

拓扑排序是一种用于对有向无环图节点进行线性排序的算法，常用于解决依赖问题。它可以通过 Kahn 算法（基于入度）或 DFS 实现，具有 O(V + E) 的时间复杂度，是解决依赖排序问题的高效方法。

真好，又把忘记的算法捡起来了。会写算法，术语也能说个一二，才能一本正经地装X，哈哈。