当前位置: 首页 > news >正文

数据结构--拓扑排序

数据结构–拓扑排序

AOV⽹

A O V ⽹ \color{red}AOV⽹ AOV(Activity On Vertex NetWork,⽤顶点表示活动的⽹):
D A G 图 \color{red}DAG图 DAG(有向⽆环图)表示⼀个⼯程。顶点表示活动,有向边 < V i , V j > <V_i, V_j> <Vi,Vj>表示活动Vi必须先于活动 V j V_j Vj进⾏

注:如果图中存在环路就不是 A O V 网 \color{red}注:如果图中存在环路就不是AOV网 注:如果图中存在环路就不是AOV

DAG图是指有向无环图(Directed Acyclic Graph),是一种有向图的特殊形式。它由一些有向边连接的节点组成,并且不存在任何形式的环。换句话说,从任何一个节点出发,沿着有向边的方向无法经过一系列的节点再回到原始节点。DAG图常用于表示一些具有依赖关系的任务或事件,其中每个节点表示一个任务或事件,有向边表示任务或事件之间的依赖关系。DAG图在计算机科学和工程中有广泛的应用,例如任务调度、编译器优化、数据流分析等领域。

拓扑排序

拓扑排序 \color{red}拓扑排序 拓扑排序:在图论中,由⼀个 有向⽆环图 \color{red}有向⽆环图 有向环图的顶点组成的序列,当且仅当满⾜下列条件时,称为该图的⼀个拓扑排序:
① 每个顶点出现且只出现⼀次。
② 若顶点A在序列中排在顶点B的前⾯,则在图中不存在从顶点B到顶点A的路径。或定义为:拓扑排序是对有向⽆环图的顶点的⼀种排序,它使得若存在⼀条从顶点A到顶点B的路径,则在排序中顶点B出现在顶点A的后⾯。每个AOV⽹都有⼀个或多个拓扑排序序列。

上图其中一个拓扑排序:

拓扑排序的实现:

① 从AOV⽹中选择⼀个没有前驱的顶点并输出。
② 从⽹中删除该顶点和所有以它为起点的有向边。
③ 重复①和②直到当前的AOV⽹为空或当前⽹中不存在⽆前驱的顶点为⽌。

注:拓扑排序序列可能有多个 \color{red}注:拓扑排序序列可能有多个 注:拓扑排序序列可能有多个

拓扑排序代码实现

王道书上代码

个人code

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], d[N];
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
bool topsort()
{int tt = -1, hh = 0;for(int i = 1; i <= n; i++)if(!d[i])q[++tt] = i;while(hh <= tt){int t = q[hh++];for(int i = h[t]; i != -1; i = ne[i]){int j = e[i];d[j]--;if(!d[j]) q[++tt] = j;}}return tt == n - 1;
}
int main()
{cin >> n >> m;memset(h, -1, sizeof(h));for(int i = 0; i < n; i++){int a, b;cin >> a >> b;add(a, b);d[b]++;}if(topsort()){for(int i = 0; i < n; i++)cout << q[i] << ' ';cout << endl;}else cout << "-1" << endl;return 0;
}

判断是否存在拓扑序

时间复杂度 O(n + m), n 表示点数,m表示边数
bool topsort()
{int hh = 0, tt = -1;// d[i] 存储点i的⼊度for (int i = 1; i <= n; i ++ )if (!d[i])q[ ++ tt] = i;while (hh <= tt){int t = q[hh ++ ];for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (-- d[j] == 0)q[ ++ tt] = j;}}// 如果所有点都⼊队了,说明存在拓扑序列;否则不存在拓扑序列。return tt == n - 1;
}

逆拓扑排序

对⼀个AOV⽹,如果采⽤下列步骤进⾏排序,则称之为 逆拓扑排序 \color{red}逆拓扑排序 逆拓扑排序
① 从AOV⽹中选择⼀个没有后继( 出度为 0 \color{red}出度为0 出度为0)的顶点并输出。
② 从⽹中删除该顶点和所有以它为终点的有向边。
③ 重复①和②直到当前的AOV⽹为空。

其中一个逆拓扑排序

逆拓扑排序代码实现

逆拓扑排序的实现(DFS算法)

DFS判断是否有环:

int vis[N], cnt; // timestamp
int per[N];
bool cyc[N];// 标记
void dfs(int u) //找环 & 标记环
{vis[u] = ++cnt;for (auto v : g[u]){if (per[u] == v)continue;if (!vis[v]){per[v] = u;dfs(v);}else if (vis[u] > vis[v]){for (int i = u; i != v; i = per[i])cyc[i] = true;cyc[v] = true;}}
}

