力扣207:课程表(Java拓扑排序:bfs+dfs)

简介: 力扣207:课程表(Java拓扑排序:bfs+dfs)

一、题目描述



你这个学期必须选修 numCourses 门课程,记为 0numCourses - 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] 中的所有课程对 互不相同


二、思路讲解



这是一道经典的拓扑排序问题,课程能不能修完 == 有向图中是否存在环,有向图中,一个节点的入度为他的先修课程。


2.1 方法一:广度优先搜索bfs

     

思路如下:通过bfs进行拓扑排序。利用一个队列,将入度数为0的节点加入到队列中(这些课程没有先修课程,可以访问),然后将队列中的节点依次出队,每出队一个节点,就相当于访问了这个节点(修了这门课程),就要将它在有向图中“删除”,即将它所有的出度的入度数都-1,然后将这时可能有些课程的入度数为0了,那这也是可以修的课程,也将他放入队列中。当队列为空时,拓扑排序完成,如果所有节点都访问到了,说明有向图中没有环;反之,有环。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //记录入度数
        int []indegrees = new int[numCourses];
        //出度表
        List<List<Integer>> edegree = new ArrayList<>();
        for(int i=0; i<numCourses; i++) {
            edegree.add(new ArrayList<Integer>());
        }
        //统计每个节点的出度节点  和  入度数
        for(int i=0; i<prerequisites.length; i++) {
            edegree.get(prerequisites[i][1]).add(prerequisites[i][0]);
            indegrees[prerequisites[i][0]]++;
        }
        //bfs
        Queue<Integer> queue = new LinkedList<>();
        for(int i=0; i<numCourses; i++) {
            if(indegrees[i] == 0) {
                queue.add(i);
            }
        }
        int visited = 0;    //访问节点的数量,如果和节点总数一致,说明每个节点都访问到了,有向图中不存在环
        while(!queue.isEmpty()) {
            visited++;
            int node = queue.poll();
            //把该节点的所有出度的入度数都-1,相当于把这个节点从有向图中删除
            for(int ede : edegree.get(node)) {
                indegrees[ede]--;
                //把入度数为0的节点放到队列中,这些节点是可以访问的
                if(indegrees[ede] == 0) {
                    queue.add(ede);
                }
            }
        }
        return visited==numCourses;
    }
}


时间复杂度:        O(M + N)         M为课程数,N为先修课程的要求数


空间复杂度:        O(M + N)


2.2 深度优先搜索dfs


跟bfs从入度思考相比,dfs从出度思考,更像是一种逆向思维。


思路:深度遍历判断有向图是否存在环。用visit数组记录节点的访问状态(1:当前节点正在访问; 0:未被访问; -1:被其他节点访问过)。如果当前节点的状态为-1,说明已经被其他节点访问过,已经被从有向图中“删除了”,无需考虑;而状态为1,说明是正在被访问的,则说明走了回头路,即存在环。

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        //记录每个节点的访问情况    1:当前节点正在访问; 0:未被访问; -1:被其他节点访问过
        int []visit = new int[numCourses];
        //出度表
        List<List<Integer>> edegree = new ArrayList<>();
        for(int i=0; i<numCourses; i++) {
            edegree.add(new ArrayList<Integer>());
        }
        //统计每个节点的出度节点
        for(int i=0; i<prerequisites.length; i++) {
            edegree.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        for(int i=0; i<numCourses; i++) {
            if(!dfs(edegree, visit, i)) {
                return false;
            }
        }
        return true;
    }
    boolean dfs(List<List<Integer>> edegree, int []visit, int i) {
        //如果已经被其他节点访问过,说明不需要再访问了
        if(visit[i] == -1) {
            return true;
        }
        //正在被当前节点访问,说明走了回头路,即存在环
        if(visit[i] == 1) {
            return false;
        }
        visit[i] = 1;
        //向下访问,每个出度都要走到
        for(int ede : edegree.get(i)) {
            if(!dfs(edegree, visit, ede)) {
                return false;
            }
        }
        visit[i] = -1;
        return true;
    }
}


可以把邻接表和访问状态数组设置为公共变量,减少递归传参对性能的损耗:

class Solution {
    int []visit;
    List<List<Integer>> edegree;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        visit = new int[numCourses];
        edegree = new ArrayList<>();
        for(int i=0; i<numCourses; i++) {
            edegree.add(new ArrayList<Integer>());
        }
        //统计每个节点的出度节点
        for(int i=0; i<prerequisites.length; i++) {
            edegree.get(prerequisites[i][1]).add(prerequisites[i][0]);
        }
        for(int i=0; i<numCourses; i++) {
            if(!dfs(i)) {
                return false;
            }
        }
        return true;
    }
    boolean dfs(int i) {
        if(visit[i] == -1) {
            return true;
        }
        if(visit[i] == 1) {
            return false;
        }
        visit[i] = 1;
        for(int ede : edegree.get(i)) {
            if(!dfs(ede)) {
                return false;
            }
        }
        visit[i] = -1;
        return true;
    }
}


时间复杂度:        O(M + N)         M为课程数,N为先修课程的要求数


空间复杂度:        O(M + N)

相关文章
|
1天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
7 0
|
4天前
|
人工智能 算法 BI
力扣1462.课程表
力扣1462.课程表
|
4天前
|
算法
力扣630.课程表
力扣630.课程表
|
9天前
|
消息中间件 Java Kafka
Java大文件排序(有手就能学会),kafka面试题2024
Java大文件排序(有手就能学会),kafka面试题2024
|
10天前
|
存储 算法 搜索推荐
【Java高阶数据结构】图补充-拓扑排序
【Java高阶数据结构】图补充-拓扑排序
13 1
|
10天前
|
搜索推荐 Java Shell
8大Java排序方法(由简入繁),有代码详解和原理指导
8大Java排序方法(由简入繁),有代码详解和原理指导
34 0
|
10天前
|
监控 搜索推荐 算法
Java排序:原理、实现与应用
【4月更文挑战第28天】本文探讨了Java中的排序算法,包括原理和实现。Java利用Comparator接口进行元素比较,通过Arrays和Collections类的sort方法对数组和列表进行排序。示例展示了使用这些方法的基本代码。此外,还讨论了冒泡排序算法和自定义排序场景,以适应不同需求。理解这些排序机制有助于提升程序效率。
15 1
|
1天前
|
安全 Java 大数据
Java多线程编程:深入理解与应用
Java多线程编程:深入理解与应用
|
1天前
|
安全 Java 数据安全/隐私保护
Java中的多线程编程:基础知识与实践
【5月更文挑战第24天】 在现代软件开发中,多线程编程是提升应用性能和响应速度的关键技术之一。Java 作为一种广泛使用的编程语言,其内置的多线程功能为开发者提供了强大的并发处理能力。本文将深入探讨 Java 多线程的基础概念、实现机制以及在实际开发中的应用。我们将从线程的创建和管理出发,逐步讲解同步机制、死锁问题以及如何利用高级并发工具有效地构建稳定、高效的多线程应用。通过理论结合实例的方式,旨在帮助读者掌握 Java 多线程编程的核心技能,并在实际项目中灵活运用。
|
1天前
|
缓存 安全 Java
JAVA多线程编程与并发控制
```markdown Java多线程编程与并发控制关键点:1) 通过Thread或Runnable创建线程,管理线程状态;2) 使用synchronized关键字和ReentrantLock实现线程同步,防止数据竞争;3) 利用线程池(如Executors)优化资源管理,提高系统效率。并发控制需注意线程安全,避免死锁,确保程序正确稳定。 ```

热门文章

最新文章