Java使用List和Map实现拓扑排序 代码加注释描述

下面是使用 List 和 Map 实现拓扑排序的 Java 代码，注释已经加上：

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class TopologicalSort {
    public static void main(String[] args) {
        // 构建图，key 为节点，value 为该节点的后继节点列表
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(1, new ArrayList<>());
        graph.put(2, new ArrayList<>());
        graph.put(3, new ArrayList<>());
        graph.put(4, new ArrayList<>());
        graph.put(5, new ArrayList<>());
        graph.get(1).add(2);
        graph.get(1).add(3);
        graph.get(2).add(4);
        graph.get(3).add(4);
        graph.get(4).add(5);

        // 拓扑排序，返回排序后的节点列表
        List<Integer> sorted = topologicalSort(graph);

        // 输出排序结果
        System.out.println(sorted);
    }

    /**
     * 使用 List 和 Map 实现拓扑排序
     * @param graph 待排序的有向图，key 为节点，value 为该节点的后继节点列表
     * @return 排序后的节点列表
     */
    public static List<Integer> topologicalSort(Map<Integer, List<Integer>> graph) {
        // 统计每个节点的入度
        Map<Integer, Integer> inDegree = new HashMap<>();
        for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
            int node = entry.getKey();
            inDegree.putIfAbsent(node, 0); // 初始化节点的入度为 0
            for (int successor : entry.getValue()) {
                inDegree.put(successor, inDegree.getOrDefault(successor, 0) + 1); // 统计后继节点的入度
            }
        }

        // 将入度为 0 的节点加入队列
        List<Integer> queue = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : inDegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.add(entry.getKey());
            }
        }

        // 拓扑排序
        List<Integer> sorted = new ArrayList<>();
        while (!queue.isEmpty()) {
            int node = queue.remove(0); // 取出队首节点
            sorted.add(node); // 将节点加入排序列表
            for (int successor : graph.get(node)) { // 遍历后继节点
                int newDegree = inDegree.get(successor) - 1; // 将后继节点的入度减 1
                inDegree.put(successor, newDegree);
                if (newDegree == 0) { // 如果后继节点的入度为 0，则加入队列
                    queue.add(successor);
                }
            }
        }

        if (sorted.size() != graph.size()) { // 如果排序列表的长度小于节点数，说明图中存在环
            throw new IllegalArgumentException("The graph contains a cycle");
        }

        return sorted;
    }
}