代码随想录算法训练营第五十八天 | 拓扑排序精讲-软件构建
目录
软件构建
思路
拓扑排序的背景
拓扑排序的思路
模拟过程
判断有环
写代码
方法一: 拓扑排序
软件构建
- 题目链接:卡码网:117. 软件构建
文章讲解:代码随想录
某个大型软件项目的构建系统拥有 N 个文件,文件编号从 0 到 N - 1,在这些文件中,某些文件依赖于其他文件的内容,这意味着如果文件 A 依赖于文件 B,则必须在处理文件 A 之前处理文件 B (0 <= A, B <= N - 1)。请编写一个算法,用于确定文件处理的顺序。
输入描述:
第一行输入两个正整数 N, M。表示 N 个文件之间拥有 M 条依赖关系。
后续 M 行,每行两个正整数 S 和 T,表示 T 文件依赖于 S 文件。
输出描述:
输出共一行,如果能处理成功,则输出文件顺序,用空格隔开。
如果不能成功处理(相互依赖),则输出 -1。
输入示例:
5 4 0 1 0 2 1 3 2 4
输出示例:
0 1 2 3 4
提示信息:
文件依赖关系如下:
所以,文件处理的顺序除了示例中的顺序,还存在
0 2 4 1 3
0 2 1 3 4
等等合法的顺序。
数据范围:
- 0 <= N <= 10 ^ 5
- 1 <= M <= 10 ^ 9
思路
拓扑排序的背景
本题是拓扑排序的经典题目。
一聊到 拓扑排序,一些录友可能会想这是排序,不会想到这是图论算法。
其实拓扑排序是经典的图论问题。
先说说 拓扑排序的应用场景。
大学排课,例如 先上A课,才能上B课,上了B课才能上C课,上了A课才能上D课,等等一系列这样的依赖顺序。 问给规划出一条 完整的上课顺序。
拓扑排序在文件处理上也有应用,我们在做项目安装文件包的时候,经常发现 复杂的文件依赖关系, A依赖B,B依赖C,B依赖D,C依赖E 等等。
如果给出一条线性的依赖顺序来下载这些文件呢?
有录友想上面的例子都很简单啊,我一眼能给排序出来。
那如果上面的依赖关系是一百对呢,一千对甚至上万个依赖关系,这些依赖关系中可能还有循环依赖,你如何发现循环依赖呢,又如果排出线性顺序呢。
所以 拓扑排序就是专门解决这类问题的。
概括来说,给出一个 有向图,把这个有向图转成线性的排序 就叫拓扑排序。
当然拓扑排序也要检测这个有向图 是否有环,即存在循环依赖的情况,因为这种情况是不能做线性排序的。
所以拓扑排序也是图论中判断有向无环图的常用方法。
拓扑排序的思路
拓扑排序指的是一种 解决问题的大体思路, 而具体算法,可能是广搜也可能是深搜。
大家可能发现 各式各样的解法,纠结哪个是拓扑排序?
其实只要能在把 有向无环图 进行线性排序 的算法 都可以叫做 拓扑排序。
实现拓扑排序的算法有两种:卡恩算法(BFS)和DFS
卡恩1962年提出这种解决拓扑排序的思路
一般来说我们只需要掌握 BFS (广度优先搜索)就可以了,清晰易懂,如果还想多了解一些,可以再去学一下 DFS 的思路,但 DFS 不是本篇重点。
接下来我们来讲解BFS的实现思路。
以题目中示例为例如图:
做拓扑排序的话,如果肉眼去找开头的节点,一定能找到 节点0 吧,都知道要从节点0 开始。
但为什么我们能找到 节点0呢,因为我们肉眼看着 这个图就是从 节点0出发的。
作为出发节点,它有什么特征?
你看节点0 的入度 为0 出度为2, 也就是 没有边指向它,而它有两条边是指出去的。
节点的入度表示 有多少条边指向它,节点的出度表示有多少条边 从该节点出发。
所以当我们做拓扑排序的时候,应该优先找 入度为 0 的节点,只有入度为0,它才是出发节点。 理解以上内容很重要!
接下来我给出 拓扑排序的过程,其实就两步:
- 找到入度为0 的节点,加入结果集
- 将该节点从图中移除
循环以上两步,直到 所有节点都在图中被移除了。
结果集的顺序,就是我们想要的拓扑排序顺序 (结果集里顺序可能不唯一)
模拟过程
用本题的示例来模拟这一过程:
1、找到入度为0 的节点,加入结果集
2、将该节点从图中移除
1、找到入度为0 的节点,加入结果集
这里大家会发现,节点1 和 节点2 入度都为0, 选哪个呢?
选哪个都行,所以这也是为什么拓扑排序的结果是不唯一的。
2、将该节点从图中移除
1、找到入度为0 的节点,加入结果集
节点2 和 节点3 入度都为0,选哪个都行,这里选节点2
2、将该节点从图中移除
后面的过程一样的,节点3 和 节点4,入度都为0,选哪个都行。
最后结果集为: 0 1 2 3 4 。当然结果不唯一的。
判断有环
如果有 有向环怎么办呢?例如这个图:
这个图,我们只能将入度为0 的节点0 接入结果集。
之后,节点1、2、3、4 形成了环,找不到入度为0 的节点了,所以此时结果集里只有一个元素。
那么如果我们发现结果集元素个数 不等于 图中节点个数,我们就可以认定图中一定有 有向环!
这也是拓扑排序判断有向环的方法。
通过以上过程的模拟大家会发现这个拓扑排序好像不难,还有点简单。
写代码
理解思想后,确实不难,但代码写起来也不容易。
为了每次可以找到所有节点的入度信息,我们要在初始化的时候,就把每个节点的入度 和 每个节点的依赖关系做统计。
代码如下:
# 记录每个文件的入度
inDegree = [0] * n
# 记录文件的依赖关系
ucamp = defaultdict(list)# s->t,先有s才能有t
for s,t in edges:#t的入度加一inDegree[t] += 1# 记录s指向哪些文件ucamp[s].append(t)
找入度为0 的节点,我们需要用一个队列放存放。
因为每次寻找入度为0的节点,不一定只有一个节点,可能很多节点入度都为0,所以要将这些入度为0的节点放到队列里,依次去处理。
代码如下:
# 初始化队列,加入入度为0的节点
que = deque([i for i in range(len(inDegree)) if inDegree[i] == 0])
开始从队列里遍历入度为0 的节点,将其放入结果集。
while que:# 当前选中的文件cur = que.popleft()result.append(cur)
这里面还有一个很重要的过程,如何把这个入度为0的节点从图中移除呢?
首先我们为什么要把节点从图中移除?
为的是将 该节点作为出发点所连接的边删掉。
删掉的目的是什么呢?
要把 该节点作为出发点所连接的节点的 入度 减一。
如果这里不理解,看上面的模拟过程第一步:
这事节点1 和 节点2 的入度为 1。
将节点0删除后,图为这样:
那么 节点0 作为出发点 所连接的节点的入度 就都做了 减一 的操作。
此时 节点1 和 节点 2 的入度都为0, 这样才能作为下一轮选取的节点。
所以,我们在代码实现的过程中,本质是要将 该节点作为出发点所连接的节点的 入度 减一 就可以了,这样好能根据入度找下一个节点,不用真在图里把这个节点删掉。
方法一: 拓扑排序
from collections import deque, defaultdictdef topological_sort(n, edges):inDegree = [0] * n # inDegree 记录每个文件的入度umap = defaultdict(list) # 记录文件依赖关系# 构建图和入度表for s, t in edges:inDegree[t] += 1umap[s].append(t)# 初始化队列,加入所有入度为0的节点queue = deque([i for i in range(n) if inDegree[i] == 0])result = []while queue:cur = queue.popleft() # 当前选中的文件result.append(cur)for file in umap[cur]: # 获取该文件指向的文件inDegree[file] -= 1 # cur的指向的文件入度-1if inDegree[file] == 0:queue.append(file)if len(result) == n:print(" ".join(map(str, result)))else:print(-1)if __name__ == "__main__":n, m = map(int, input().split())edges = [tuple(map(int, input().split())) for _ in range(m)]topological_sort(n, edges)
相关文章:

