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

c++ 拓扑排序

news 来源：原创 2025/7/13 3:52:43

概念

拓扑排序是一种线性排序算法，主要用于有向无环图 (DAG, Directed Acyclic Graph) 中，对顶点进行排序，使得对于每一条边 u→v，顶点 u 都排在顶点 v之前。

特点

适用于有向无环图。
拓扑排序的结果不唯一（如果有多种线性排序方式满足条件）。
常用于任务调度、依赖关系解析、课程安排等场景。

算法

基于 Kahn 算法 (入度法)

核心思想：依次找出入度为 0 的节点，移除它们以及相关边，直到图中没有节点。
步骤：
1. 统计所有节点的入度。
2. 将入度为 0 的节点入队。
3. 每次从队列中取出一个节点，加入结果序列，并将它指向的节点入度减 1。
4. 如果入度变为 0，则加入队列。
5. 直到队列为空，若结果序列包含所有节点，则排序成功。

基于深度优先搜索 (DFS)

核心思想：对每个节点进行深度优先搜索，节点访问完成后，逆序加入结果。
步骤：
1. 用一个数组记录节点是否被访问。
2. 对每个未访问的节点进行 DFS。
3. 每次访问完成一个节点后，将其压入栈中。
4. 最后将栈中元素依次弹出，得到排序结果。

实例

使用 Kahn 算法（c++）

#include <iostream>
#include <vector>
#include <queue>using namespace std;// 拓扑排序函数
vector<int> topologicalSortKahn(int n, vector<vector<int>>& adj) {vector<int> inDegree(n, 0); // 记录每个节点的入度for (auto& edges : adj) {for (int v : edges) {inDegree[v]++;}}queue<int> q;              // 存放入度为 0 的节点for (int i = 0; i < n; i++) {if (inDegree[i] == 0) {q.push(i);}}vector<int> result;while (!q.empty()) {int u = q.front();q.pop();result.push_back(u);   // 加入结果for (int v : adj[u]) { // 移除节点 u 的所有边inDegree[v]--;if (inDegree[v] == 0) {q.push(v);}}}if (result.size() != n) {throw runtime_error("Graph has a cycle!"); // 图中存在环}return result;
}// 主函数
int main() {int n = 6; // 节点数vector<vector<int>> adj = {{2, 3},    // 节点 0 指向 2, 3{3, 4},    // 节点 1 指向 3, 4{},        // 节点 2 无指向{5},       // 节点 3 指向 5{5},       // 节点 4 指向 5{}         // 节点 5 无指向};try {vector<int> result = topologicalSortKahn(n, adj);cout << "拓扑排序结果: ";for (int v : result) {cout << v << " ";}} catch (const exception& e) {cout << e.what() << endl;}return 0;
}

使用 DFS 方法（c++）

#include <iostream>
#include <vector>
#include <stack>using namespace std;// 深度优先搜索
void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited, stack<int>& stk) {visited[node] = true;for (int v : adj[node]) {if (!visited[v]) {dfs(v, adj, visited, stk);}}stk.push(node); // 当前节点访问完成后入栈
}// 拓扑排序函数
vector<int> topologicalSortDFS(int n, vector<vector<int>>& adj) {vector<bool> visited(n, false);stack<int> stk;for (int i = 0; i < n; i++) {if (!visited[i]) {dfs(i, adj, visited, stk);}}vector<int> result;while (!stk.empty()) {result.push_back(stk.top());stk.pop();}return result;
}// 主函数
int main() {int n = 6; // 节点数vector<vector<int>> adj = {{2, 3},    // 节点 0 指向 2, 3{3, 4},    // 节点 1 指向 3, 4{},        // 节点 2 无指向{5},       // 节点 3 指向 5{5},       // 节点 4 指向 5{}         // 节点 5 无指向};vector<int> result = topologicalSortDFS(n, adj);cout << "拓扑排序结果: ";for (int v : result) {cout << v << " ";}return 0;
}

课程表安排问题

