Java实现拓扑排序：算法详解与代码示例363

拓扑排序(Topological Sorting) 是一种对有向无环图(Directed Acyclic Graph, DAG) 的顶点进行线性排序的方法。在这个排序中，对于图中的每一条有向边 (u, v)，顶点 u 都出现在顶点 v 的前面。换句话说，如果存在一条从顶点 A 到顶点 B 的路径，那么顶点 A 必须在排序中出现在顶点 B 的前面。拓扑排序并非唯一，一个 DAG 可以有多个有效的拓扑排序。

拓扑排序在许多实际应用中都非常有用，例如：
课程安排：确定课程的学习顺序，使得先修课程总是在后续课程之前学习。
软件构建：确定软件模块的编译顺序，确保依赖关系得到满足。
数据依赖分析：在数据处理流水线中，确定数据处理步骤的执行顺序。
Makefile构建：在大型项目中确定编译顺序。

Java 提供了多种方法实现拓扑排序。本文将重点介绍两种常用的方法：基于 Kahn 算法和基于深度优先搜索(DFS) 的方法，并提供相应的 Java 代码示例。

基于 Kahn 算法的拓扑排序

Kahn 算法是一种基于贪心策略的拓扑排序算法。其基本思想是：持续查找入度为 0 的顶点（即没有指向它的边），并将这些顶点添加到排序结果中。然后，删除这些顶点及其出边，并重复这个过程，直到所有顶点都被处理。

以下是用 Java 实现 Kahn 算法的代码:```java
import .*;
public class TopologicalSortKahn {
public static List topologicalSort(Map graph) {
Map inDegree = new HashMap();
for (int node : ()) {
(node, 0);
}
for (int node : ()) {
for (int neighbor : (node)) {
(neighbor, (neighbor) + 1);
}
}
Queue queue = new LinkedList();
for ( entry : ()) {
if (() == 0) {
(());
}
}
List result = new ArrayList();
while (!()) {
int node = ();
(node);
for (int neighbor : (node, new ArrayList())) {
(neighbor, (neighbor) - 1);
if ((neighbor) == 0) {
(neighbor);
}
}
}
if (() != ()) {
return new ArrayList(); // 图中有环
}
return result;
}

public static void main(String[] args) {
Map graph = new HashMap();
(5, (11, 12));
(7, (8, 11));
(3, (8, 10));
(11, (2, 9, 10));
(8, (9));
List sorted = topologicalSort(graph);
("拓扑排序结果: " + sorted);
}
}
```

这段代码首先计算每个节点的入度，然后将入度为 0 的节点加入队列。循环处理队列中的节点，将节点加入结果列表，并将该节点的邻接节点入度减一。如果邻接节点入度变为 0，则将其加入队列。最后，如果结果列表的大小与图中节点数量不同，则表示图中有环，返回空列表。

基于深度优先搜索(DFS)的拓扑排序

另一种实现拓扑排序的方法是使用深度优先搜索 (DFS)。DFS 遍历图，在访问完一个节点的所有后继节点后，将该节点添加到结果列表的开头。这种方法的逆序结果即为拓扑排序。

以下是用 Java 实现基于 DFS 的拓扑排序的代码：```java
import .*;
public class TopologicalSortDFS {
private static List result = new ArrayList();
private static Set visited = new HashSet();
private static Set visiting = new HashSet();
public static List topologicalSort(Map graph) {
for (int node : ()) {
if (!(node)) {
if (!dfs(graph, node)) return new ArrayList(); //图中有环
}
}
(result);
return result;
}

private static boolean dfs(Map graph, int node) {
if ((node)) return false; // 存在环
if ((node)) return true;
(node);
for (int neighbor : (node, new ArrayList())) {
if (!dfs(graph, neighbor)) return false;
}
(node);
(node);
(node);
return true;
}

public static void main(String[] args) {
Map graph = new HashMap();
(5, (11, 12));
(7, (8, 11));
(3, (8, 10));
(11, (2, 9, 10));
(8, (9));
List sorted = topologicalSort(graph);
("拓扑排序结果: " + sorted);
}
}
```