景真

外观

课程表

约 1700 字大约 6 分钟

图拓扑排序DFSBFS

2025-02-25

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。这是可能的。

示例 2：

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

提示：

  • 1 <= numCourses <= 105
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同

DFS，动态规划，后序

构建邻接表，用于存储课程的先修关系，对每个课程进行 DFS，标记数组记录每个节点的状态，正在访问可用于发现环，已访问可去重。

就好像有多条链表，DFS是依次处理完每条链表，BFS是同时处理每条链表的头节点。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 定义并初始化邻接表 adjacencyList，存储课程的先修关系
        List<List<Integer>> adjacencyList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        // 构建邻接表：prerequisite[1] -> prerequisite[0] 表示修完 prerequisite[1] 才能修 prerequisite[0]
        for (int[] prerequisite : prerequisites) {
            adjacencyList.get(prerequisite[1]).add(prerequisite[0]);
        }
        
        // 创建标记数组，记录每个节点的访问状态：0 = 未访问, 1 = 正在访问, -1 = 已访问
        int[] visitStatus = new int[numCourses];
        
        // 对每个课程进行深度优先搜索（DFS）。需要执行多次DFS，但是会用记忆数组中的-1优化
        for (int course = 0; course < numCourses; course++) {
            if (hasCycle(adjacencyList, visitStatus, course)) {
                return false;  // 如果发现环，无法完成所有课程，返回 false
            } 
        }
        
        return true;  // 如果没有发现环，可以完成所有课程，返回 true
    }

    // 深度优先搜索辅助函数，检查是否存在环
    private boolean hasCycle(List<List<Integer>> adjacencyList, int[] visitStatus, int course) {
        // 如果当前节点正在访问，说明存在环，返回 true。重点。
        if (visitStatus[course] == 1) {
            return true;
        }
        if (visitStatus[course] == -1) {  
            return false;  // 如果当前节点已访问过，直接返回 false
        }
        
        // 标记当前节点为正在访问。这个操作是为了避免重复，是个辅助操作，对当前节点的主要操作是下面的for循环
        visitStatus[course] = 1;
        // 遍历当前课程的所有后续课程，递归检测是否存在环
        for (Integer nextCourse : adjacencyList.get(course)) {
            if (hasCycle(adjacencyList, visitStatus, nextCourse)) {
                return true;  // 如果发现环，返回 true
            }
        }
        // 当前节点及其所有后续课程都处理完后，标记当前节点为已访问。重点。
        visitStatus[course] = -1;
        
        return false;  // 当前节点及其后续课程没有环，返回 false
    }
}
  • 时间复杂度: O(n+m)O(n+m) ，其中 nn 为课程数，mm 为先修课程的要求数。这其实就是对图进行深度优先搜索的时间复杂度。
  • 空间复杂度: O(n+m)O(n+m) 。题目中是以列表形式给出的先修课程关系，为了对图进行深度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(n+m)O(n+m) 。在深度优先搜系的过程中，我们需要最多 O(n)O(n) 的栈空间 (递归) 进行深度优先搜索，因此总空间复杂度为 O(n+m)O(n+m)。

BFS

队列里存入度为零的元素，每剥去一个入度为零的元素，就要把它的联系也去掉，即与之相连的元素的入度也要减一， 如果一个元素的入度减到了零，那么要把它也入队。就像提一颗多叉树，我们肯定要捏着最上面的根节点，如果根节点被我们提掉了， 那么它的一个子节点就成了根节点，我们只能捏这个新根节点了。我们的目的是拆开这个由多个多叉树组成的图，肯定要从根节点开始拆， 最后如果找不到根节点（类似线头），那就拆不开了。队列就相当于备忘录，或DFS中的标记数组，只要按照顺序拆，就不会重复。

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];  // 记录每个课程的入度。重点。
        List<List<Integer>> adjacencyList = new ArrayList<>();  // 邻接表，存储课程的依赖关系
        Queue<Integer> queue = new LinkedList<>();  // 队列，存储入度为0的课程

        // 初始化邻接表
        for (int i = 0; i < numCourses; i++) {
            adjacencyList.add(new ArrayList<>());
        }
        // 构建邻接表和入度数组
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int prerequisiteCourse = prerequisite[1];
            
            indegrees[course]++;  // 当前课程的入度加1
            adjacencyList.get(prerequisiteCourse).add(course);  // 添加依赖关系。前置课表指向后置课表，也可以后置指向前置。只要是有向图都可以。入度数组指的是被指向节点的入度。
        }

        // 将所有入度为0的课程加入队列
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                queue.offer(i);
            }
        }

        // 处理队列中的课程
        int processedCourses = 0;  // 记录已处理的课程数量
        while (!queue.isEmpty()) {
            int currentCourse = queue.poll();  // 取出队首元素
            processedCourses++;  // 已处理的课程数量加1

            // 遍历当前课程指向的所有课程，该节点出队后，它指向的所有节点的入度都要减一。
            for (int nextCourse : adjacencyList.get(currentCourse)) {
                indegrees[nextCourse]--;  // 当前课程的入度减1
                if (indegrees[nextCourse] == 0) {  // 如果入度变为0，将其加入队列。队列中只存储入度为0的节点，因此两个互相依赖的节点不会入队。
                    queue.offer(nextCourse);
                }
            }
        }

        // 如果所有课程都已处理完，则可以完成所有课程，否则不行
        return processedCourses == numCourses;
    }
}
  • 时间复杂度: O(n+m)O(n+m) ，其中 nn 为课程数， mm 为先修课程的要求数。这其实就是对图进行广度优先搜索的时间复杂度。
  • 空间复杂度: O(n+m)O(n+m) 。题目中是以列表形式给出的先修课程关系，为了对图进行广度优先搜索，我们需要存储成邻接表的形式，空间复杂度为 O(n+m)O(n+m) 。在广度优先搜素的过程中，我们需要最多 O(n)O(n) 的队列空间 (迭代) 进行广度优先搜索。因此总空间复杂度为 O(n+m)O(n+m) 。