如果单纯判断是否有环,只需要引进父结点(fa)
dfs(u,fa)
如果 u == fa 则存在环

知识点回顾与重要考点

相关文章:

数据结构--拓扑排序

数据结构–拓扑排序 AOV⽹ A O V ⽹ \color{red}AOV⽹ AOV⽹(Activity On Vertex NetWork&#xff0c;⽤顶点表示活动的⽹)&#xff1a; ⽤ D A G 图 \color{red}DAG图 DAG图&#xff08;有向⽆环图&#xff09;表示⼀个⼯程。顶点表示活动&#xff0c;有向边 < V i , V j …...

算法竞赛备赛之搜索与图论训练提升,暑期集训营培训

目录 1.DFS和BFS 1.1.DFS深度优先搜索 1.2.BFS广度优先搜索 2.树与图的遍历&#xff1a;拓扑排序 3.最短路 3.1.迪杰斯特拉算法 3.2.贝尔曼算法 3.3.SPFA算法 3.4.多源汇最短路Floy算法 4.最小生成树 4.1.普利姆算法 4.2.克鲁斯卡尔算法 5.二分图&#xff1a;染色法…...

Linux驱动入门(6.2)按键驱动和LED驱动 --- 将逻辑电平与物理电平分离

前言 &#xff08;1&#xff09;在学习完Linux驱动入门&#xff08;6&#xff09;LED驱动—设备树之后&#xff0c;我们发现一个问题&#xff0c;设备树明明的gpios信息明明有三个元素gpios <&gpio5 3 GPIO_ACTIVE_LOW>; &gpio5 3 用来确定控制那个引脚&#xf…...

CentOS系统环境搭建(十四)——CentOS7.9安装elasticsearch-head

centos系统环境搭建专栏&#x1f517;点击跳转 关于node的安装请看上一篇CentOS系统环境搭建&#xff08;十三&#xff09;——CentOS7安装nvm&#xff0c;&#x1f517;点击跳转。 CentOS7.9安装elasticsearch-head 文章目录 CentOS7.9安装elasticsearch-head1.下载2.解压3.修…...

设计HTML5图像和多媒体

在网页中的文本信息直观、明了&#xff0c;而多媒体信息更富内涵和视觉冲击力。恰当使用不同类型的多媒体可以展示个性&#xff0c;突出重点&#xff0c;吸引用户。在HTML5之前&#xff0c;需要借助插件为网页添加多媒体&#xff0c;如Adobe Flash Player、苹果的QuickTime等。…...

基于YOLOv8模型和Caltech数据集的行人检测系统(PyTorch+Pyside6+YOLOv8模型)

摘要 基于YOLOv8模型和Caltech数据集的行人检测系统可用于日常生活中检测与定位行人&#xff0c;利用深度学习算法可实现图片、视频、摄像头等方式的行人目标检测&#xff0c;另外本系统还支持图片、视频等格式的结果可视化与结果导出。本系统采用YOLOv8目标检测算法训练数据集…...

Flutter 宽高自适应

在Flutter开发中也需要宽高自适应&#xff0c;手动写一个工具类&#xff0c;集成之后在像素后面直接使用 px或者 rpx即可。 工具类代码如下&#xff1a; import dart:ui;class HYSizeFit {static double screenWidth 0.0;static double screenHeight 0.0;static double phys…...

LeetCode 0833. 字符串中的查找与替换

【LetMeFly】833.字符串中的查找与替换 力扣题目链接&#xff1a;https://leetcode.cn/problems/find-and-replace-in-string/ 你会得到一个字符串 s (索引从 0 开始)&#xff0c;你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出&#xff1a;indices,…...

Redis对象和五种常用数据类型

Redisobject 对象 对象分为键对象和值对象 键对象一般是string类型 值对象可以是string&#xff0c;list&#xff0c;set,zset,hash q&#xff1a;redisobj的结构 typedef struct redisObject { //类型 unsigned type:4; //编码 unsigned encoding:4; //指向底层实现…...

常用的Elasticsearch查询DSL

1.基本查询 GET /index_name/_search {"query": {"match": {"dispatchClass": "1"}} }2.多条件查询 GET /index_name/_search {"query": {"bool": {"must": [{"match": {"createUser&…...

计算机网络笔记

TCP有连接可靠服务 TCP特点&#xff1a; 1.TCP是面向连接的传输层协议&#xff1b; 2.每条TCP连接只能有两个端点&#xff0c;每条TCP连接是一对一的&#xff1b; 3.TCP提供可靠交付&#xff0c;保证传送数据无差错&#xff0c;不丢失&#xff0c;不重复且有序&#xff1b; 4.…...

高效反编译luac文件

对于游戏开发人员,有时候希望从一些游戏apk中反编译出源代码,进行学习,但是如果你触碰到法律边缘,那么你要非常小心。 这篇文章,我针对一些用lua写客户端或者服务器的编译过的luac文件进行反编译,获取其源代码的过程。 这里我不赘述如何反编译解压apk包的过程了,只说重点…...

密码湘军,融合创新!麒麟信安参展2023商用密码大会,铸牢数据安全坚固堡垒

2023年8月9日至11日&#xff0c;商用密码大会在郑州国际会展中心正式开幕。本次大会由国家密码管理局指导&#xff0c;中国密码学会支持&#xff0c;郑州市人民政府、河南省密码管理局主办&#xff0c;以“密码赋能美好发展”为主题&#xff0c;旨在推进商用密码创新驱动、前沿…...

关于视频监控平台EasyCVR视频汇聚平台建设“明厨亮灶”具体实施方案以及应用

一、方案背景 近几年来&#xff0c;餐饮行业的食品安全、食品卫生等新闻频频发生&#xff0c;比如某火锅店、某网红奶茶&#xff0c;食材以次充好、后厨卫生被爆堪忧&#xff0c;种种问题引起大众关注和热议。这些负面新闻不仅让餐饮门店的品牌口碑暴跌&#xff0c;附带的连锁…...

区块链系统探索之路:私钥的压缩和WIF格式详解

在前面章节中&#xff0c;我们详细介绍了公钥的压缩&#xff0c;在比特币网络中&#xff0c;一个私钥可以对应两个地址&#xff0c;一个地址是由未压缩公钥所生成的地址&#xff0c;另一个就是由压缩公钥所创建的地址&#xff0c;从公钥到区块链地址的转换算法&#xff0c;我们…...

DiffusionDet: Diffusion Model for Object Detection

DiffusionDet: Diffusion Model for Object Detection 论文概述不同之处整体流程 论文题目&#xff1a;DiffusionDet: Diffusion Model for Object Detection 论文来源&#xff1a;arXiv preprint 2022 论文地址&#xff1a;https://arxiv.org/abs/2211.09788 论文代码&#xf…...

CH01_重构、第一个示例

概述 在这一章节&#xff0c;作者给出了一个戏剧演出团售票的示例&#xff1a;剧目有悲剧&#xff08;tragedy&#xff09;和喜剧&#xff08;comedy&#xff09;&#xff1b;为了卖出更多的票&#xff0c;剧团则更具观众的数量来为下次演出打折扣&#xff08;大致意思是这次的…...

学习篇之React Fiber概念及原理

什么是React Fibber&#xff1f; React Fiber 是 React 框架的一种底层架构&#xff0c;为了改进 React 的渲染引擎&#xff0c;使其更加高效、灵活和可扩展。 传统上&#xff0c;React 使用一种称为堆栈调和递归算法来处理虚拟 DOM 的更新&#xff0c;这种方法在大型应用或者…...

商城-学习整理-高级-全文检索-ES(九)

目录 一、ES简介1、网址2、基本概念1、Index&#xff08;索引&#xff09;2、Type&#xff08;类型&#xff09;3、Document&#xff08;文档&#xff09;4、倒排索引机制4.1 正向索引和倒排索引4.2 正向索引4.3 倒排索引 3、相关软件及下载地址3.1 Kibana简介3.2 logstash简介…...

无人机跟随一维高度避障场景--逻辑分析

无人机跟随一维高度避障场景--逻辑分析 1. 源由2. 视频3. 问题3.1 思维发散3.2 问题收敛 4. 图示4.1 水平模式4.2 下坡模式4.3 上坡模式4.4 碰撞分析 5. 总结5.1 一维高度避障场景5.2 业界跟随产品5.3 APM集成跟随 6. 参考资料7. 补充资料 - 大疆智能跟随7.1 炸机7.2 成功 1. 源…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

golang循环变量捕获问题​​

在 Go 语言中&#xff0c;当在循环中启动协程&#xff08;goroutine&#xff09;时&#xff0c;如果在协程闭包中直接引用循环变量&#xff0c;可能会遇到一个常见的陷阱 - ​​循环变量捕获问题​​。让我详细解释一下&#xff1a; 问题背景 看这个代码片段&#xff1a; fo…...

Docker 运行 Kafka 带 SASL 认证教程

Docker 运行 Kafka 带 SASL 认证教程 Docker 运行 Kafka 带 SASL 认证教程一、说明二、环境准备三、编写 Docker Compose 和 jaas文件docker-compose.yml代码说明&#xff1a;server_jaas.conf 四、启动服务五、验证服务六、连接kafka服务七、总结 Docker 运行 Kafka 带 SASL 认…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...