【图论】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<Integer, List<Integer>> 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<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        // 使用广度优先搜索进行拓扑排序
        int visited = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            visited++;
            List<Integer> neighbors = graph.getOrDefault(course, new ArrayList<>());
            for (int neighbor : neighbors) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.offer(neighbor);
                }
            }
        }
        
        return visited == numCourses;
    }

    public static void main(String[] args) {
        CourseSchedule scheduler = new CourseSchedule();
        int numCourses = 4;
//        int[][] prerequisites = {{1, 0}, {2, 1}, {3, 2}, {3, 1}};
        int[][] prerequisites = {{1, 0}, {2, 1}, {3, 2}, {1, 3}};
        System.out.println(scheduler.canFinish(numCourses, prerequisites));
    }
}

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

时间空间复杂度

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

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