我们有 nnn 门课程，编号为 0,1,…,n−1。有一些课程的先修要求，比如修读课程 1之前必须修读课程 0。这些要求可以表示为一个有向图，判断是否可以完成所有课程，并给出一个可行的学习顺序。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;// 拓扑排序函数 (基于 Kahn 算法)
vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {vector<vector<int>> adj(numCourses); // 邻接表vector<int> inDegree(numCourses, 0); // 入度数组// 构建图和入度for (auto& prereq : prerequisites) {adj[prereq.second].push_back(prereq.first);inDegree[prereq.first]++;}queue<int> q; // 存放入度为 0 的节点for (int i = 0; i < numCourses; i++) {if (inDegree[i] == 0) {q.push(i);}}vector<int> result; // 存储拓扑排序结果while (!q.empty()) {int course = q.front();q.pop();result.push_back(course);for (int next : adj[course]) {inDegree[next]--;if (inDegree[next] == 0) {q.push(next);}}}// 如果结果中包含所有课程，返回排序；否则返回空return (result.size() == numCourses) ? result : vector<int>();
}// 主函数
int main() {int numCourses = 6; // 总课程数vector<pair<int, int>> prerequisites = {{1, 0}, {2, 1}, {3, 1}, {4, 2}, {5, 3}, {5, 4}};vector<int> order = findOrder(numCourses, prerequisites);if (order.empty()) {cout << "无法完成所有课程（存在环）！" << endl;} else {cout << "课程学习顺序: ";for (int course : order) {cout << course << " ";}cout << endl;}return 0;
}

c++ 拓扑排序

概念拓扑排序是一种线性排序算法，主要用于有向无环图 (DAG, Directed Acyclic Graph) 中，对顶点进行排序，使得对于每一条边 u→v，顶点 u 都排在顶点 v之前。特点适用于有向无环图。拓扑排序的结果不唯一（如果有…...

编程日记 2025/7/13 3:52:43

Vue3的双向数据绑定

如果你有多个 ref 类型的数据需要在父子组件之间实现双向绑定，可以使用 v-model 来进行多个数据的双向绑定。在 Vue 3 中，v-model 默认是针对 modelValue 的，但你可以通过指定自定义的属性名来实现多个双向绑定。多个 v-model 双向绑定的实…...

编程日记 2025/7/13 3:05:20

android-sdk 安装脚本、android-sdk(和platform-tools)国内镜像

android-sdk国内镜像 https://mirrors.cloud.tencent.com/AndroidSDK/ android-sdk安装脚本 android-sdk 安装脚本 androidSdk_install.sh #!/bin/bash #[描述] android-sdk 安装# set -eu shopt -s expand_aliasesAndroid_SDK_D/app5/android-sdk-home/JAVA17_D/app/zulu17…...

编程日记 2025/7/9 5:28:49

SAR ADC 系列16：基于运放的高精度比较器

高精度比较器的设计目标静态开环运放比较器共模为，Id*R1，不稳定，随Id和R1变化。正反馈。Vin增加，Vout-减小推推推推推，Vout-又减小，正反馈同时，MP2 < MP1 时，增益提升。MP…...

编程日记 2025/6/30 19:17:30

spring boot 调用C#封装的DLL文件中的函数

1、C#方法 using Infrastructure; using System.Runtime.InteropServices; using System.Text; using System.Text.Json;namespace PH.Resistance;/// <summary> /// 预热器阻力计算 /// </summary> public class PHResistance {private double? C1_outlet_YP01…...

编程日记 2025/7/4 19:01:14

《C++ 与神经网络：自动微分在反向传播中的高效实现之道》

在深度学习蓬勃发展的今天，神经网络成为了众多领域的核心技术驱动力。而反向传播算法作为训练神经网络的关键手段，其背后的自动微分技术的高效实现尤为重要，特别是在 C 这样追求性能与内存控制极致的编程语言环境下。神经网络通过大量的参数…...

编程日记 2025/7/8 8:17:00

AppFlow：支持飞书机器人调用百炼应用

AppFlow：支持飞书机器人调用百炼应用简介： 本文介绍了如何创建并配置飞书应用及机器人，包括登录飞书开发者后台创建应用、添加应用能力和API权限，以及通过AppFlow连接流集成阿里云百炼服务，最后详细说明了如何将机器…...

编程日记 2025/7/13 1:33:24

Axure RP教程：创建高效用户界面和交互

