代码随想录算法训练营第五十八天 | 拓扑排序精讲-软件构建
目录
软件构建
思路
拓扑排序的背景
拓扑排序的思路
模拟过程
判断有环
写代码
方法一: 拓扑排序
软件构建
- 题目链接:卡码网: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入门示例服务注册与发…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...

均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...

GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...

tauri项目,如何在rust端读取电脑环境变量
如果想在前端通过调用来获取环境变量的值,可以通过标准的依赖: std::env::var(name).ok() 想在前端通过调用来获取,可以写一个command函数: #[tauri::command] pub fn get_env_var(name: String) -> Result<String, Stri…...
Linux安全加固:从攻防视角构建系统免疫
Linux安全加固:从攻防视角构建系统免疫 构建坚不可摧的数字堡垒 引言:攻防对抗的新纪元 在日益复杂的网络威胁环境中,Linux系统安全已从被动防御转向主动免疫。2023年全球网络安全报告显示,高级持续性威胁(APT)攻击同比增长65%,平均入侵停留时间缩短至48小时。本章将从…...

MeshGPT 笔记
[2311.15475] MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers https://library.scholarcy.com/try 真正意义上的AI生成三维模型MESHGPT来袭!_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...
python读取SQLite表个并生成pdf文件
代码用于创建含50列的SQLite数据库并插入500行随机浮点数据,随后读取数据,通过ReportLab生成横向PDF表格,包含格式化(两位小数)及表头、网格线等美观样式。 # 导入所需库 import sqlite3 # 用于操作…...
接口 RESTful 中的超媒体:REST 架构的灵魂驱动
在 RESTful 架构中,** 超媒体(Hypermedia)** 是一个核心概念,它体现了 REST 的 “表述性状态转移(Representational State Transfer)” 的本质,也是区分 “真 RESTful API” 与 “伪 RESTful AP…...