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

图论入门算法:拓扑排序(C++)

上文中我们了解了图的遍历(DFS/BFS), 本节我们来学习拓扑排序.

在图论中, 拓扑排序(Topological Sorting)是对一个有向无环图(Directed Acyclic Graph, DAG)的所有顶点进行排序的一种算法, 使得如果存在一条从顶点 u 到顶点 v 的有向边 (u, v) , 那么在排序后的序列中, u 一定在 v 之前.

环境要求

本文所用样例在Windows 11以及Ubuntu 24.04上面编译通过.

  1. Windows: 使用[Visual Studio],
  2. Ubuntu: 使用 Clang 18.1.3. (Ubuntu 24.04 系统安装版本)
  3. GCC 无法编译直接本项目代码, 因为本文代码使用了 C++20 Module, 而 GCC 对此支持不完整.

关于 Module 的更多信息, 请参考我之前的博客: CMake 构建 C++20 Module 实例(使用 MSVC)

本项目工程目录: 图论代码


适用场景

拓扑排序适用于需要确定一系列任务的执行顺序, 且任务之间存在依赖关系的场景. 下图是是一个示例图, 其中顶点代表任务, 有向边代表依赖(A -> B 意味着A 需要在 B 之前完成). 拓扑排序就是给出任务能够完成的先后顺序.

sample

算法实现

常见的拓扑排序算法有两种: Kahn 算法和深度优先搜索(DFS)算法.

Kahn 算法

  1. 统计每个顶点的入度(即指向该顶点的边的数量).
  2. 将所有入度为 0 的顶点加入队列中.
  3. 从队列中取出一个顶点, 将其输出, 并将该顶点的所有邻接顶点的入度减 1.
  4. 如果某个邻接顶点的入度变为 0, 则将其加入队列中.
  5. 重复步骤 3 和 4, 直到队列为空.
  6. 如果输出的顶点数量小于图中的顶点总数, 则说明图中存在环, 无法进行拓扑排序.

过程步骤如图:

  1. 起初, 入度为 0 的顶点为 A, F. 我们可以弹出 AF中的任意一个. 这里假设我们先弹出 A.
    kahn0
  2. 弹出 A 后, 边线 A -> BA -> C 被弹出, 并且入度 BC 分别减 1, 此时状态如图所示. 接下来我们要弹出F.
    kahn1
  3. 弹出F后, 边线 F -> C 被弹出, 并且入度 C 减 1, 此时状态如图所示. 接下来我们弹出B.
    kahn2
  4. 弹出B后, 边线 B -> D 被弹出, 并且入度 D 减 1, 此时状态如图所示. 接下来我们弹出C.
    kahn3
  5. 弹出C后, 边线 C -> D 被弹出, 并且入度 D 减 1, 此时状态如图所示. 接下来我们弹出D.
    kahn4
  6. 弹出D后, 边线 D -> E 被弹出, 并且入度 E 减 1, 此时状态如图所示. 接下来我们弹出E.
    kahn5
  7. 弹出E后, 队列为空, 算法结束.