Axure RP是一款广受好评的软件，专门用于设计精致的用户界面和交互体验。这款软件提供了众多UI控件，并根据它们的用途进行了分类。与此同时，国产的即时设计软件作为Axure的替代品，支持在线协作和直接在浏览器中使用，无需…...

编程日记 2025/7/6 11:05:45

【Bug】el-date-picker组件时间差

这个组件默认是国际标准时间 2024-11-27T07:56:37.000Z 表示的是 UTC 时间。如果你当前所在的时区是 UTC8（例如中国），那么这个时间实际上是比你选择的时间早 8 个小时 T表示分隔符，Z表示的是UTC 解决：给el-date-pic…...

编程日记 2025/7/11 1:11:09

Ubuntu问题 -- 使用scp将本机文件传输至ubuntu服务器中

目的临时没有文件传输工具使用一条命令快速传输指定文件或文件夹使用scp命令传输指定文件 scp -P 22 D:\Storage\myCache\UE\Linux_ue_demo.zip txl10.1.112.93:/home/txl-P是远程机器的ssh端口号, SCP（安全复制协议）使用和SSH（安全外壳…...

编程日记 2025/7/12 8:04:59

每日速记10道java面试题02

其他面试题每日速记10道java面试题01-CSDN博客目录一、Java 中 String、StringBuffer 和 StringBuilder 的区别是什么? 二、java的Stringbuilder是怎么实现的？ 三、Java 中包装类型和基本类型的区别是什么? 四、接口和抽象类有什么区别？ 编辑…...

编程日记 2025/7/12 16:27:58

解决 Vim 上下左右变成 ABCD 的问题

解决 Vim 上下左右变成 ABCD 的问题 Vim 是 Linux 和 Unix 系统上广受欢迎的编辑器，但许多用户在首次使用时会遇到一些让人困惑的问题，例如：按下上下左右键时光标不移动，而是输出 A、B、C、D 字母。这篇文章将深入分析该问题的解…...

编程日记 2025/7/9 22:56:59

并发编程（14）——内存栅栏

文章目录十四、day141. 内存栅栏1.1 什么是栅栏1.2 栅栏和原子操作的对比1.2.1 获取操作1.2.2 释放操作 1.3 线程可见顺序1.4 通过栅栏保证指令编排顺序1.5 通过栅栏令非原子操作服从内存次序1.6 同步线程间的内存访问十四、day14 在学习完内存模型、内存序、原子类型、操作…...

编程日记 2025/7/10 10:20:31

消息中间件用途介绍

1. 解耦（Decoupling）： • 消息中间件能够将消息的生产者（Producer）和消费者（Consumer）分离开来，使它们不必直接相互依赖。这种设计降低了系统的耦合度，提升了系统的可扩展…...

编程日记 2025/7/9 4:32:36

Algorithms and Data Structures in C++ by Mohammed Yasir Eramangadan

编程日记 2025/7/8 14:00:46

Binder架构

一、架构如上图，binder 分为用户层和驱动层两部分，用户层有客户端（Client）、服务端（Server）、服务管理（ServiceManager）。从用户空间的角度，使用步骤如下（…...

编程日记 2025/7/12 22:44:32

【第十一课】Rust并发编程（二）

目录前言 Channel 多生产者前言在上一节中，我们介绍了Rust中并发编程的方式之一：Fork和Join，通过新建线程提升代码的效率，这节课我们介绍并发编程的第二种方式：通道。Channel就类似于水管，通过Channe…...

编程日记 2025/7/12 23:47:22

网络知识1-TCP/IP模型

从用户端到服务端，tcp/ip模型可分为应用层、传输层、网络层、网络接口层以下使用寄快递为例进行解释应用层职责： 只关注与为用户提供应用功能，如HTTP、FTP、telnet、DNS、SMTP等 ，应用层的职责就像我们寄快递时将快递给快递员…...

编程日记 2025/7/7 13:39:39

burpsuite（2）最新版burpsuite安装教程

一、安装Java 1.安装jdk21，直接官网下载下载链接：Java21 2.cmd 输出java（查看java是否已经被安装） 3.java -version（查看java版本） 二、安装burpsuite 4.下载burpsuite最新版本，选择jar方式…...

编程日记 2025/7/12 22:43:33

