欢迎光临
我们一直在努力

力扣实训 _ [207].课程表/图论

1. 题目回顾

本题是经典的图论问题 LeetCode 207. 课程表。
核心要求:给定 numCourses 门课程(编号 0 到 numCourses-1)和先修关系数组 prerequisites,判断是否可能完成所有课程的学习。
本质转化:将课程看作节点,先修关系看作有向边,判断该有向图中是否存在环。若存在环(如 A 依赖 B,B 依赖 A),则无法完成;若无环(即有向无环图 DAG),则可以完成。

2. 核心思路:拓扑排序与“入度归零”

解决此类问题的核心在于拓扑排序。我们可以把修课过程想象成“剥洋葱”或“流水线生产”:

  • 入度(Indegree):表示一门课有多少个前置依赖。例如 [0, 1] 表示学 0 之前必须先学 1,此时课程 0 的入度为 1。
  • 核心逻辑:只有当一门课的入度变为 0 时(即所有前置课程都修完了),这门课才能被选修。
  • 判环依据:如果我们不断移除入度为 0 的课程,最后发现还有课程剩余(入度永远不为 0),说明剩下的课程之间存在循环依赖,无法完成。

3. 算法详细步骤

3.1 深度优先搜索 (DFS) 步骤

这种方法通过递归遍历来检测“当前路径上”是否有环。

  • 构建邻接表:建立从“先修课”指向“后续课”的映射关系。
  • 状态标记:为每个节点维护三种状态:
    • 0:未访问。
    • 1:正在访问中(在当前递归栈中)。如果再次遇到状态为 1 的节点,说明发现了环。
    • 2:已完成访问(安全节点)。
  • 递归检测:对每个未访问节点启动 DFS。如果在递归过程中遇到状态为 1 的邻居,直接返回 False。
  • 回溯标记:当某节点的所有邻居都检查完毕且无环,将其标记为 2。
  • 3.2 广度优先搜索 (BFS) / 入度表法步骤

    这是最直观的“模拟上课”过程,也是通常所说的拓扑排序标准解法。

  • 统计入度与建图:
    • 计算每门课的入度(有多少先修课)。
    • 建立邻接表,记录每门课修完后能解锁哪些后续课程。
  • 初始化队列:将所有入度为 0 的课程加入队列(这些是可以直接开始学的课)。
  • 循环处理:
    • 从队列取出一个课程,计数器 +1(表示已修完)。
    • 遍历该课程的后续课程,将它们入度 -1。
    • 如果某后续课程入度变为 0,说明其前置条件已全部满足,加入队列。
  • 结果判定:比较“已修课程数”与“总课程数”。若相等,说明无环,返回 True;否则返回 False。
  • 4. 代码实现

    以下代码采用 Python 编写,注重可读性。

    解法一:BFS 入度表法

    import java.util.*;

    class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 1. 初始化数据结构
    // inDegree[i] 存储第 i 门课的先修课数量
    int[] inDegree = new int[numCourses];
    // adj 存储邻接表,adj[i] 包含修完 i 之后可以修的所有课程
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
    adj.add(new ArrayList<>());
    }

    // 2. 构建图和入度表
    for (int[] pre : prerequisites) {
    int target = pre[0]; // 目标课程
    int source = pre[1]; // 先修课程
    // source -> target
    adj.get(source).add(target);
    // 目标课程入度 +1
    inDegree[target]++;
    }

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

    // 4. BFS 过程
    int count = 0; // 记录已修完的课程数
    while (!queue.isEmpty()) {
    int curr = queue.poll(); // 拿出一门课来修
    count++;

    // 遍历这门课解锁的后续课程
    for (int nextCourse : adj.get(curr)) {
    inDegree[nextCourse]–; // 前置任务少了一个
    // 如果入度变为 0,说明可以修这门课了
    if (inDegree[nextCourse] == 0) {
    queue.offer(nextCourse);
    }
    }
    }

    // 5. 判断是否所有课都能修完
    return count == numCourses;
    }
    }

    解法二:DFS 状态标记法

    class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 构建邻接表
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < numCourses; i++) {
    adj.add(new ArrayList<>());
    }
    for (int[] pre : prerequisites) {
    adj.get(pre[1]).add(pre[0]);
    }

    // flags 数组用于标记节点状态
    // 0: 未访问
    // 1: 正在访问(当前递归路径上)-> 发现环的标志
    // -1: 已访问(安全节点,之前的路径已经确认无环)
    int[] flags = new int[numCourses];

    // 对每个节点进行 DFS 检测
    for (int i = 0; i < numCourses; i++) {
    if (!dfs(adj, flags, i)) {
    return false;
    }
    }
    return true;
    }

    private boolean dfs(List<List<Integer>> adj, int[] flags, int i) {
    // 如果状态为 1,说明在当前路径上遇到了自己,有环!
    if (flags[i] == 1) return false;
    // 如果状态为 -1,说明之前已经检查过这条路,是安全的,无需重复检查
    if (flags[i] == -1) return true;

    // 标记为正在访问
    flags[i] = 1;

    // 递归访问所有邻居
    for (int j : adj.get(i)) {
    if (!dfs(adj, flags, j)) {
    return false;
    }
    }

    // 当前节点及其所有后代都检查完毕,没有环,标记为安全
    flags[i] = -1;
    return true;
    }
    }

    5. 复杂度分析

    BFS 入度表法

    • 时间复杂度: O(N+E)。其中 N 是课程数, E 是先修关系数。我们需要遍历所有节点和所有边各一次。
    • 空间复杂度: O(N+E) 。需要存储邻接表( E )和入度数组( N )以及队列( N )。

    DFS 状态标记法

    • 时间复杂度: O(N+E) 。每个节点和每条边最多被访问一次。
    • 空间复杂度: O(N+E) 。除了存储图的空间外,递归调用栈在最坏情况下(链状图)深度为 N 。
    赞(0)
    未经允许不得转载:171主机测评 » 力扣实训 _ [207].课程表/图论
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址