Java 实现拓扑排序算法（源代码）

拓扑排序（Topological Sorting）是对DAG（有向无环图，Directed Acyclic Graph）的顶点进行排序，使得对每一条有向边 (u, v)，均有 u（在排序记录中）比 v 先出现。它通常用于在具有依赖关系的任务中确定任务的执行顺序。 实现步骤： 创建一个队列，用于存放入度为0的顶点。 创建一个数组或列表，用于存放拓扑排序的结果。 创建一个数组或列表，用于记录每个顶点的入度。 遍历所有顶点，如果某个顶点没有前驱（即入度为0），则将其加入队列。 当队列不为空时，执行以下操作： 从队列中取出一个顶点，并添加到结果列表中。 遍历该顶点的所有邻接点，将它们的入度减1。 如果邻接点的入度变为0，则将其加入队列。 如果结果列表中的顶点数不等于DAG中的顶点数，则说明图中存在环，无法进行拓扑排序。 ### Java 实现拓扑排序算法（源代码） #### 拓扑排序算法介绍 拓扑排序（Topological Sorting）是一种针对有向无环图（DAG，Directed Acyclic Graph）的特殊排序方法。其基本思想是对于有向图中的每条边 (u, v)，确保顶点 u 在排序序列中位于顶点 v 之前。这种排序方式常被用于处理有先后顺序依赖的任务安排问题中，例如课程选修、项目依赖等场景。 #### 拓扑排序的实现步骤 拓扑排序可以通过以下步骤实现： 1. **初始化**：创建一个队列用于存储入度为 0 的顶点；创建一个数组或列表来存储最终的拓扑排序结果；另外创建一个数组或列表来记录每个顶点的入度。 2. **寻找入度为 0 的顶点**：遍历所有顶点，将入度为 0 的顶点加入队列。 3. **处理队列中的顶点**：当队列非空时，执行以下操作： - 从队列中取出一个顶点，并将其添加到结果列表中。 - 遍历该顶点的所有邻接点，并减少它们的入度值。 - 如果某个邻接点的入度变为 0，则将该邻接点加入队列。 4. **检测环的存在**：若最终的结果列表中的顶点数与 DAG 中的顶点总数相等，则说明图中无环且排序成功；否则，图中存在环，无法完成拓扑排序。 #### Java 代码实现 下面通过具体的 Java 代码实现上述拓扑排序算法。为了便于理解，我们定义了一个 `Graph` 类来表示图结构，并提供添加边、进行拓扑排序等方法。 ```java import java.util.*; public class TopologicalSort { private static class Graph { private int V; // 顶点数量 private LinkedList<Integer>[] adj; // 邻接表 private int[] inDegree; // 入度数组 Graph(int v) { V = v; adj = new LinkedList[v]; inDegree = new int[v]; for (int i = 0; i < v; ++i) adj[i] = new LinkedList<>(); } void addEdge(int v, int w) { adj[v].add(w); inDegree[w]++; // 增加w的入度 } void topologicalSort() { Queue<Integer> queue = new LinkedList<>(); // 使用队列代替栈实现 List<Integer> result = new ArrayList<>(); // 存储拓扑排序结果 int[] inDegreeCopy = Arrays.copyOf(inDegree, V); // 复制入度数组 // 将所有入度为0的顶点加入队列 for (int i = 0; i < V; i++) if (inDegreeCopy[i] == 0) queue.offer(i); while (!queue.isEmpty()) { int u = queue.poll(); result.add(u); // 添加到结果列表 for (int v : adj[u]) { inDegreeCopy[v]--; if (inDegreeCopy[v] == 0) queue.offer(v); } } if (result.size() != V) { System.out.println("存在环，无法完成拓扑排序！"); } else { System.out.println("拓扑排序结果为：" + result); } } } public static void main(String[] args) { Graph g = new Graph(6); g.addEdge(5, 2); g.addEdge(5, 0); g.addEdge(4, 0); g.addEdge(4, 1); g.addEdge(2, 3); g.addEdge(3, 1); g.topologicalSort(); } } ``` #### 代码解析 1. **类定义**：定义了一个 `Graph` 类来表示图结构，其中包含了顶点数量 `V`、邻接表 `adj` 和入度数组 `inDegree`。 2. **添加边**：通过 `addEdge` 方法向图中添加边，并更新顶点的入度。 3. **拓扑排序**：`topologicalSort` 方法实现了拓扑排序的过程。首先初始化一个队列和结果列表，并复制一份入度数组以跟踪每次迭代后的入度变化。然后遍历所有顶点，将初始入度为 0 的顶点加入队列。接下来循环处理队列中的顶点，直至队列为空。最后检查结果列表的长度是否与顶点总数相等，以此判断图中是否存在环。 通过上述代码实现，我们可以清晰地看到拓扑排序的基本流程及其实现细节，有助于理解和应用拓扑排序算法解决实际问题。