【BFS拓扑排序】207. 课程表

2024-02-14 14:04
文章标签 bfs 排序 拓扑 课程表 207

本文主要是介绍【BFS拓扑排序】207. 课程表,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

207. 课程表

解题思路

  • 首先构建了一个 inDegree 哈希表,用于存储每门课程的入度,即有多少课程依赖当前课程。

  • 构建了一个 adj 哈希表,用于存储每门课程所依赖的其他课程。这个结构可以理解为一个邻接表,对于每门课程,存储了其所有的前置课程。

  • 根据给定的课程依赖关系数组 prerequisites,更新了每门课程的入度和依赖关系。

  • 初始化一个队列 q,将所有入度为 0 的课程加入队列。这些课程是没有任何先修课程的课程,可以直接学习。

  • 开始一个循环,每次从队列中取出一门课程,表示这门课程被选择学习。然后遍历其邻接表中的课程,将这些课程的入度减 1,并将入度减为 0 的课程加入队列,表示这些课程可以被学习了。

  • 最后,遍历所有课程的入度,如果存在入度不为 0 的课程,说明存在环路,直接返回 false,表示无法完成所有课程的学习;否则返回 true,表示能够完成所有课程的学习。

class Solution {public boolean canFinish(int numCourses, int[][] prerequisites) {// 先让入度为0 的课入队// 然后逐个出队 出队的课代表被选择,然后减小相关课程的入度// 如果相关课的入度为0 安排出队// 课程号和对应的入度Map<Integer,Integer> inDegree = new HashMap<>();// 将所有的课程先放入for(int i = 0; i < numCourses; i++){inDegree.put(i,0);}// 依赖关系 计算每一门课程所依赖的前面的课程// cur 依赖pre cur1依赖 pre 那么 pre ,(cur,cur1)Map<Integer,List<Integer>>  adj = new HashMap<>();// 初始化入度和依赖的关系for(int[] relate: prerequisites){// 想要学cur 必须先完成pre 也就是cur 依赖pre pre指向cur  作为cur的一个入度int cur  = relate[0];int pre = relate[1];// 更新入度inDegree.put(cur,inDegree.get(cur) + 1);// 入度 + 1if(!adj.containsKey(pre)){// 如果不存在依赖关系 先初始化adj.put(pre,new ArrayList<>());}adj.get(pre).add(cur);}Queue<Integer> q = new LinkedList<>();// 将所有入度为0 的全部入队for(int key:inDegree.keySet()){if(inDegree.get(key) == 0){q.offer(key);}}// 取出一个节点 对应学习这门课程// 遍历当前邻接表 更新其入度  更新之后 查看入度 如果为0 加入到队列while(!q.isEmpty()){int cur = q.poll();// 取出当前课程// 查看当前课程是否存在邻接表if(!adj.containsKey(cur)){continue;}List<Integer> successorList = adj.get(cur);// 取出它的邻接表// 遍历所有的需要依赖当前课程cur 的所有课程for(int k: successorList){// 依赖cur的课程 入度减小1inDegree.put(k,inDegree.get(k) - 1);// 入度减小1// 当依赖cur的课程 入度减小为1的时候  直接入队if(inDegree.get(k) == 0){q.offer(k);}}}// 遍历队列 如果还有课程的入度不为0 说明存在环路 直接falsefor(int key:inDegree.keySet()){if(inDegree.get(key) != 0){return false;}}return true;}
}

这篇关于【BFS拓扑排序】207. 课程表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/708692

相关文章

hdu1254(嵌套bfs,两次bfs)

/*第一次做这种题感觉很有压力,思路还是有点混乱,总是wa,改了好多次才ac的思路:把箱子的移动当做第一层bfs,队列节点要用到当前箱子坐标(x,y),走的次数step,当前人的weizhi(man_x,man_y),要判断人能否将箱子推到某点时要嵌套第二层bfs(人的移动);代码如下:

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

poj 2195 bfs+有流量限制的最小费用流

题意: 给一张n * m(100 * 100)的图,图中” . " 代表空地, “ M ” 代表人, “ H ” 代表家。 现在,要你安排每个人从他所在的地方移动到家里,每移动一格的消耗是1,求最小的消耗。 人可以移动到家的那一格但是不进去。 解析: 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了,先抽象出源点s和汇点t。 令源点与每个人相连,容量为1,费用为

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible

【软考】希尔排序算法分析

目录 1. c代码2. 运行截图3. 运行解析 1. c代码 #include <stdio.h>#include <stdlib.h> void shellSort(int data[], int n){// 划分的数组,例如8个数则为[4, 2, 1]int *delta;int k;// i控制delta的轮次int i;// 临时变量,换值int temp;in

深度优先(DFS)和广度优先(BFS)——算法

深度优先 深度优先搜索算法(英语:Depth-First-Search,DFS)是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点,尽可能深的搜索树的分支,当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点,则选择其中一个作为源节点并重复以上过程,整个进程反复进行直到所有节点都被访

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图