代码实现
class TopologicalSortKahn {public:explicit TopologicalSortKahn(const AdjList& graph) : graph_(graph) {if (!graph_.Directed()) {throw std::invalid_argument("Graph must be directed for topological sorting.");}}std::vector<

相关文章:

图论入门算法:拓扑排序(C++)

上文中我们了解了图的遍历(DFS/BFS), 本节我们来学习拓扑排序. 在图论中, 拓扑排序(Topological Sorting)是对一个有向无环图(Directed Acyclic Graph, DAG)的所有顶点进行排序的一种算法, 使得如果存在一条从顶点 u 到顶点 v 的有向边 (u, v) , 那么在排序后的序列中, u 一定…...

【CXX】2 CXX blobstore客户端说明

本示例演示了一个调用blobstore服务的C客户端的Rust应用程序。事实上&#xff0c;我们会看到两个方向的调用&#xff1a;Rust到C以及C到Rust。对于您自己的用例&#xff0c;您可能只需要其中一个方向。 示例中涉及的所有代码都显示在此页面上&#xff0c;但它也以可运行的形式提…...

HTTP相关面试题

HTTP/1.1、HTTP/2、HTTP/3 演变 HTTP/1.1 相比 HTTP/1.0 提高了什么性能&#xff1f; HTTP/1.1 相⽐ HTTP/1.0 性能上的改进&#xff1a; 使⽤长连接的⽅式改善了 HTTP/1.0 短连接造成的性能开销。⽀持管道&#xff08;pipeline&#xff09;网络传输&#xff0c;只要第⼀个请…...

关于XML映射器的基本问题

前言 XML 映射器是 MyBatis 中用于定义 SQL 语句及其与 Java 对象映射关系的 XML 文件。它通过 XML 配置将数据库操作与 Java 代码分离&#xff0c;使 SQL 语句更易维护和管理。 主要作用 定义 SQL 语句&#xff1a;在 XML 中编写 SQL 查询、插入、更新和删除操作。 映射结果…...

【MyBatis】预编译SQL与即时SQL

目录 1. 以基本类型参数为例测试#{ }与${ }传递参数的区别 1.1 参数为Integer类型 1.2 参数为String类型 2. 使用#{ }传参存在的问题 2.1 参数为排序方式 2.2 模糊查询 3. 使用${ }传参存在的问题 3.1 SQL注入 3.2 对比#{ } 与 ${ }在SQL注入方面存在的问题 3.3 预编译…...

Python--正则表达式

1. 日志打印与终端颜色控制 1.1 使用 loguru​ 打印日志 from loguru import loggerlogger.debug("调试信息") logger.info("普通信息") logger.warning("警告信息") logger.error("错误信息") logger.success("成功信息"…...

【java面试】线程篇

1.什么是线程&#xff1f; 线程是操作系统能够进行运算调度的最小单位&#xff0c;它被包含在进程之中&#xff0c;是进程中的实际运作单位。 2.线程和进程有什么区别&#xff1f; 线程是进程的子集&#xff0c;一个进程可以有很多线程&#xff0c;每条线程并行执行不同的任…...

分布式光纤传感:为生活编织“感知密网”

分布式光纤测温技术虽以工业场景为核心&#xff0c;但其衍生的安全效益已逐步渗透至日常生活。 分布式光纤测温技术&#xff08;DTS&#xff09;作为一种先进的线型温度监测手段&#xff0c;近年来在多个领域展现了其独特的优势。虽然其核心应用场景主要集中在工业、能源和基础…...

cmake Qt Mingw windows构建

今天教大家怎么在windows构建qt应用使用cmd命令行&#xff0c;而不是一键通过QtCreator一键构建。首先我们用qtcreator创建一个模板程序(PS&#xff1a;记得在安装qt时要悬着mingw套件&#xff0c;如果安装太慢可以换源&#xff09; 输入以下的命令&#xff1a; mkdir build …...

无人机信号调制技术原理

一、调制技术的必要性 频谱搬移&#xff1a;将低频的基带信号搬移到高频的载波上&#xff0c;便于天线辐射和传播。 信道复用&#xff1a; 利用不同的载波频率或调制方式&#xff0c;实现多路信号同时传输&#xff0c;提高信道利用率。 抗干扰&#xff1a; 通过选择合适的调…...

书评与笔记:《如何有效报告Bug》

文章目录 书评笔记核心原则1. 首要目标&#xff1a;让程序员亲眼看到问题2. 次要目标&#xff1a;详细描述问题3. 保持冷静&#xff0c;避免误操作4. 提供额外信息5. 清晰、准确地表达 实用建议不要自作聪明地诊断问题类比&#xff1a;看医生时的症状描述程序员的心理 总结 原文…...

3.【线性代数】——矩阵乘法和逆矩阵

三 矩阵乘法和逆矩阵 1. 矩阵乘法1.1 常规方法1.2 列向量组合1.3 行向量组合1.4 单行和单列的乘积和1.5 块乘法 2. 逆矩阵2.1 逆矩阵的定义2.2 奇异矩阵2.3 Gauss-Jordan 求逆矩阵2.3.1 求逆矩阵 ⟺ \Longleftrightarrow ⟺解方程组2.3.2 Gauss-Jordan求逆矩阵 1. 矩阵乘法 1.…...

[JVM篇]虚拟机性能监控、故障处理工具

虚拟机性能监控、故障处理工具 基础故障处理工具 jps&#xff08;JVM Peocess Status Tool - 虚拟机进程状况工具&#xff09; jstat(JVM Statistics Monitoring Too - 虚拟机统计信息监视工具) jinfo( Configuration info for Java - Java配置信息工具) jmap(Memory Map for…...

UniApp 中 margin 和 padding 属性的使用详解

margin 属性的作用与使用 margin 属性用于设置元素的外边距&#xff0c;也就是元素与其他元素之间的距离。它可以分别设置元素四个方向&#xff08;上、右、下、左&#xff09;的外边距&#xff0c;也支持使用简写形式来一次性设置多个方向的外边距。 <template><view…...

`fi` 是 Bash 脚本中用来结束 `if` 条件语句块的关键字

fi 是 Bash 脚本中 if 语句的结束标志&#xff0c;它用于结束一个 if 块。与其他编程语言&#xff08;如 C、Java&#xff09;中的 } 不同&#xff0c;Bash 使用 fi 来标识条件语句的结束。 语法示例&#xff1a; if [ condition ]; then# 如果条件为真时执行的代码echo &quo…...

cap2:1000分类的ResNet的TensorRT部署指南(python版)

《TensorRT全流程部署指南》专栏文章目录&#xff1a; cap1&#xff1a;TensorRT介绍及CUDA环境安装cap2&#xff1a;1000分类的ResNet的TensorRT部署指南&#xff08;python版&#xff09;cap3&#xff1a;自定义数据集训练ResNet的TensorRT部署指南&#xff08;python版&…...

每日一题——把数字翻译成字符串

把数字翻译成字符串 题目描述示例示例1示例2 题解动态规划代码实现复杂度分析 总结 题目描述 有一种将字母编码成数字的方式&#xff1a;‘a’->1, ‘b’->2, … , ‘z’->26。 现在给一串数字&#xff0c;返回有多少种可能的译码结果。 数据范围&#xff1a;字符串…...

我们来学HTTP/TCP -- 三次握手?

三次握手 题记三次呼叫结语 题记 来&#xff0c;我们来演示下川普王和普京帝会面了 哎呦&#xff01;你好你好&#xff0c;握手…哎嗨&#xff01;侬好侬好&#xff0c;握手…欧嘿呦玛斯&#xff0c;握手… 抓狂啊&#xff01;作孽啊!!! 不说人话啊! 关键的是&#xff0c;“三…...

多媒体软件安全与授权新范例,用 CodeMeter 实现安全、高效的软件许可管理

背景概述 Reason Studios 成立于 1994 年&#xff0c;总部位于瑞典斯德哥尔摩&#xff0c;是全球领先的音乐制作软件开发商。凭借创新的软件产品和行业标准技术&#xff0c;如 ReWire 和 REX 文件格式&#xff0c;Reason Studios 为全球专业音乐人和业余爱好者提供了一系列高质…...

SQL复习

SQL复习 MySQL MySQL MySQL有什么特点&#xff1f; MySQL 不支持全外连接。 安装 数据类型 MySQL中的数据类型分为哪些&#xff1f; MySQL中的数据类型主要分为三大类&#xff1a;数值类型、字符串类型、日期时间类型。 其中&#xff0c; 数值类型又分为七种&#xff1a;T…...

告别高成本DAC!用单片机PWM+RC滤波,低成本搞定LM5175数控电源的电压调节

低成本数控电源方案&#xff1a;用PWMRC滤波替代DAC驱动LM5175 在硬件开发领域&#xff0c;预算限制常常是创新路上的绊脚石。当我们面对一个需要精确电压控制的电源项目时&#xff0c;传统方案会毫不犹豫地选择高精度DAC芯片。但现实情况是&#xff0c;一块16位DAC的价格可能比…...

xpath-helper-plus:深度解析高性能网页定位工具架构与3大核心特性

xpath-helper-plus&#xff1a;深度解析高性能网页定位工具架构与3大核心特性 【免费下载链接】xpath-helper-plus 这是一个xpath开发者的工具&#xff0c;可以帮助开发者快速的定位网页元素。 项目地址: https://gitcode.com/gh_mirrors/xp/xpath-helper-plus xpath-he…...

AI智能体业务规则管理:用rulespec告别提示词泥潭

1. 项目概述&#xff1a;为AI智能体构建可管理的业务规则引擎在AI应用开发&#xff0c;尤其是基于大语言模型&#xff08;LLM&#xff09;构建智能体&#xff08;Agent&#xff09;的过程中&#xff0c;一个长期存在的痛点是如何系统化地管理那些驱动智能体行为的“业务规则”。…...

AISMM模型落地三阶跃迁,深度拆解某千亿级集团如何用12周实现OEE提升18.6%

更多请点击&#xff1a; https://intelliparadigm.com 第一章&#xff1a;AISMM模型在制造业落地的战略价值与行业适配性 AISMM&#xff08;Artificial Intelligence-enabled Smart Manufacturing Model&#xff09;并非通用AI框架的简单移植&#xff0c;而是面向离散制造与流…...

告别SAP RFC调用迷茫:用C# .NET Core 6封装一个自己的SAPHelper(附完整源码)

告别SAP RFC调用迷茫&#xff1a;用C# .NET Core 6封装一个自己的SAPHelper&#xff08;附完整源码&#xff09; 在企业级应用开发中&#xff0c;SAP系统集成往往是绕不开的话题。许多.NET开发者虽然掌握了基础的RFC调用技术&#xff0c;却在面对重复代码、类型安全缺失和连接管…...

智慧工业粉碎沙石机图像识别 取料机物料状态监测 智慧工业车辆图像识别 voc+yolo+voc数据集第10685期

车辆与工程机械检测数据集 ) 本数据集专注于工业与建筑场景下的重型设备识别&#xff0c;旨在为自动驾驶巡检、智慧工地管理及物流调度提供高质量的视觉训练底座。1. 数据集概述 通过对复杂作业环境下的视觉特征进行深度提取&#xff0c;本数据集涵盖了核心的运输与施工车辆目标…...

电压监控器原理与Microchip选型指南

1. 电压监控器核心原理与系统价值电压监控器&#xff08;Voltage Supervisor&#xff09;是嵌入式硬件系统中的"电力哨兵"&#xff0c;其核心工作原理是通过高精度电压比较器持续监测供电电压。当检测到电压低于预设阈值&#xff08;如3.3V系统的典型阈值2.93V&#…...

网盘直链下载终极解决方案:全平台免费高速下载的完整指南

网盘直链下载终极解决方案&#xff1a;全平台免费高速下载的完整指南 【免费下载链接】Online-disk-direct-link-download-assistant 一个基于 JavaScript 的网盘文件下载地址获取工具。基于【网盘直链下载助手】修改 &#xff0c;支持 百度网盘 / 阿里云盘 / 中国移动云盘 / 天…...

5G NR DRX配置实战:手把手教你理解HARQ-RTT-Timer与RetransmissionTimer的协同工作

5G NR DRX配置实战&#xff1a;深度解析HARQ-RTT-Timer与RetransmissionTimer的协同机制 在5G网络优化工作中&#xff0c;DRX&#xff08;Discontinuous Reception&#xff09;配置是平衡终端功耗与业务时延的关键技术。其中drx-HARQ-RTT-Timer和drx-RetransmissionTimer的协同…...

Pearcleaner:彻底清理Mac应用的终极指南,释放宝贵存储空间

Pearcleaner&#xff1a;彻底清理Mac应用的终极指南&#xff0c;释放宝贵存储空间 【免费下载链接】Pearcleaner A free, source-available and fair-code licensed mac app cleaner 项目地址: https://gitcode.com/gh_mirrors/pe/Pearcleaner 你是否曾注意到&#xff0…...