【图论】Leetcode 207. 课程表【中等】-Toy模板网

这篇具有很好参考价值的文章主要介绍了【图论】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));
    }
}

时间空间复杂度

时间复杂度：O(V + E)，其中 V 表示课程数量，E 表示先修课程的数量，因为需要构建邻接表和统计入度，以及进行BFS拓扑排序。
空间复杂度：O(V + E)，其中 V 表示课程数量，E 表示先修课程的数量，因为需要存储邻接表和入度数组。文章来源地址https://www.toymoban.com/news/detail-851570.html

到了这里，关于【图论】Leetcode 207. 课程表【中等】的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！