课程表排序问题，图的拓扑排序！

以你之姓@ 2023-09-27 11:44 88阅读 0赞

## 题目描述： ##

![22a681e2b679464f91791cabc480c0f3.png][]

#### 题解： ####

class Solution {
        //本题是求图的拓扑排序
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            List<List<Integer>> list=new ArrayList<>();//用于构造邻接表
            int[] count=new int[numCourses];//用于统计每个顶点的入度数
            //初始化邻接表
            for(int i=0;i<numCourses;i++){
                list.add(new ArrayList<Integer>());
            }
            //开始构造邻接表和统计入度数
            for(int[] pre:prerequisites){
                list.get(pre[1]).add(pre[0]);//完成pre[0]前先完成pre[1]
                count[pre[0]]++;//pre[0]的入度+1；
            }
            Queue<Integer> queue=new LinkedList<Integer>();
            //将度为0的顶点入列
            for(int i=0;i<numCourses;i++){
                if(count[i]==0){
                    queue.offer(i);
                }
            }
            int[] res=new int[numCourses];//存放学完的课程
            int index=0;
            while(!queue.isEmpty()){
                int v=queue.poll();//顶点出列
                res[index++]=v;
                for(int u:list.get(v)){//v顶点可以到达的其它顶点
                    count[u]--;
                    if(count[u]==0){
                        queue.offer(u);
                   }
                }
            }
            return index==numCourses?res:new int[0];
        }
    }

[22a681e2b679464f91791cabc480c0f3.png]: https://img-blog.csdnimg.cn/22a681e2b679464f91791cabc480c0f3.png

发表评论取消回复

表情：

评论列表（有 0 条评论，88人围观）

还没有评论，来说两句吧...

相关阅读

相关课程表排序问题，图的拓扑排序！

题目描述： ![22a681e2b679464f91791cabc480c0f3.png][] 题解： class Solution {

以你之姓@/ 2023年09月27日 11:44/ 0 赞/ 89 阅读

相关有向图的拓扑排序

一.拓扑排序的步骤如下 1.输出AOV网中没有前驱节点的节点。 2.在AOV网中删除该节点以及对应的出边。 3.重复上述步骤，直到所有节点都输出为止，完成的拓扑排序

秒速五厘米/ 2022年12月28日 00:42/ 0 赞/ 159 阅读

相关【拓扑排序（Topological Sorting）——图】

拓扑排序（Topological Sorting）一、基本概念二、拓扑排序的过程三、拓扑排序的实现 1、设计数据结构

Bertha 。/ 2022年12月21日 06:09/ 0 赞/ 153 阅读

相关有向图的拓扑排序

有向图的拓扑排序本文取自《数据结构与算法》(C语言版)(第三版)，出版社是清华大学出版社。本博文作为学习资料整理。源代码是VC++ 6.0上可执行程序，我挪到了VS20

柔光的暖阳◎/ 2022年08月21日 04:45/ 0 赞/ 158 阅读

相关拓扑排序

在这里我们引入AOV（Activity-On-Vertex）网，图的顶点代表活动，其有向边<Vi,Vj>代表完成Vj之前Vi必须先完成。对于一个工程，我们首先将这

野性酷女/ 2022年06月10日 13:28/ 0 赞/ 199 阅读

相关图的拓扑排序及其应用

拓扑排序的定义对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。通常

逃离我推掉我的手/ 2022年06月04日 05:47/ 0 赞/ 212 阅读

相关有向图拓扑排序

// // main.cpp // Tu // // Created by 李奕昕 on 2018/6/16. // Copyr

绝地灬酷狼/ 2022年05月22日 08:27/ 0 赞/ 214 阅读

相关数据结构——图——拓扑排序

在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序（英语：Topological sorting）。（1）每个顶点出现且只出现一次

Bertha 。/ 2022年04月12日 05:07/ 0 赞/ 243 阅读

相关 DAG图中的拓扑排序

拓扑排序概念思想代码应用概念 > DAG是指有向无环图，而拓扑排序是有向无环图的一个具体应用。拓扑

港控/mmm°/ 2021年09月21日 06:18/ 0 赞/ 266 阅读

相关拓扑排序

作用：判断是否存在环 1.数组模拟队列 include <iostream> include <vector> include <cst

喜欢ヅ旅行/ 2021年06月22日 15:37/ 0 赞/ 478 阅读