【算法】BFS系列之 拓扑排序

【ps】本篇有 3 道 leetcode OJ。 

目录

一、算法简介

二、相关例题

1）课程表

.1- 题目解析

.2- 代码编写

2）课程表 II

.1- 题目解析

.2- 代码编写

3）火星词典

.1- 题目解析

.2- 代码编写

一、算法简介

【补】图的基本概念

（1）图是由顶点集合及顶点间的关系组成的一种数据结构：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>。

（2）入度和出度

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

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

（3）邻接表

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

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

（4）有向图邻接表存储

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

        一个较大的工程往往被划分成许多子工程，我们把这些子工程称作活动（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 直到队列为空。

        至于如何建图，请见下文例题。

二、相关例题

1）课程表

207. 课程表

.1- 题目解析

        不难看出，这些课程可以构成一个有向无环图，本题其实在问，这些课程构成的有向无环图中是否有环，换句话说，是否可以进行拓扑排序。

        那么，用 BFS 来实现拓扑排序即可。

 

.2- 代码编写

class Solution {
public:bool canFinish(int n, vector<vector<int>>& prerequisites) {unordered_map<int,vector<int>> edges; //用容器（邻接表）建图vector<int> in(n); //标识每一个点的入度//1.遍历原始数组建图for(auto& e:prerequisites){int a=e[0],b=e[1]; //b -> aedges[b].push_back(a); //把b指向a的这条边添加入邻接表in[a]++; //统计入度}//2.BFS实现拓扑排序queue<int> q;//1）把所有入度为0的点入队for(int i=0;i<n;i++){if(in[i]==0)q.push(i);}//2）进行BFSwhile(q.size()){int t=q.front();q.pop();for(int a: edges[t]) //遍历t连接的点{in[a]--; //修改点的入度，相当于删除点if(in[a]==0)q.push(a); //继续将入度为0的点入队}}//3，判断是否有环for(int i=0;i<n;i++)if(in[i])return false;//拓扑排序之后，每个点的入度都应为0return true;}};

2）课程表 II

210. 课程表 II

.1- 题目解析

        本题与上道题类似，也是用 BFS 实现拓扑排序，但与上道题判断是否有环不同，本题返回的是拓扑排序的一种结果。

.2- 代码编写

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>> edges(numCourses);//用容器（邻接表）存图vector<int> in(numCourses);           //统计入度//1.建图for(auto& v:prerequisites){int a=v[0],b=v[1]; // b -> aedges[b].push_back(a);in[a]++;}//2.BFS实现拓扑排序queue<int> q;vector<int> ret;for(int i=0;i<numCourses;i++){if(in[i]==0)q.push(i);}while(q.size()){int t=q.front();q.pop();ret.push_back(t);//记录拓扑排序的结果for(int a:edges[t]){in[a]--;if(in[a]==0)q.push(a);}}if(ret.size()==numCourses)return ret;else return {};}
};

3）火星词典

LCR 114. 火星词典

.1- 题目解析

        本题是在问，判断有向图是否有环，因此可以用 BFS 实现拓扑排序来解决。

        特别的，如何搜集信息（如何建图）？——