微知-arp如何删除所有表项？（arp -d； ip neighbor delete 192.168.0.100）

ar命令删掉所有表项 sudo arp -d使用ip命令 ip neighbor delete 192.168.0.100...

编程日记 2025/7/12 19:45:20

使用guzzlehttp异步多进程实现爬虫业务

Python和PHP核心技术共享平台背景小哥近来在通过动态代理池爬取一些公司需要的大文件pdf规格书的处理。遇到的难点，如何保证服务器CPU、连接数等正常情况下，多进程、异步快速处理这些业务并且保证准确。下面小哥就给看官唠嗑一下，我使用gu…...

编程日记 2025/7/9 14:45:39

websocket前后端长连接之java部分

一共有4个类,第一个WebSocketConfig 配置类 Configuration EnableWebSocket public class WebSocketConfig implements WebSocketConfigurer {Autowiredprivate WebSocketHandler webSocketHandler;Autowiredprivate WebSocketInterceptor webSocketInterceptor;Overridepubli…...

编程日记 2025/7/6 7:23:57

无线感知会议系列【16】QGesture-1

摘要： 这是2018年发表的一篇 paper 《 Quantifying Gesture Distance and Direction with WiFi Signals》下一篇重要分享 Decimeter-level localization with a single WiFi access point，主要创新点是如何对CFO SFO PBD 噪声进行去噪。许多人机交互&…...

编程日记 2025/7/6 6:22:21

如何用通义灵码快速绘制流程图？

使用通义灵码快速绘制流程图？新功能体验不想读前人“骨灰级”代码，不想当“牛马”程序员，想像看图片一样快速读复杂代码和架构？ 通义灵码已经支持代码逻辑可视化，可以把你的每段代码画成流程图。像个脑图工具一样帮你…...

编程日记 2025/7/12 21:29:25

如何搭建一个小程序：从零开始的详细指南

在当今数字化时代，小程序以其轻便、无需下载安装即可使用的特点，成为了连接用户与服务的重要桥梁。无论是零售、餐饮、教育还是娱乐行业，小程序都展现了巨大的潜力。如果你正考虑搭建一个小程序，本文将为你提供一个从零开始的详细…...

编程日记 2025/7/12 1:42:22

wp the_posts_pagination 与分类页面搭配使用

<ul> <?php while( have_posts() ) : the_post(); <li > <a href"<?php the_permalink(); ?>"> <?php xizhitbu_get_thumbnail(thumb-pro); ?> </a> <p > <a href&q…...

编程日记 2025/7/12 16:12:20

文件包含漏洞

本质本质和SQL注入相同，都是输入一段用户可以控制的脚本或代码，让服务器执行包含就比如把函数写在一个文件里，调用函数时直接用文件文件包含漏洞就是攻击者修改了文件的位置，让后台执行任意文件函数 （PHP&…...

编程日记 2025/7/8 4:26:23

docker快速安装zookeeper

一、拉取镜像 docker pull zookeeper:3.9.3 二、启动zookeeper docker run --restartalways -d --name zookeeper -p 2181:2181 -v /etc/localtime:/etc/localtime zookeeper:3.9.3 如果需要挂载zookeeper文件及目录，则参数增加： -v /mydata/zookeeper/d…...

编程日记 2025/7/10 20:43:33

如何解决 java.security.acl.NotOwnerException: 在 ACL 中尝试执行非所有者的操作问题？亲测有效的解决方法！

在 Java 中，java.security.acl.NotOwnerException 异常通常出现在访问控制列表（ACL）操作中。当你尝试在一个不属于拥有者的实体上执行特定的操作时，Java 安全管理器会抛出此异常。简单来说，它指的是你正在尝试执行一个…...

编程日记 2025/7/9 6:52:51

【电力行业标准】《电力信息化软件工程度量规范》（DL/T 2015-2019）-费用标准解读系列20

《电力信息化软件工程度量规范》（DL/T 2015-2019）是国家能源局2019年6月4日发布，2019年10月1日实施的电力行业标准（了解更多可直接关注我们咨询），规定了电力行业信息化软件工程度量原则与内容、成本构成及各…...

编程日记 2025/7/7 12:57:28

python除了熟悉的pandas，openpyxl库也很方便的支持编辑Excel表

excel表格是大家经常用到的文件格式，各行各业都会跟它打交道。之前文章我们介绍了使用openpyxl和xlrd库读取excel表数据，使用xlwt库创建和编辑excel表，在办公自动化方面可以方便我们快速处理数据，帮助我们提升效率。 python之open…...

编程日记 2025/7/12 20:56:29

JavaEE---计算机是如何工作的?

1.了解冯诺依曼体系结构 2.CPU的核心概念,CPU的两个重要指标(核心数和频率) 3.CPU执行指令的流程(指令表,一条一条指令,取指令,解析指令,执行指令) 4.操作系统核心概念(管理硬件,给软件提供稳定的运行环境) 5.进程的概念(运行起来的程序和可执行文件的区别) 6.进程的管理(…...

编程日记 2025/7/9 16:22:41

数据结构(Java版)第五期：ArrayList与顺序表(下)

目录一、用数组实现顺序表一、用数组实现顺序表我们提到过，顺序表是基于数组的封装，这次我们以int为例，用数组去实现一个顺序表。 public class MyArrayList {private int[] arr;public MyArrayList(int capacity){//指定初始容量arr n…...

编程日记 2025/7/9 1:36:57

Docker和Docker Compose部署方式的区别以及各自适用的场景（ChatGPT-4o回答）

prompt: 请详细介绍和解释一下docker和docker compose部署两者之间的区别和使用场景 Docker和Docker Compose是用于容器化应用程序的两个重要工具，它们在功能和使用场景上有一些关键区别。 Docker Docker是一个开源平台，用于开发、运输和运行应用程序。…...

编程日记 2025/7/6 23:15:02

JavaSE---异常

1.异常的体系结构 Thorwable是异常类顶层类，派生出了Error和Exception Error：指的是JVM层面无法解决的问题，如JVM内部错误，资源耗尽等..一旦发生很难解决。 Exception：异常发生后可以通过代码处理，使程序继…...

编程日记 2025/7/13 1:25:40

大模型的认知记录：一次与4o讨论道德经的对话 - “我无法触碰“真实的花草树木”（无名），但通过语言（有名），我可以靠近人类的认知方式。”

因为其它人都去放假了，我比较悠闲，于是想再强化下认知和正念方面的东西。对于世界的感知，只要不强迫训练，很容易被现实世界给侵蚀了。记得去年有幸悟到点什么，感受点什么，但慢慢那种感受变得虚无起来了&…...

编程日记 2025/7/10 20:01:59

std::srand(static_cast＜unsigned int＞(std::time(0)))；每一部分都是啥意思

std::srand(static_cast<unsigned int>(std::time(0))); 这行代码在C中用于初始化随机数生成器的种子。下面我将逐一解释这行代码中的每个部分： ‌std::time(0)‌: std::time 是C标准库中的一个函数，它返回当前时间（自1970年1月1日以来…...

编程日记 2025/7/9 23:19:46

云计算之elastaicsearch logstach kibana面试题

1.ELK是什么？ ELK 其实并不是一款软件，而是一整套解决方案，是三个软件产品的首字母缩写 Elasticsearch：负责日志检索和储存 Logstash：负责日志的收集和分析、处理 Kibana：负责日志的可视化这三款软件都是开源软件，通常是配合使用，而且又先后归于 Elastic.co 公司名下，…...

编程日记 2025/7/9 11:25:38

汽车免拆诊断案例 | 2017款捷豹F-PACE车发动机偶尔怠速不稳

故障现象　一辆2017款捷豹F-PACE车，搭载2.0 L GTDi发动机，累计行驶里程约为16万km。车主反映，车辆组合仪表上发动机故障灯点亮（图1），且发动机偶尔怠速不稳。图1　发动机故障灯点亮故障诊断接车后试车…...

编程日记 2025/7/9 16:52:16

20241124 Typecho 视频插入插件

博文免不了涉及到视频插入这些,网上的插件都或多或少的比较重,和Typecho的风格不搭配后面就有了DPlay插件精简而来的VideoInsertion插件 VideoInsertion: Typecho 视频插入插件目录结构 rockhinlink-ht2:/var/www/html/typecho/usr/plugins/VideoInsertion$ tree -h [4.…...

编程日记 2025/7/8 18:35:25

【接口调试】OpenAI ChatGPT API

【接口调试】AbortController 发出请求finish_reason 参数细节 – Openai ChatGPT 文档发出请求可以将以下命令粘贴到终端中以运行第一个API请求。请确保用您的秘密API密钥替换$OPENAI_API_KEY。 curl https://api.openai.com/v1/chat/completions \-H "Content-Ty…...

编程日记 2025/7/10 19:21:33

ubuntu安装chrome无法打开问题

如果在ubuntu安装chrome后，点击chrome打开没反应，可以先试着在terminal上用命令打开 google-chrome 如果运行命令显示 Chrome has locked the profile so that it doesnt get corrupted. If you are sure no other processes are using this profile…...

编程日记 2025/7/10 8:28:13

【R安装】VSCODE安装及R语言环境配置

目录 VSCODE下载及安装VSCODE上配置R语言环境参考 Visual Studio Code（简称“VSCode” ）是Microsoft在2015年4月30日Build开发者大会上正式宣布一个运行于 Mac OS X、Windows和 Linux 之上的，针对于编写现代Web和云应用的跨平台源代码编辑器&…...

编程日记 2025/7/12 0:07:31

什么是 Token 和 MD5 ？

目录一：Token和MD5分别是什么 1：Token 2：MD5 二：简易Token的实现 1：Base64。 2：验证Token 三：MD5的使用一：Token和MD5分别是什么 1：Token Token 的中文有人翻译成…...

编程日记 2025/7/10 1:12:14

Kubernetes(k8s)1.30.7简单快速部署对外部开放的有状态服务MYSQL8（快速有效）

如何在Kubernetes集群中快速创建部署一个单节点的有状态（即将数据文件挂载到宿主机，防止重新部署mysql服务，数据文件丢失）的对外开放的MYSQL服务。通过创建一个 Kubernetes Deployment 并使用 PersistentVolumeClaim 将其连接到…...

编程日记 2025/7/11 1:14:16

基于Linux的repmgr搭建

第一部分说明 repmgr是一个开源工具套件，用于管理 PostgreSQL 服务器集群中的复制和故障转移。它通过设置备用服务器、监控复制和执行管理任务（例如故障转移或手动切换操作）的工具增强了 PostgreSQL 的内置热备用功能。 PostgreSQL在9.0后引…...

编程日记 2025/7/7 21:09:06

Diff差异算法

目录虚拟DOM Diff算法 Diff过程示例总结在Vue.js中，虚拟DOM（Virtual DOM）是其核心特性之一，它极大地提高了DOM更新的效率。Vue.js使用虚拟DOM的diff算法来比较新旧虚拟DOM树，从而确定最小的DOM更新操作。这种…...

编程日记 2025/7/8 20:20:57

visionpro官方示例分析（一）模板匹配工具缺陷检测工具

1.需求：找出图像中的这个图形。 2.步骤使用CogPMAlignTool工具，该工具是模板匹配工具，见名知意，所谓模板匹配工具就是说先使用该工具对一张图像建立模板，然后用这个模板在其他图像上进行匹配，匹配上了就说…...

编程日记 2025/7/9 18:40:37

字符串分割转换（Java Python JS C++ C ）

题目描述给定一个非空字符串S，其被N个‘-’分隔成N+1的子串，给定正整数K，要求除第一个子串外，其余的子串每K个字符组成新的子串，并用‘-’分隔。对于新组成的每一个子串，如果它含有的小写字母比大写字母多，则将这个子串的所有大写字母转换为小写字母；反之，如果它…...

编程日记 2025/7/9 21:37:47

第33章 - Go语言云原生开发

第33章 - 云原生开发将深入探讨云原生技术及其在现代软件开发中的应用。我们将从云原生的基本概念开始，逐步介绍Kubernetes的基本使用方法，并结合具体的云服务提供商实例，通过Go语言编写的应用程序来展示如何实现云原生开发。 33.1 云原生的…...

编程日记 2025/7/9 11:32:06

概念

特点

算法

基于 Kahn 算法 (入度法)

基于深度优先搜索 (DFS)

实例

使用 Kahn 算法（c++）

使用 DFS 方法（c++）

课程表安排问题

相关文章：