拓扑排序的工程意义

拓扑排序是对一个有向图构造拓扑序列，解决工程是否能顺利进行的问题。构造时有 2 2 2种结果：

1. 此图全部顶点被输出：说明说明图中无「环」存在， 是 AOV 网（有向无环图）
2. 没有输出全部顶点：说明图中有「环」存在，不是 AOV 网

主要思想

遍历所有入度为 0 0 0的节点，并由该节点刷新其指向节点的度，即将其指向节点的入度减 1 1 1，当该节点入度为 0 0 0，将其加入队列。最后查看所有节点的入度是否为 0 0 0，如果全部为 0 0 0，说明该网络是有向无环图。

例题

LeetCode.207 课程表

你这个学期必须选修 n u m C o u r s e s numCourses numCourses门课程，记为 0 0 0到 n u m C o u r s e s − 1 numCourses-1 numCourses−1 。 在选修某些课程之前需要一些先修课程。 先修课程按数组 p r e r e q u i s i t e s prerequisites prerequisites 给出，其中 p r e r e q u i s i t e s [ i ] = [ a i , b i ] prerequisites[i] = [a_i, b_i] prerequisites[i]=[ai,bi]，表示如果要学习课程 a i a_i ai则必须先学习课程 b i b_i bi。例如，先修课程对 [ 0 , 1 ] [0, 1] [0,1]表示：想要学习课程 0 0 0，你需要先完成课程 1 1 1 。 请你判断是否可能完成所有课程的学习？如果可以，返回 t r u e true true；否则，返回 f a l s e false false。 提示： 1 < = n u m C o u r s e s < = 1 0 5 1 <= numCourses <= 10^5 1<=numCourses<=105 0 < = p r e r e q u i s i t e s . l e n g t h < = 5000 0 <= prerequisites.length <= 5000 0<=prerequisites.length<=5000 p r e r e q u i s i t e s [ i ] . l e n g t h = = 2 prerequisites[i].length == 2 prerequisites[i].length==2 0 < = a i , b i < n u m C o u r s e s 0 <= a_i, b_i < numCourses 0<=ai,bi<numCourses p r e r e q u i s i t e s [ i ] prerequisites[i] prerequisites[i]中的所有课程对互不相同

思路

使用拓扑排序来解题，当构成的有向图没有环，那么说明可以完成所有课程的学习。先修课程数组相当于有向图的边，当课程不需要先修课程即可学习，那么该课程入度为 0 0 0，否则入度就是需要先修课程的数量。

代码

class Solution {
          
   
    public boolean canFinish(int n, int[][] edges) {
          
   
        int[] d = new int[n];
        List<Integer>[] g = new List[n];
        for(int i = 0; i < n; i++) {
          
   
            g[i] = new ArrayList<>();
        }
        for(int[] x : edges) {
          
   
            int a = x[0], b = x[1];
            g[b].add(a);
            d[a]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for(int i = 0; i < n; i++) {
          
   
            if(d[i] == 0) {
          
   
                q.offer(i);
            }
        }
        int cnt = 0;
        while(q.size() > 0) {
          
   
            int x = q.poll();
            cnt++;
            for(int y : g[x]) {
          
   
                d[y]--;
                if(d[y] == 0) {
          
   
                    q.offer(y);
                }
            }
        }
        return cnt == n;
    }
}