高频刷题-207. Course Schedule和210. Course Schedule II

高频刷题-207. Course Schedule和210. Course Schedule II

https://leetcode.com/problems/course-schedule/

 

拓扑排序用于解决有向无环图(DAG, Directed Acyclic Graph)按依赖关系排线性序列问题,直白地说解决这样的问题:有一组数据,其中一些数据依赖其他,问能否按依赖关系排序(被依赖的排在前面),或给出排序结果。

 

最常用解决拓扑排序问题的方法是Kahn算法,步骤可以概括为:

 

  1. 根据依赖关系,构建邻接矩阵或邻接表、入度数组;
  2. 取入度为0的数据(即不依赖其他数据的数据),根据邻接矩阵/邻接表依次减小依赖其的数据的入度;
  3. 判断减小后是否有新的入度为0的数据,继续进行第2步;

直到所有数据入度为0,得到拓扑排序序列,或返回失败(存在环形依赖)。

高频刷题-207. Course Schedule和210. Course Schedule II

具体实现为:

定义二维数组 graph 来表示这个有向图,一维数组 in 来表示每个顶点的入度。开始先根据输入来建立这个有向图,并将入度数组也初始化好。然后定义一个 queue 变量,将所有入度为0的点放入队列中,然后开始遍历队列,从 graph 里遍历其连接的点,每到达一个新节点,将其入度减一,如果此时该点入度为0,则放入队列末尾。直到遍历完队列中所有的值,若此时还有节点的入度不为0,则说明环存在,返回 false,反之则返回 true。

public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 使用邻接表建图
        List[] graph = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses];
        
        // queue存储入度为0的节点
        Queue<Integer> queue = new LinkedList<>();

        // 给graph[i]分配空间
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        // 使用邻接表建图,生成inDegree值
        for (int[] edge : prerequisites) {
            graph[edge[1]].add(edge[0]);
            inDegree[edge[0]]++;
        }

        // 将入度为0的节点放到queue
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        int count = 0;  // 最终check出队列的课程数量是否等于输入的数量,等于说明每个节点都变成了入度为0的节点,表示边已经删除殆尽
        while(!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            for (int i = 0; i < graph[course].size(); i++) {  // 查找它的临接节点,删除边(将它们的度减1)
                int neighbor = (int)graph[course].get(i);
                if (--inDegree[neighbor] == 0) queue.offer(neighbor); // 如果入度为0则加到queue中
            }
        }
        return count == numCourses;
    }

对一个具有n个顶点e条弧的AOV网来说, Kahn算法的时间复杂度为O(n+e)。

 

高频刷题-207. Course Schedule和210. Course Schedule II

https://leetcode.com/problems/course-schedule-ii/

这个题目就是将上面输出的拓扑排序输出出来。注意这里有一些不好处理的地方,需要判断如果图是有环的时候,返回的是[]。代码上直接copy之前的实现,就加上了返回结果res。

public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 使用邻接表建图
        List[] graph = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses];
        int[] res = new int[numCourses];  // 返回的topological sorting结果
        int index = 0;
        
        // queue存储入度为0的节点
        Queue<Integer> queue = new LinkedList<>();

        // 给graph[i]分配空间
        for (int i = 0; i < numCourses; i++) {
            graph[i] = new ArrayList<Integer>();
        }

        // 使用邻接表建图,生成inDegree值
        for (int[] edge : prerequisites) {
            graph[edge[1]].add(edge[0]);
            inDegree[edge[0]]++;
        }

        // 将入度为0的节点放到queue
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
                res[index++] = i;
            }
        }
        
        while(!queue.isEmpty()) {
            int course = queue.poll();
            for (int i = 0; i < graph[course].size(); i++) {  // 查找它的临接节点,删除边(将它们的度减1)
                int neighbor = (int)graph[course].get(i);
                if (--inDegree[neighbor] == 0) {
                    queue.offer(neighbor); // 如果入度为0则加到queue中
                    res[index++] = neighbor;
                }
            }
        }
        return index == numCourses ? res : new int[0];
    }

 

上一篇:[百度空间] --whole-archive & --no-whole-archive


下一篇:【leetcode】课程表