【图论】Leetcode 207. 课程表【中等】

课程表

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

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

• 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

  请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

  示例1：

  输入： numCourses = 2, prerequisites = [[1,0]]

  输出： true

  解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

  解题思路

  • 这个问题可以转化为判断有向图中是否存在环的问题，如果存在环，

    则说明存在课程之间的循环依赖，无法完成所有课程的学习；

    如果不存在环，则说明不存在循环依赖，可以完成所有课程的学习。

  • 1、使用拓扑排序来判断是否存在环，即是否可以完成所有课程的学习。

  • 2、使用邻接表来表示课程之间的先修关系。

  • 3、统计每门课程的入度，入度为0表示没有先修课程。

  • 4、将入度为0的课程加入队列，并从队列中依次弹出课程，将其后继课程的入度减1。

  • 5、如果存在环，即存在入度为0的课程无法全部弹出，则说明无法完成所有课程的学习，返回false；否则返回true。

    Java实现

    广度优先搜索（BFS）实现

    public class CourseSchedule {
        public boolean canFinish(int numCourses, int[][] prerequisites) {
            // 构建有向图和入度数组
            Map graph = new HashMap();
            int[] indegree = new int[numCourses];
            for (int[] prereq : prerequisites) {
                int course = prereq[0];
                int prereqCourse = prereq[1];
                graph.putIfAbsent(prereqCourse, new ArrayList());
                graph.get(prereqCourse).add(course);
                indegree[course]++;
            }
            
            // 将入度为 0 的节点加入队列中
            Queue queue = new LinkedList();
            for (int i = 0; i  
    时间空间复杂度
     
    

    • 时间复杂度：O(V + E)，其中 V 表示课程数量，E 表示先修课程的数量，因为需要构建邻接表和统计入度，以及进行BFS拓扑排序。

    • 空间复杂度：O(V + E)，其中 V 表示课程数量，E 表示先修课程的数量，因为需要存储邻接表和入度数组。