207、课程表

leetcode

Created At : 2020-07-26 00:19

Count:800 Views 👀 :

Comment:

207、课程表
1. 示例 1:
2. 示例 2:
题解
1. 1、广度优先遍历
2. 2、深度优先搜索

207、课程表

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

示例 2:

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。

提示：

输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
你可以假定输入的先决条件中没有重复的边。
$1 <= numCourses <= 10^5$

链接：https://leetcode-cn.com/problems/course-schedule

题解

n个课程的编号是：$0,1,…,n-1$

1、广度优先遍历

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 判断有向图是否存在环
        // 入度表
        int[] indegrees = new int[numCourses];
        // 邻接表
        List<List<Integer>> adjacency = new ArrayList<>();
        // 广度优先遍历的队列
        Queue<Integer> queue = new LinkedList<>();
        // 初始化邻接表
        for (int i = 0;i < numCourses;i++) {
            adjacency.add(new ArrayList<>());
        }
        // 初始化课程的前驱课程数 以及邻接表
        for (int[] cp : prerequisites) {
            indegrees[cp[0]]++;
            adjacency.get(cp[1]).add(cp[0]);
        }
        // 将所有没有前置课程的课程入队
        for (int i = 0;i < numCourses;i++) {
            if (indegrees[i] == 0) {
                queue.add(i);
            }
        }
        // 广度优先搜索
        while (!queue.isEmpty()) {
            // 前置课程树为0的课程出队
            int pre = queue.poll();
            // 待排序的课程为0
            numCourses--;
            // 将后去课程的入度减一，同时将没有前驱课程的课程入队
            for (int cur: adjacency.get(pre)) {
                if (--indegrees[cur] == 0) {
                    queue.add(cur);
                }
            }
        }
        return numCourses == 0;
    }
}

2、深度优先搜索

状态数组flags，多状态管理:

1: 表示当前节点已经作为dfs的开始节点遍历过
0: 表示从未被遍历
-1：表示已被其他节点通过dfs访问

class Solution {
    public boolean canFinish(int numCourses,int[][] prerequisites) {
        List<List<Integer>> adjacency = new ArrayList<>();
        for (int i = 0;i < numCourses;i++) {
            adjacency.add(new ArrayList<>());
        }
        int[] flags = new int[numCourses];
        for (int[] cp : prerequisites) {
            adjacency.get(cp[0]).add(cp[1]);
        }
        // 对每个课程进行深度优先搜索
        for (int i = 0;i < numCourses;i++) {
            // 找到环，返回false
            if (!dfs(adjacency,flags,i)) return false;
        }
        return true;
    }

    private boolean dfs(List<List<Integer>> adjacency, int[] flags,int i) {
        // 说明在本轮 DFS 搜索中节点 i 被第 22 次访问，即 课程安排图有环 
        if (flags[i] == 1) {
            return false;
        }
        // 说明当前访问节点已被其他节点启动的 DFS 访问，无需再重复搜索
        if (flags[i] == -1) {
            return true;
        }
        flags[i] = 1;
        for (Integer j : adjacency.get(i)) {
            if (!dfs(adjacency,flags,j)) {
                return false;
            }
        }
        flags[i] = -1;
        return true;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com