每日OJ题_BFS解决拓扑排序①_力扣207. 课程表

2024-04-24 05:36

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

目录

拓扑排序和图的介绍

①力扣207. 课程表

解析代码


拓扑排序和图的介绍

        拓扑排序简单来说就是找到做事情的先后顺序(拓扑排序的结果可能不是唯一的)。

学习拓扑排序前先简单学习图的基本概念:

 图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E),其中:

  • 顶点集合V = {x|x属于某个数据对象集}是有穷非空集合;
  • E = {(x,y)|x,y属于V}或者E = {<x, y>|x,y属于V && Path(x, y)}是顶点间关系的有穷集合,也叫做边的集合。
  • (x, y)表示x到y的一条双向通路,即(x, y)是无方向的;Path(x, y)表示从x到y的一条单向通路,即Path(x, y)是有方向的。
  • 顶点和边:图中结点称为顶点,第i个顶点记作vi。两个顶点vi和vj相关联称作顶点vi和顶点vj之间有一条边,图中的第k条边记作ek,ek = (vi,vj)或<vi,vj>。
  • 有向图和无向图:在有向图中,顶点对<x, y>是有序的,顶点对<x,y>称为顶点x到顶点y的一条边(弧),<x, y>和<y, x>是两条不同的边,比如下图G3和G4为有向图。在无向图中,顶点对(x, y)是无序的,顶点对(x,y)称为顶点x和顶点y相关联的一条边,这条边没有特定方向,(x, y)和(y,x)是同一条边,比如下图G1和G2为无向图。注意:无向边(x, y)等于有向边<x, y>和<y, x>。

入度和出度

图中的度:所谓顶点的度(degree),就是指和该顶点相关联的边数。在有向图中,度又分为入度和出度。

  • 入度 (in-degree) :以某顶点为弧头,终止于该顶点的边的数目称为该顶点的入度。
  • 出度 (out-degree) :以某顶点为弧尾,起始于该顶点的弧的数目称为该顶点的出度。

邻接表

        邻接表存储方法跟树的孩子链表示法相类似,是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点,则把相邻顶点依次存放于表头结点所指向的单向链表中。

  • 在有向图中,描述每个点向别的节点连的边(点a->点b这种情况)。
  • 在无向图中,描述每个点所有的边(点a-点b这种情况)

有向图邻接表存储


下面是拓扑排序的概念:

        一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程的开始是以它的所有前序子工程的结束为先决条件的,但有些子工程没有先决条件,可以安排在任何时间开始。为了形象地反映出整个工程中各个子工程(活动)之间的先后关系,可用一个有向图来表示,图中的顶点代表活动(子工程),图中的有向边代表活动的先后关系,即有向边的起点的活动是终点活动的前序活动,只有当起点活动完成之后,其终点活动才能进行。通常,我们把这种顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network),简称AOV网。

        在AOV网中,若不存在回路,则所有活动可排列成一个线性序列,使得每个活动的所有前驱活动都排在该活动的前面,我们把此序列叫做拓扑序列(Topological order),由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的,满足上述定义的任一线性序列都称作它的拓扑序列。

对于有向图的拓扑排序,我们可以使用如下思路输出拓扑序(BFS 方式):

  1. 起始时,将所有入度为 0 的节点进行入队(入度为 0,说明没有边指向这些节点,将它们放到拓扑排序的首部,不会违反拓扑序定义)。
  2. 从队列中进行节点出队操作,出队序列就是对应我们输出的拓扑序。对于当前弹出的节点 x,遍历x 的所有出度y,即遍历所有由 x直接指向的节点y,对y做入度减一操作(因为x节点已经从队列中弹出,被添加到拓扑序中,等价于x节点从有向图中被移除,相应的由x发出的边也应当被删除,带来的影响是与 x相连的节点y的入度减一)。
  3. 对y进行入度减一之后,检查 y的入度是否为0,如果为0则将y入队(当y的入度为0,说明有向图中在y前面的所有的节点均被添加到拓扑序中,此时 可以作为拓扑序的某个片段的首部被添加,而不是违反拓扑序的定义)。
  4. 循环流程 2、3 直到队列为空。

①力扣207. 课程表

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 。这是可能的。

示例 2:

输入:numCourses = 2, prerequisites = [[1,0],[0,1]]
输出:false
解释:总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0 ;并且学习课程 0 之前,你还应先完成课程 1 。这是不可能的。

提示:

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= 5000
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • prerequisites[i] 中的所有课程对 互不相同
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {}
};

解析代码

