拓扑排序判断有向图中是否有环_拓扑排序判环

拓扑排序的工程意义

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

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

主要思想

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

例题

LeetCode.207 课程表

你这个学期必须选修$numCourses$门课程，记为$0$到$numCourses-1$ 。
在选修某些课程之前需要一些先修课程。 先修课程按数组$prerequisites$ 给出，其中$prerequisites[i]=[a_i,b_i]$，表示如果要学习课程$a_i$则必须先学习课程$b_i$。例如，先修课程对$[0,1]$表示：想要学习课程$0$，你需要先完成课程$1$ 。
请你判断是否可能完成所有课程的学习？如果可以，返回$true$；否则，返回$false$。
提示：
$1<=numCourses<=10^5$
$0<=prerequisites.length<=5000$
$prerequisites[i].length==2$
$0<=a_i,b_i<numCourses$
$prerequisites[i]$中的所有课程对互不相同

思路

使用拓扑排序来解题，当构成的有向图没有环，那么说明可以完成所有课程的学习。先修课程数组相当于有向图的边，当课程不需要先修课程即可学习，那么该课程入度为$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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32