每日算法 — 使用java实现课程表：拓扑排序与有向图环检测

问题描述

课程表问题是图论中的经典应用场景。假设你总共有 numCourses 门课需要选，记为 0 到 numCourses-1。在选修某些课程之前需要先修完一些其他课程，这种前置依赖关系用数组 prerequisites 表示，其中 prerequisites[i] = [ai, bi] 表示如果要学习课程 ai，则必须先学习课程 bi。问题是：判断是否存在一种选课顺序，使得所有课程都能顺利完成？

该问题的本质是判断有向图中是否存在环。如果存在环，意味着课程之间存在循环依赖，无法完成全部课程；如果不存在环，则可以找到合法的选课顺序。

核心思路：拓扑排序

拓扑排序（Topological Sort）是对有向无环图（DAG）的节点进行线性排序，使得对于图中的每条有向边 (u, v)，节点 u 在排序中总是位于节点 v 之前。

解决课程表问题有两种经典方法：

方法一：Kahn算法（基于入度的BFS）

1. 计算每个节点的入度（即有多少前置课程）。
2. 将所有入度为0的节点加入队列（这些课程没有前置依赖，可以直接选修）。
3. 依次从队列中取出节点，将其加入拓扑序列，并将其所有邻接节点的入度减1。
4. 如果邻接节点入度变为0，将其加入队列。
5. 最终如果拓扑序列的长度等于节点总数，说明无环；否则存在环。

方法二：DFS深度优先搜索

1. 用三种颜色标记节点状态：白色（未访问）、灰色（正在访问）、黑色（已访问完毕）。
2. DFS遍历过程中，如果遇到灰色节点，说明存在环。
3. 如果DFS完成未发现环，则存在合法选课顺序。

完整Java实现

import java.util.*;

/**
 * 课程表问题求解器
 * 使用拓扑排序判断有向图中是否存在环
 */
public class CourseSchedule {

