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

以你之姓@ 2023-09-27 11:44 127阅读 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 条评论，127人围观）

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

相关阅读

相关 LeetCode_拓扑排序_BFS_中等_1462.课程表 IV

目录 1.题目 2.思路 3.代码实现（Java） 1.题目你总共需要上 numCourses 门课，课程编号依次为 0 到 numCours

我就是我/ 2023年10月15日 21:12/ 0 赞/ 23 阅读

相关 LeetCode_拓扑排序_BFS_中等_210.课程表 II

目录 1.题目 2.思路 3.代码实现（Java） 1.题目现在你总共有 numCourses 门课需要选，记为 0 到 numCourses

妖狐艹你老母/ 2023年10月06日 22:37/ 0 赞/ 24 阅读

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

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

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

相关【数据结构】什么是拓扑排序—关于图的拓扑排序

目录一、什么是拓扑排序？二、拓扑排序：基本概念三、拓扑排序：分析四、拓扑排序：步骤五、拓扑排序：实现六、练习 ------------------

待我称王封你为后i/ 2023年09月26日 10:26/ 0 赞/ 15 阅读

相关图的拓扑排序

图的基本算法-拓扑序列拓扑排序拓扑排序基本算法代码示例拓扑排序对于一个有向无环图，简称DAG（Directed Acyc

我不是女神ヾ/ 2023年07月19日 04:55/ 0 赞/ 14 阅读

相关 [Leetcode][第207题][JAVA][课程表][拓扑排序][DFS]

【问题描述】\[中等\] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6L

超、凢脫俗/ 2023年03月01日 13:27/ 0 赞/ 38 阅读

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

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

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

相关有向图的拓扑排序

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

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

相关有向图拓扑排序

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

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

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

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

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