拓扑排序

以leetcode上207. Course Schedule为例，实现拓扑排序

题目简述：有n个课程，某些课程有前置课程，用课程对表示。问是否可以按要求完成所有课程。

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

学习课程j之前需要先学习课程i，用i->j表示，将每个课程看成节点，课程间的依赖关系看成有向边，则问题就转换成了有向图是否有环，或者是否存在拓扑结构。
下面是拓扑排序的代码，主要是用矩阵记录每个对应关系，数组记录每个节点的入度，入度为0加入队列中，依次出队列表示剔除这个节点，更新依赖这个节点的其他节点的入度，如果入度更新为0则加入队列中，直到队列为空。
队列中添加的总是入度为0的结点，最后考虑队列中添加的结点数是否和总结点数相同即可判断是否有拓扑结构。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[][] matrix = new int[numCourses][numCourses]; // i -> j
        int[] indegree = new int[numCourses];  //入度

        //赋值
        for(int i = 0; i < prerequisites.length; ++i){
            int pre = prerequisites[i][1];
            int course = prerequisites[i][0];
            matrix[pre][course] = 1;
            indegree[course] ++;
        }

        //拓扑排序
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; ++i){
            if(indegree[i] == 0) queue.offer(i);
        }
        int count = 0;
        while(!queue.isEmpty()){
            int course = queue.poll();
            for(int i = 0; i < numCourses; ++i){
                if(matrix[course][i] == 1){
                    indegree[i] --;
                    if(indegree[i] == 0){
                        queue.offer(i);
                    }
                }
            }
            count ++;
        }

        return count == numCourses;
    }
}