原问题可以转换成一个拓扑排序问题。用BFS 解决拓扑排序即可。

  • 将所有入度为 0 的点加入到队列中。
  • 当队列不空的时候,一直循环以下三步:
  1. 取出队头元素。
  2. 将于队头元素相连的顶点的入度 - 1。
  3. 然后判断是否减成 0。如果减成 0,就加入到队列中。
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {unordered_map<int, vector<int>> edges; // 领接表vector<int> in(numCourses, 0); // 存储每一个结点的入度for(auto& e : prerequisites) // 1. 建图{int a = e[0], b = e[1];; // b指向aedges[b].push_back(a);in[a]++;}queue<int> q; // 2. BFS解决拓扑排序for(int i = 0; i < numCourses; ++i){if(in[i] == 0)q.push(i);}while(!q.empty()) // 层序遍历{int tmp = q.front();q.pop();for(auto& e : edges[tmp]) // 得到tmp指向的顶点, 删掉一个入度{in[e]--;if(in[e] == 0)q.push(e);}}for(auto& e : in) // 3. 判断是否有环{if(e != 0)return false;}return true;}
};

这篇关于每日OJ题_BFS解决拓扑排序①_力扣207. 课程表的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

Spring事务中@Transactional注解不生效的原因分析与解决

《Spring事务中@Transactional注解不生效的原因分析与解决》在Spring框架中,@Transactional注解是管理数据库事务的核心方式,本文将深入分析事务自调用的底层原理,解释为... 目录1. 引言2. 事务自调用问题重现2.1 示例代码2.2 问题现象3. 为什么事务自调用会失效3

mysql出现ERROR 2003 (HY000): Can‘t connect to MySQL server on ‘localhost‘ (10061)的解决方法

《mysql出现ERROR2003(HY000):Can‘tconnecttoMySQLserveron‘localhost‘(10061)的解决方法》本文主要介绍了mysql出现... 目录前言:第一步:第二步:第三步:总结:前言:当你想通过命令窗口想打开mysql时候发现提http://www.cpp

SpringBoot启动报错的11个高频问题排查与解决终极指南

《SpringBoot启动报错的11个高频问题排查与解决终极指南》这篇文章主要为大家详细介绍了SpringBoot启动报错的11个高频问题的排查与解决,文中的示例代码讲解详细,感兴趣的小伙伴可以了解一... 目录1. 依赖冲突:NoSuchMethodError 的终极解法2. Bean注入失败:No qu

springboot报错Invalid bound statement (not found)的解决

《springboot报错Invalidboundstatement(notfound)的解决》本文主要介绍了springboot报错Invalidboundstatement(not... 目录一. 问题描述二.解决问题三. 添加配置项 四.其他的解决方案4.1 Mapper 接口与 XML 文件不匹配

Python中ModuleNotFoundError: No module named ‘timm’的错误解决

《Python中ModuleNotFoundError:Nomodulenamed‘timm’的错误解决》本文主要介绍了Python中ModuleNotFoundError:Nomodulen... 目录一、引言二、错误原因分析三、解决办法1.安装timm模块2. 检查python环境3. 解决安装路径问题

如何解决mysql出现Incorrect string value for column ‘表项‘ at row 1错误问题

《如何解决mysql出现Incorrectstringvalueforcolumn‘表项‘atrow1错误问题》:本文主要介绍如何解决mysql出现Incorrectstringv... 目录mysql出现Incorrect string value for column ‘表项‘ at row 1错误报错

如何解决Spring MVC中响应乱码问题

《如何解决SpringMVC中响应乱码问题》:本文主要介绍如何解决SpringMVC中响应乱码问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Spring MVC最新响应中乱码解决方式以前的解决办法这是比较通用的一种方法总结Spring MVC最新响应中乱码解

Java报NoClassDefFoundError异常的原因及解决

《Java报NoClassDefFoundError异常的原因及解决》在Java开发过程中,java.lang.NoClassDefFoundError是一个令人头疼的运行时错误,本文将深入探讨这一问... 目录一、问题分析二、报错原因三、解决思路四、常见场景及原因五、深入解决思路六、预http://www

pip无法安装osgeo失败的问题解决

《pip无法安装osgeo失败的问题解决》本文主要介绍了pip无法安装osgeo失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 进入官方提供的扩展包下载网站寻找版本适配的whl文件注意:要选择cp(python版本)和你py

SpringBoot项目启动报错"找不到或无法加载主类"的解决方法

《SpringBoot项目启动报错找不到或无法加载主类的解决方法》在使用IntelliJIDEA开发基于SpringBoot框架的Java程序时,可能会出现找不到或无法加载主类com.example.... 目录一、问题描述二、排查过程三、解决方案一、问题描述在使用 IntelliJ IDEA 开发基于