本文共 2603 字，大约阅读时间需要 8 分钟。

链接：

大意：

给定一个整数num为所需学习的课程数目，一个二维整数数组pre为修习课程的先决条件。若pre中某个一维数组为[0,1]，则表示要学习0号课程，则必须先学习1号课程。规定：课程编号为0~num-1。现在要求判断是否有一种安排使得可以修习完所有课程。例子：

思路：

说的这么多，其实就是在一个有向图中判断是否存在拓扑序列。

通过num值，构造一个每个节点的入度数组degree，以及构造一个以每个节点为边的起点的边信息graph（其实就是构图）。

通过pre数组，对degree和graph进行初始化。

接下来就是模拟寻找拓扑序列了。

首先，找到图中剩余顶点中的一个入度为0的顶点，之后将以该顶点为起点的边所指向的节点的入度减1，同时需要将该节点置为已访问（不然下次找入度为0的顶点时又会找到它）。之后便是重复该过程。知道找到的顶点数（课程数）等于num（返回true）或者找不到入度为0的点了 （返回false）

代码：

class Solution {    // 判断一个图是否可以找出一个拓扑序列    public boolean canFinish(int num, int[][] pre) {        int[] degree = new int[num]; // 记录每个节点的入度        List
   
    [] graph = new ArrayList[num]; // 记录各个边的关系        for (int i = 0; i < num; i++) {            graph[i] = new ArrayList<>();        }        for (int[] nums : pre) {            degree[nums[0]]++;            graph[nums[1]].add(nums[0]); // nums[1] -> nums[0]        }        int count = 0;        boolean[] visited = new boolean[num]; // 记录节点是否已被访问        while (count < num) {            int curIdx = -1;            // 尝试找到一个入度为0的点            for (int i = 0; i < degree.length; i++) {                if (!visited[i] && degree[i] == 0) {                    curIdx = i;                    break;                }            }            // 没找到入度为0的点            if (curIdx == -1)                break;            visited[curIdx] = true;            for (int tail : graph[curIdx]) {                degree[tail]--;            }            count++;        }        return count == num;    }}
   

结果：

结论：

效率有点低，需要改进。

改进：

猜测主要性能瓶颈是在while循环中尝试找到入度为0的点的for循环中，需要遍历一次degree数组。可以使用一个列表idxs首先存储一开始入度为0的点，然后依次取出list的点，判断该点指向的那些点入度减1后是否为0.若为0，则将指向的该点也加入idxs

当idxs为空时跳出循环，并判断count是否与num相等

class Solution {    // 判断一个图是否可以找出一个拓扑序列    public boolean canFinish(int num, int[][] pre) {        int[] degree = new int[num]; // 记录每个节点的入度        List
   
    [] graph = new ArrayList[num]; // 记录各个边的关系        for (int i = 0; i < num; i++) {            graph[i] = new ArrayList<>();        }        for (int[] nums : pre) {            degree[nums[0]]++;            graph[nums[1]].add(nums[0]); // nums[1] -> nums[0]        }        int count = 0;        ArrayList
    
      idxs = new ArrayList<>(); // 存储所有当前入度为0的点的位置        // 记录入度为0的点        for (int i = 0; i < degree.length; i++) {            if (degree[i] == 0)                 idxs.add(i);        }        while (!idxs.isEmpty()) {            int curIdx = idxs.remove(idxs.size() - 1);            for (int tail : graph[curIdx]) {                if (--degree[tail] == 0) // 又找到一个新的入度为0的点                    idxs.add(tail);            }            count++;        }        return count == num;    }}
    
   

转载地址：http://baesi.baihongyu.com/