用java实现拓补算法

拓扑排序（Topological Sorting）是指将有向无环图（DAG）中的节点按照拓扑顺序进行排序的算法。在拓扑排序中，若存在一条从节点 A 到节点 B 的路径，那么在排序结果中节点 A 出现在节点 B 的前面。

以下是使用 Java 实现拓扑排序算法的示例代码：

import java.util.*;

public class TopologicalSort {
    public List<Integer> sort(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        Map<Integer, List<Integer>> graph = new HashMap<>();

        // 初始化图和入度数组
        for (int i = 0; i < numCourses; i++) {
            graph.put(i, new ArrayList<>());
        }
        for (int[] edge : prerequisites) {
            graph.get(edge[1]).add(edge[0]);
            indegrees[edge[0]]++;
        }

        // 使用队列存储入度为 0 的节点
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }

        // 拓扑排序
        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.poll();
            result.add(node);
            for (int neighbor : graph.get(node)) {
                indegrees[neighbor]--;
                if (indegrees[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }

        // 判断图中是否存在环
        if (result.size() != numCourses) {
            return new ArrayList<>();
        }

        return result;
    }
}

这段代码中，我们首先初始化了图和入度数组。然后使用队列存储入度为 0 的节点，并在每次从队列中取出节点时，将其邻居节点的入度减 1。如果邻居节点的入度为 0，则将其加入队列中。最后，我们判断是否存在环，如果不存在，则返回拓扑排序结果。