[数据结构与算法]课程排序java实现

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //这一题输出先修课程在后修课程之前的特点其实和拓扑排序的特点不谋而合
        //第一步是根据prerequisites构建一张图
        Map<Integer,List<Integer>> graph = new HashMap<>();
        for(int i = 0;i < numCourses;i++){
            graph.put(i,new LinkedList<>());
        }
        int[] indegred = new int[numCourses];
        for(int[] prerequisite : prerequisites){
            graph.get(prerequisite[1]).add(prerequisite[0]);
            indegred[prerequisite[0]]++;
        }
        //构建完图之后执行拓扑排序算法，先找出入度为0的节点入队，然后将入度为0的节点从图中删除，以它为起始节点的节点入度减少，如果此时入读为0则入队
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0;i < indegred.length;i++){
            if(indegred[i] == 0){
                queue.offer(i);
            }
        }
        LinkedList<Integer> list = new LinkedList<Integer>();
        while(!queue.isEmpty()){
            int pos = queue.poll();
            list.add(pos);
            for(int next : graph.get(pos)){
                indegred[next]--;
                if(indegred[next] == 0){
                    queue.offer(next);
                }
            }
        }
        return list.size() == numCourses ? list.stream().mapToInt(i -> i).toArray() : new int[0];
    }
}