如何在Java中高效地实现拓扑排序？

在Java中实现拓扑排序（Topological Sort）通常用于处理有向无环图（DAG, Directed Acyclic Graph），其结果是一个线性的序列，表示从依赖关系的角度来看，所有节点按照某种顺序排列。以下是一种使用邻接表表示图并使用深度优先搜索（DFS）来实现的简单但高效的算法：

import java.util.*;

class Node {
    int id;
    List<Node> dependencies;

    Node(int id) {
        this.id = id;
        this.dependencies = new ArrayList<>();
    }
}

public class TopologicalSort {
    public static List<Integer> topologicalSort(Node[] nodes) {
        Map<Integer, Integer> indegreeMap = new HashMap<>();
        for (Node node : nodes) {
            for (Node dep : node.dependencies) {
                if (!indegreeMap.containsKey(dep.id)) {
                    indegreeMap.put(dep.id, 0);
                }
                indegreeMap.put(node.id, indegreeMap.get(node.id) + 1);
            }
        }

        Queue<Node> queue = new LinkedList<>();
        for (int id : indegreeMap.keySet()) {
            if (indegreeMap.get(id) == 0) {
                queue.offer(nodes[id]);
            }
        }

        List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            Node curr = queue.poll();
            result.add(curr.id);
            for (Node dep : curr.dependencies) {
                indegreeMap.put(dep.id, indegreeMap.get(dep.id) - 1);
                if (indegreeMap.get(dep.id) == 0) {
                    queue.offer(dep);
                }
            }
        }

        return result.stream().sorted().collect(Collectors.toList());
    }

    // 示例用法
    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        Node n4 = new Node(4);

        n1.dependencies.add(n2); // n1 -> n2
        n2.dependencies.add(n3); // n2 -> n3
        n3.dependencies.add(n4); // n3 -> n4

        System.out.println(topologicalSort(new Node[]{n1, n2, n3, n4}));
    }
}

这个算法首先计算每个节点的入度（依赖其他节点的数量），然后将入度为0的节点加入队列。接着，每次从队列中取出一个节点，将其添加到结果列表中，并更新依赖它的节点的入度。如果某个节点的入度变为0，就再次将该节点放入队列。由于这是一个DFS的过程，所以当遍历完所有节点后，得到的结果就是一个有效的拓扑排序。