  1. 两层 for 循环枚举出所有的两个字符串的组合。
  2. 利用指针，根据字典序规则找出信息。

 

.2- 代码编写

class Solution {unordered_map<char,unordered_set<char>> edges;//用容器（邻接表）存图unordered_map<char,int> in;                   //统计入度bool check;                                   //处理边界情况
public:string alienOrder(vector<string>& words) {//1.建图+初始化入度哈希表for(auto& s:words)for(auto ch:s)in[ch]=0;//2.搜集信息int n=words.size();for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){add(words[i],words[j]);//添加信息if(check)//处理边界情况return "";}//3.拓扑排序queue<char> q;for(auto& [a,b]:in) {if(b==0)q.push(a);}string ret; //统计结果while(q.size()){char t=q.front();q.pop();ret+=t;for(char ch:edges[t]){if(--in[ch]==0)q.push(ch);}}//4.判断是否有环for(auto& [a,b]:in)if(b!=0)return "";return ret;}void add(string& s1,string& s2){int n=min(s1.size(),s2.size());int i=0;for(;i<n;i++){if(s1[i]!=s2[i]){char a=s1[i],b=s2[i]; //a -> bif(!edges.count(a) || !edges[a].count(b)) //a没有存过，或a存过但a里没存过b的信息{edges[a].insert(b);in[b]++;}break;}}if(i==s2.size() && i<s1.size())//s1的长度大于s2，就无需进行拓扑排序了check=true;}
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/1542407.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

HTML翻牌器：用CSS和HTML元素创造动态数字展示

HTML翻牌器：用CSS和HTML元素创造动态数字展示

HTML翻牌器&#xff1a;用CSS和HTML元素创造动态数字展示 前言 翻牌器是一种数字动态展示形式&#xff0c;在生活中常见的例如翻牌计分、翻牌时钟等。 之所以以翻牌的形式是因为其物理设计的原因使其只能滚动翻牌展示数字&#xff0c;在电子显示设备不普及时&#xff0c;使用…
阅读更多...
Leetcode - 139双周赛

Leetcode - 139双周赛

目录 一&#xff0c;3285. 找到稳定山的下标 二&#xff0c;3286. 穿越网格图的安全路径 三&#xff0c;3287. 求出数组中最大序列值 四&#xff0c;3288. 最长上升路径的长度 一&#xff0c;3285. 找到稳定山的下标 本题就是找[0&#xff0c; n-2]中&#xff0c;height[i]…
阅读更多...
C++入门12——详解多态2

C++入门12——详解多态2

上篇文章&#xff08;C入门12——详解多态1&#xff09;中&#xff0c;我们介绍了C多态的概念和用法&#xff0c;但是只知其然而不知其所以然是万万不行的&#xff0c;所以本篇文章将从探案的角度详细介绍多态的原理。 1. 虚函数表 想要弄懂多态的原理&#xff0c;首先要了解一…
阅读更多...
数据结构与算法学习day22-回溯算法-分割回文串、复原IP地址、子集

数据结构与算法学习day22-回溯算法-分割回文串、复原IP地址、子集

一、分割回文串 1.题目 131. 分割回文串 - 力扣&#xff08;LeetCode&#xff09; 2.思路 分割回文串可以抽象为一棵树形结构。 递归用来纵向遍历&#xff0c;for循环用来横向遍历&#xff0c;切割线&#xff08;就是图中的红线&#xff09;切割到字符串的结尾位置&#xf…
阅读更多...
STM32F407单片机编程入门(十三) 单片机IAP(在应用编程)详解及实战源码

STM32F407单片机编程入门(十三) 单片机IAP(在应用编程)详解及实战源码

文章目录 一.概要二.STM32F407VET6单片机IAP介绍1.STM32F407VET6单片机IAP基本原理2.STM32F407VET6单片机IAP基本流程 三.配置一个BOOT工程四.配置一个APP工程五.工程源代码下载六.小结 一.概要 STM32单片机程序升级方法有很多种&#xff0c;主要有以下几种&#xff1a; 1.将…
阅读更多...
【LeetCode】146. LRU缓存

【LeetCode】146. LRU缓存

1.题目 2.思想 3.代码 3.1 代码1 下面这是一版错误的代码。错误的原因在于逻辑不正确导致最后的代码也是不正确的。 class LRUCache:def __init__(self, capacity: int):self.time 0 # 用于全局记录访问的时间self.num2time {} # 数字到时间的映射self.key2val {} # 数字…
阅读更多...
如何理解MVCC

如何理解MVCC

MVCC是什么&#xff1f; MVCC&#xff0c;是MultiVersion Concurrency Control的缩写&#xff0c;翻译成中文就是多版本并发控制&#xff0c;多个事务同时访问同一数据时&#xff0c;调控每一个事务获取到数据的具体版本。和数据库锁一样&#xff0c;它也是一种并发控制的解决…
阅读更多...
实时同步 解决存储问题 sersync

实时同步 解决存储问题 sersync

目录 1.sersync服务 2.sersync同步整体架构 ​编辑 3.rsync服务准备 4.sersync部署使用 5.修改配置文件 6.启动sersync 7.接入nfs服务 8.联调测试 1.sersync服务 sersync服务其实就是由两个服务组成一个是inotify服务和rsync服务组成 inotify服务用来监控那个…
阅读更多...
Infineon——TC397 Multicore简介

Infineon——TC397 Multicore简介

文章目录 前言一、TC397简介二、命名规则三、多核开发建议 前言 AURIX™ TC3xx微控制器架构具有多达6个独立的处理器内核CPU0…CPU5, 可在一个统一平台上无缝托管多个应用程序和操作系统. 由于实现了具有独立读取接口的多个程序Flash模块, 该架构支持进一步的实时处理. AURIX™…
阅读更多...
自学笔记之TVM编译器框架 ，核心特性，模型优化概述，AI应用落地

自学笔记之TVM编译器框架 ，核心特性，模型优化概述，AI应用落地

最近在学习一些和芯片 AI相关的知识&#xff0c;重点了解了一下TVM&#xff0c;我自己认为TVM在AI应用落地类似的项目中&#xff0c;用途还是非常广泛的&#xff0c;现在把一些重要的笔记贴在下面&#xff0c;有两篇原帖链接也附上&#xff0c;感兴趣的同学可以学习一下。 TVM…
阅读更多...
小球轻重的测量

小球轻重的测量

设有12个小球。其中11个小球的重量相同&#xff0c;称为好球&#xff1b;有一个小球的重量与11个好球的重量不同&#xff08;或轻或重&#xff09;&#xff0c;称这个小球为坏球。试编写一个算法&#xff0c;用一个无砝码的天平称三次找出这个坏球&#xff0c;并确定其比好球轻…
阅读更多...
SpringCloud入门（五）Nacos注册中心（上）

SpringCloud入门（五）Nacos注册中心（上）

国内公司一般都推崇阿里巴巴的技术&#xff0c;比如注册中心&#xff0c;SpringCloudAlibaba也推出了一个名为Nacos的注册中心。Dynami Naming and Configuration Service。是阿里巴巴2018年7月开源的项目。 Nacos是阿里巴巴的产品&#xff0c;现在是SpringCloud中的一个组件。…
阅读更多...
智谱清影 - CogVideoX-2b-部署与使用

智谱清影 - CogVideoX-2b-部署与使用

&#x1f351;个人主页&#xff1a;Jupiter. &#x1f680; 所属专栏&#xff1a;Linux从入门到进阶 欢迎大家点赞收藏评论&#x1f60a; 目录 体验地址&#xff1a;[丹摩DAMODEL官网](https://www.damodel.com/console/overview) CogVideoX 简介本篇将详细介绍使用丹摩服务器部…
阅读更多...
网络通信——OSI七层模型和TCP/IP模型

网络通信——OSI七层模型和TCP/IP模型

OSI模型 一.OSI七层模型 OSI&#xff08;Open System Interconnect&#xff09;七层模型是一种将计算机网络通信协议划分为七个不同层次的标准化框架。每一层都负责不同的功能&#xff0c;从物理连接到应用程序的处理。这种模型有助于不同的系统之间进行通信时&#xff0c;更…
阅读更多...
KamaCoder 103. 水流问题

KamaCoder 103. 水流问题

题目要求 N*M的矩阵&#xff0c;数值代表位置的相对高度。矩阵模拟了一个地形&#xff0c;当雨水落上时&#xff0c;会根据地形倾斜向低处流动。但是只能从较高或等高的地点流向较低或等高并且相邻的地点&#xff0c;我们的目标是确定那些单元格&#xff0c;从这些单元格出发的…
阅读更多...
Vue(14)——组合式API①

Vue(14)——组合式API①

setup 特点&#xff1a;执行实际比beforeCreate还要早&#xff0c;并且获取不到this <script> export default{setup(){console.log(setup函数);},beforeCreate(){console.log(beforeCreate函数);} } </script> 在setup函数中提供的数据和方法&#xff0c;想要在…
阅读更多...
101. 对称二叉树(共含三道leetcode题）

101. 对称二叉树(共含三道leetcode题）

文章目录 101. 对称二叉树递归法迭代法 小结100.相同的树572.另一个树的子树 101. 对称二叉树 101. 对称二叉树 给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true示例 2&#…
阅读更多...
Administration Console后台弱⼝令登录

Administration Console后台弱⼝令登录

1.环境搭建 cd vulhub-master/iboss/CVE-2017-12149 docker-compose up-d 2.访问登录页面 JBoss AS 6 Admin Consolehttp://47.121.211.205:8080/admin-console/login.seam?conversationId4用户名admin 密码vulhub 3.上传war文件 4.访问上传文件并进行连接 访问上传文件 使…
阅读更多...
kubectl 执行一条命令之后发生了什么？

kubectl 执行一条命令之后发生了什么？

kubectl 是与 Kubernetes 集群交互的命令行工具&#xff0c;用户通过它可以对集群资源进行操作和管理。你有没有想过&#xff0c;当我们执行一条 kubectl 命令之后&#xff0c;背后都发生了什么&#xff1f; 详细过程 kubectl -> kube-api-server 根据通信类型&#xff0…
阅读更多...
算法题之宝石与石头

算法题之宝石与石头

宝石与石头 给你一个字符串 jewels 代表石头中宝石的类型&#xff0c;另有一个字符串 stones 代表你拥有的石头。 stones 中每个字符代表了一种你拥有的石头的类型&#xff0c;你想知道你拥有的石头中有多少是宝石。 字母区分大小写&#xff0c;因此 "a" 和 "…
阅读更多...
最新文章

Copyright @ 2022~2023