    /**
     * Kahn算法：基于入度的广度优先搜索实现拓扑排序
     *
     * @param numCourses    课程总数
     * @param prerequisites 前置依赖关系，prerequisites[i] = [a, b] 表示b是a的先修课
     * @return 是否可以完成所有课程（即图中无环）
     */
    public boolean canFinishKahn(int numCourses, int[][] prerequisites) {
        // 构建邻接表和入度数组
        // adjacency[i] 存储课程i的所有后继课程（即依赖i的课程）
        List<Integer>[] adjacency = new ArrayList[numCourses];
        // inDegree[i] 表示课程i的入度（前置课程数量）
        int[] inDegree = new int[numCourses];

        // 初始化邻接表
        for (int i = 0; i < numCourses; i++) {
            adjacency[i] = new ArrayList<>();
        }

        // 根据前置依赖关系构建图
        for (int[] pre : prerequisites) {
            int course = pre[0];   // 当前课程
            int prerequisite = pre[1]; // 前置课程
            // 前置课程 -> 当前课程 建立有向边
            adjacency[prerequisite].add(course);
            // 当前课程的入度加1
            inDegree[course]++;
        }

        // 使用队列存储所有入度为0的节点（无前置依赖的课程）
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 记录已处理的课程数量
        int processedCount = 0;

        // BFS处理队列中的节点
        while (!queue.isEmpty()) {
            int current = queue.poll();
            processedCount++;

            // 遍历当前课程的所有后继课程
            for (int next : adjacency[current]) {
                // 后继课程的入度减1（相当于完成了一门前置课）
                inDegree[next]--;
                // 如果入度变为0，说明所有前置课程已完成，可以加入队列
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // 如果所有课程都被处理，说明无环，可以完成全部课程
        return processedCount == numCourses;
    }

    /**
     * DFS算法：使用三色标记法检测环
     * 0=白色(未访问), 1=灰色(正在访问), 2=黑色(已访问完毕)
     */
    public boolean canFinishDFS(int numCourses, int[][] prerequisites) {
        // 构建邻接表
        List<Integer>[] adjacency = new ArrayList[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adjacency[i] = new ArrayList<>();
        }
        for (int[] pre : prerequisites) {
            adjacency[pre[1]].add(pre[0]);
        }

        // 0=未访问, 1=正在访问(在当前DFS路径上), 2=已访问完毕
        int[] visitStatus = new int[numCourses];

        // 对每个未访问的节点执行DFS
        for (int i = 0; i < numCourses; i++) {
            if (visitStatus[i] == 0) {
                if (hasCycle(i, adjacency, visitStatus)) {
                    return false; // 发现环，无法完成课程
                }
            }
        }
        return true; // 无环，可以完成全部课程
    }

    /**
     * DFS递归检测从当前节点出发是否存在环
     *
     * @param current    当前访问的节点
     * @param adjacency  邻接表
     * @param status     访问状态数组
     * @return 是否存在环
     */
    private boolean hasCycle(int current, List<Integer>[] adjacency, int[] status) {
        // 标记当前节点为"正在访问"
        status[current] = 1;

        // 遍历所有后继节点
        for (int next : adjacency[current]) {
            if (status[next] == 1) {
                // 遇到"正在访问"的节点，说明存在回边，即存在环
                return true;
            }
            if (status[next] == 0) {
                // 未访问的节点，继续DFS
                if (hasCycle(next, adjacency, status)) {
                    return true;
                }
            }
            // status[next] == 2 表示已安全访问完毕，无需处理
        }

        // 当前节点的所有后继都已处理完毕，标记为"已访问完毕"
        status[current] = 2;
        return false;
    }

    /**
     * 返回一个合法的选课顺序（拓扑排序序列）
     * 如果无法完成全部课程，返回空数组
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] adjacency = new ArrayList[numCourses];
        int[] inDegree = new int[numCourses];

        for (int i = 0; i < numCourses; i++) {
            adjacency[i] = new ArrayList<>();
        }
        for (int[] pre : prerequisites) {
            adjacency[pre[1]].add(pre[0]);
            inDegree[pre[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] order = new int[numCourses];
        int index = 0;

        while (!queue.isEmpty()) {
            int current = queue.poll();
            order[index++] = current;

            for (int next : adjacency[current]) {
                inDegree[next]--;
                if (inDegree[next] == 0) {
                    queue.offer(next);
                }
            }
        }

        // 如果index不等于numCourses，说明存在环，返回空数组
        return index == numCourses ? order : new int[0];
    }

    public static void main(String[] args) {
        CourseSchedule solution = new CourseSchedule();

        // 测试用例1：无环，可以完成
        int numCourses1 = 2;
        int[][] prerequisites1 = {{1, 0}};
        System.out.println("测试1 - Kahn: " + solution.canFinishKahn(numCourses1, prerequisites1)); // true
        System.out.println("测试1 - DFS: " + solution.canFinishDFS(numCourses1, prerequisites1)); // true
        System.out.println("测试1 - 选课顺序: " + Arrays.toString(solution.findOrder(numCourses1, prerequisites1)));

        // 测试用例2：有环，无法完成
        int numCourses2 = 2;
        int[][] prerequisites2 = {{1, 0}, {0, 1}};
        System.out.println("\n测试2 - Kahn: " + solution.canFinishKahn(numCourses2, prerequisites2)); // false
        System.out.println("测试2 - DFS: " + solution.canFinishDFS(numCourses2, prerequisites2)); // false

        // 测试用例3：复杂依赖关系
        int numCourses3 = 4;
        int[][] prerequisites3 = {{1, 0}, {2, 0}, {3, 1}, {3, 2}};
        System.out.println("\n测试3 - Kahn: " + solution.canFinishKahn(numCourses3, prerequisites3)); // true
        System.out.println("测试3 - 选课顺序: " + Arrays.toString(solution.findOrder(numCourses3, prerequisites3)));
    }
}

复杂度分析

其中 V 为课程数（节点数），E 为前置依赖数（边数）。

实际应用场景

1. 编译依赖管理：如 Maven/Gradle 中模块的编译顺序确定。
2. 任务调度系统：工作流引擎中的任务执行顺序编排。
3. Makefile构建：确定文件编译的先后顺序。
4. 数据库迁移脚本：确保外键约束和表创建顺序正确。

总结

课程表问题将抽象的图论概念与实际应用场景紧密结合。通过拓扑排序，我们不仅能够判断任务是否可以全部完成，还能输出一个合法的执行顺序。理解 Kahn 算法和 DFS 三色标记法，是掌握图论算法的重要一步。