代码随想录算法训练营第五十八天 | 拓扑排序精讲-软件构建
目录 软件构建 思路 拓扑排序的背景 拓扑排序的思路 模拟过程 判断有环 写代码 方法一: 拓扑排序 软件构建 题目链接:卡码网:117. 软件构建 文章讲解:代码随想录 某个大型软件项目的构建系统拥有 N 个文件,文…...

Spring Cloud常见面试题
1.请说说你用过Spring Cloud哪些组件?这些组件分别有什么作用? 1、注册中心:Eureka、Nacos、Zookeeper、Consul;(服务注册) 2、负载均衡:Ribbon、LoadBalancer;(客户端的…...

老古董Lisp实用主义入门教程(9): 小小先生学习Lisp表达式
小小先生 小小先生个子很小,胃口也很小,每次只能干一件事情,还是一件很小很小的事情。 好奇先生已经把explore-lisp代码库安装好,小小先生就只需要打开VS Code, 新建一个lisp为后缀的文件,就能够开始写Lisp代码。 c…...

基于YOLOV8+Pyqt5光伏太阳能电池板目标检测系统
基于YOLOV8Pyqt5光伏太阳能电池板目标检测系统 高质量太阳能光伏电池板可见光图像数据集,标签包含鸟粪,清洁,脏污,电气损坏,物理损坏,积雪覆盖六类。用于目标检测,缺陷检测,异物检测…...
【C++ 设计模式】单例模式的两种懒汉式和饿汉式
文章目录 1. 单例模式2. 单例模式简单示例3. 懒汉模式4. 饿汉模式5. 懒汉式和饿汉式的区别 1. 单例模式 🐧定义:保证一个类仅有一个实例,并提供一个访问它的全局访问点。 单例模式是一种常用的软件设计模式,在它的核心结构中只包…...

计算机的错误计算(九十三)
摘要 探讨 log(y,x) 即以 x 为底 y 的对数的计算精度问题。 Log(y,x)运算是指 x 为底 y 的对数。 例1. 计算 log(123667.888, 0.999999999999999) . 不妨在Python中计算,则有: 若在 Excel 单元格中计算,则有几乎同样的输出: 然…...

基于SpringBoot+Vue的牙科就诊管理系统(带1w+文档)
基于SpringBootVue的牙科就诊管理系统(带1w文档) 基于SpringBootVue的牙科就诊管理系统(带1w文档) 伴随着互联网发展,现今信息类型愈来愈多,信息量也非常大,那也是信息时代的缩影。近些年,电子元器件信息科学合理发展的趋势变的越…...

微信小程序使用 ==== 粘性布局
目录 Chrome杀了个回马枪 position:sticky简介 你可能不知道的position:sticky 深入理解粘性定位的计算规则 粘性定位其他特征 代码实现 微信小程序在scroll-view中使用sticky Chrome杀了个回马枪 position:sticky早有耳闻也有所了解,后来,Chro…...

LineageOS刷机教程
版权归作者所有,如有转发,请注明文章出处:https://cyrus-studio.github.io/blog/ LineageOS 是一个基于 Android 开源项目(AOSP)的开源操作系统,主要由社区开发者维护。它起源于 CyanogenMod 项目ÿ…...
Unity3D帧同步模式的网络游戏详解
帧同步概述 帧同步(Frame Synchronization)是指在网络游戏中,多个客户端在同一时刻执行相同的游戏逻辑,确保各个客户端的游戏状态保持一致。这种同步方式对于实现公平的多人游戏和减少网络延迟对游戏体验的影响至关重要。Unity3D…...

“树”据结构:并查集从入门到AC
“树”据结构:并查集 前言算法设计代码示例优化相关文章 前言 在一组数据中,数据被分为了不同的集合,那么其中的集合往往可以用树形来表示。而区分集合,与查找集合的元素,就会成为核心的问题。并查集主要就是解决这类…...
高级java每日一道面试题-2024年9月11日-数据库篇-事务回滚的常见原因有哪些?
如果有遗漏,评论区告诉我进行补充 面试官: 事务回滚的常见原因有哪些? 我回答: 在Java高级面试中,讨论事务回滚的常见原因是考察候选人对事务管理的理解深度。事务回滚意味着事务中的所有操作都会被撤销,回到事务开始前的状态。以下是事务…...

目标检测中的解耦和耦合、anchor-free和anchor-base
解耦和耦合 写在前面 在目标检测中,objectness(或 objectness score)指的是一个评分,用来表示某个预测框(bounding box)中是否包含一个目标物体。 具体来说,YOLO等目标检测算法需要在每个候选区…...
git rev-parse
git rev-parse 是 Git 中一个非常有用的命令,用于解析并返回与 Git 对象(如提交、分支、标签等)相关的信息。它可以帮助我们从给定的引用(ref)中解析出 SHA-1 哈希值、路径信息等。这个命令在编写 Git 脚本时尤其有用&…...

【Unity】在Unity 3D中使用Spine开发2D动画
文章目录 内容概括前言下载安装 Spine Pro导入Unity插件Spine动画导入Unity使用展现动画效果展现 内容概括 本文主要讲解 Spine Pro 免(破)费(解)版的安装,以及如何将动画导入到Unity中使用。 前言 通常要用 Spine …...

考试:软件工程(01)
软件开发生命周期 ◆软件定义时期:包括可行性研究和详细需求分析过程,任务是确定软件开发工程必须完成的总目标, 具体可分成问题定义、可行性研究、需求分析等。 ◆软件开发时期:就是软件的设计与实现,可分成概要设计…...
数据结构应用实例(三)——赫夫曼编码
Content: 一、问题描述二、算法思想三、代码实现四、小结 一、问题描述 对一篇英文文章,统计各字符(仅限于26个小写字母)出现的次数,并据此进行 Huffman 编码。 二、算法思想 首先,打开文本文件࿰…...

关于Spring Cloud Gateway中 Filters的理解
Spring Cloud Gateway中 Filters的理解 Filters Filters拦截器的作用是,对请求进行处理 可以进行流量染色 ⭐增加请求头 例子 spring:cloud:gateway:routes:- id: add_request_header_routeuri: http://localhost:8123predicates:- Path/api/**filters:- AddR…...

【实践】应用访问Redis突然超时怎么处理?
目录标题 问题描述分析过程查看监控数据系统监控指标JVM监控指标Redis监控指标分析应用异常单机异常规律集群异常规律统计超时的key 初步结论验证结论访问Redis链路slowlogRedis单节点info all定位redis节点定位异常keybigkeystcpdump定位大key影响 经验总结 问题描述 某产品线…...

Spring Cloud Alibaba核心组件Nacos/Seata/Sentinel
文章目录 Spring Cloud Alibaba介绍Spring Cloud 微服务体系Spring Cloud Alibaba 定位 注册配置中心--Nacos服务治理架构注册中心原理 Nacos介绍Nacos 的关键特性1.服务注册和发现2.动态配置服务3.实时健康监控4.动态DNS服务5.易于集成: Nacos入门示例服务注册与发…...

XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...

【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

NLP学习路线图(二十三):长短期记忆网络(LSTM)
在自然语言处理(NLP)领域,我们时刻面临着处理序列数据的核心挑战。无论是理解句子的结构、分析文本的情感,还是实现语言的翻译,都需要模型能够捕捉词语之间依时序产生的复杂依赖关系。传统的神经网络结构在处理这种序列依赖时显得力不从心,而循环神经网络(RNN) 曾被视为…...
什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南
文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果
Maven 概述、安装、配置、仓库、私服详解
目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...
ip子接口配置及删除
配置永久生效的子接口,2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

初学 pytest 记录
安装 pip install pytest用例可以是函数也可以是类中的方法 def test_func():print()class TestAdd: # def __init__(self): 在 pytest 中不可以使用__init__方法 # self.cc 12345 pytest.mark.api def test_str(self):res add(1, 2)assert res 12def test_int(self):r…...
CSS设置元素的宽度根据其内容自动调整
width: fit-content 是 CSS 中的一个属性值,用于设置元素的宽度根据其内容自动调整,确保宽度刚好容纳内容而不会超出。 效果对比 默认情况(width: auto): 块级元素(如 <div>)会占满父容器…...