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

拓扑排序(C++类封装+数组模拟队列和邻接表)

拓扑序列

对于任何无回路的AOV网,其顶点均可排成拓扑序列,并且其拓扑序列未必唯一。步骤如下:

1.从网中选择一个入度为0的顶点且输出。

2.从网中删除该顶点及其所有出边

3.执行1,2,直至所有顶点已输出,或网中剩余顶点均不为0,说明网中存在回路,无法继续拓扑排列。(因此拓扑排列算法也可用来判断一个有向图中是否存在回路。)

准备工作

假定AOV网用邻接表的形式存储,为实现拓扑排序算法,事先需做好以下两项准备工作:

1.建立一个数组count[ ],count[i]的元素值取对应顶点i的入度

2.建立一个堆栈栈中存放入度为0的顶点,每当一个顶点的入度为0,就将其压入栈。

优化模拟堆栈

事实上,可以不为该顶点栈另外分配存储空间,而实直接利用入度为0的顶点的count[ ]数组元素的值来模拟堆栈的压入和弹出。方法如下:

1.设置一个”栈顶指针“top,以指示当前”栈顶“位置(这里的”栈“是模拟的,实际并不存在真正的堆栈)。

2.初始化“栈”时,top值设为-1,表示”栈“空。

3.当顶点i的入度为0,应该进“栈”时,将“栈顶指针”所指的顶点序号放在count[i]中,并更新“栈顶指针”top,令其指向顶点i:

count[I]=top;

top=i;

4.当应该从“栈”中弹出一个顶点时,把原“栈顶”位置记录下来,top退到“次栈顶”:

j=top;

top=count[top];

入度为0的顶点均要被压入“栈”,故每一次“弹出”的顶点(top所指向的顶点)入度都是0,显然,顶点的被弹出次序实际是“栈顶”指针top的变化次序,也就是拓扑排序时顶点的输出次序。如果“栈顶指针”top值变为-1,而顶点却未被全部输出,说明网中有回路,此时算法强制终止拓扑排序。

实现代码 

形式一:类封装

//对包含n个顶点的AOV网进行拓扑排序
void Graph_List::TopoOrder() {int n = graphsize;int* count = new int[n];//计算count数组for (int i = 0; i < n; i++) count[i] = 0;for (int i = 0; i < n; i++) {Edge* p = Head[i].adjacent;while (p != NULL) {count[p->VerAdj]++;p = p->link;}}int top = -1;  //初始化“栈顶指针”for (int i = 0; i < n; i++) {if (count[i] == 0) {count[i] = top;top = i;}}for (int i = 0; i < n; i++) {//若循环体尚未被执行n次,栈顶指针已为-1,说明有回路,终止程序if (top == -1) {cout << "There is a cycle in network!" << endl;return;}else {int j = top;  //从栈中弹出一个顶点jtop = count[top];cout << j << endl;  //输出该顶点Edge* p = Head.adjacent;  //令p为j的边链表头指针while (p != NULL) {  //从当前的图中删除与j关联的边int k = p->VerAdj;  //k为边终点if (--count[k] == 0) {  //入度-1count[k] = top;  //若入度为0,则k入栈top = k;}p = p->link;}}}delete[] count;
}

形式二:数组模拟队列和邻接表 

const int N=100010;
int n; //顶点数
//数组模拟队列和邻接表的拓扑排序
void topsort() {int q[N];  //模拟队列的数组qint hh = 0, tt = -1;  //队头hh,队尾ttint	count[N] = { 0 };  //存储图中所有顶点的入度int h[N]={ -1 }, e[N], ne[N], idx = 0;  //h为顶点结点,e存储顶点值,ne表示链接关系,-1表示无邻接点//计算所有顶点的入度for (int i = 1; i <= n; i++) {for (int j = h[i]; j != -1; j = ne[j]) {count[e[j]]++;}}//将n个顶点中所有入度为0的顶点入队for (int i = 1; i <= n; i++) {if (count[i] == 0) q[++tt] = i;}//while (hh <= tt) {int t = q[hh++];  //队头取出顶点//遍历所有与t邻接的顶点for (int i = h[t]; i != -1; i = ne[i]) {int j = e[i];  //与t邻接的顶点j的入度都-1count[j]--;  if (count[j] == 0) q[++tt] = j;  //若入度为0,则入队}}//若队尾tt=n-1,则证明n个顶点全部遍历if (tt == n - 1) {//此时队列内存储的便是拓扑序列for (int i = 0; i < n; i++) cout << q[i] << " ";}//否则,未全部遍历,存在回路else cout << "There is a cycle in network!" << endl;
}

《数据结构》刘大友||第6章 图||6.4拓扑排序 

相关文章:

拓扑排序(C++类封装+数组模拟队列和邻接表)

拓扑序列 对于任何无回路的AOV网&#xff0c;其顶点均可排成拓扑序列&#xff0c;并且其拓扑序列未必唯一。步骤如下&#xff1a; 1.从网中选择一个入度为0的顶点且输出。 2.从网中删除该顶点及其所有出边。 3.执行1&#xff0c;2&#xff0c;直至所有顶点已输出&#xff0…...

FP独立站引流革命:GG斗篷技术解锁流量新策略

在跨境电商领域&#xff0c;FP独立站的运营者们面临着一个共同的挑战&#xff1a;如何在遵守平台规则的同时&#xff0c;有效地吸引和保持流量。传统的引流方法如SEM、SEO、邮件推广和社交媒体营销&#xff0c;对于FP独立站来说&#xff0c;往往效果有限。但现在&#xff0c;一…...

管道(Pipes)、过滤器(Filters)和拦截器(Interceptors)

在Java中&#xff0c;管道&#xff08;Pipes&#xff09;、过滤器&#xff08;Filters&#xff09;和拦截器&#xff08;Interceptors&#xff09;是三种不同的概念&#xff0c;它们在应用中的作用和实现方式有所不同。以下是它们之间的主要区别&#xff1a; 一、管道&#xf…...

uniapp组件样式运行至小程序失效

文章目录 一、uniapp样式穿透打包运行至微信小程序失效 一、uniapp样式穿透打包运行至微信小程序失效 组件样式隔离文章参考 解决方案 options: {styleIsolation: "shared",},这个配置项改变了小程序组件的样式隔离模式&#xff0c;使得组件的样式能够共享和继承。…...

认识鸿蒙系统

鸿蒙系统作为华为推出的操作系统&#xff0c;近年来在智能手机、智能穿戴、车载和家居等多个领域取得了显著的发展。其独特的分布式技术、高性能和安全性等特点&#xff0c;使其在与安卓和iOS的竞争中逐渐崭露头角&#xff0c;有望形成三足鼎立之势。 从开发者角度来看&#x…...

Docker Compose部署Rabbitmq(Dockerfile安装延迟队列)

整个工具的代码都在Gitee或者Github地址内 gitee&#xff1a;solomon-parent: 这个项目主要是总结了工作上遇到的问题以及学习一些框架用于整合例如:rabbitMq、reids、Mqtt、S3协议的文件服务器、mongodb github&#xff1a;GitHub - ZeroNing/solomon-parent: 这个项目主要是…...

硬件基础06 滤波器——无源、有源(含Filter Solutions、Filter Pro、MATLAB Fdatool)

目录 一、Filter Solutions 1、软件资源及安装教程如下 2、使用相关内容 二、Filter Pro使用 1、软件资源及安装教程如下 2、使用相关内容 三、MATLAB Fdatool 1、在matlab命令中输入fdatool 2、输入相关参数&#xff0c;例如低通、FIR、20阶、hamming窗 3、调用 &am…...

shopify模块新增内容或图片

1、后台找到指定的liquid页面&#xff0c;在该页面下方{% schema %} 新增需求 2、添加轮播图功能 {% comment %} 轮播代码 {% endcomment %}{% if block.settings.enable_slider %}<divclass"size-guide-slider swiper"data-slides-per-view"{{ block.setti…...

【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR

近日&#xff0c;阿里云人工智能平台PAI与复旦大学王鹏教授团队合作&#xff0c;在自然语言处理顶级会议EMNLP 2024 上发表论文《Distilling Instruction-following Abilities of Large Language Models with Task-aware Curriculum Planning》。文章提出了一个名为 TAPIR 的知…...

置信传播算法复现

本文所涉及所有资源均在 传知代码平台 可获取。 目录 一.背景及意义介绍 1. 实际应用广泛 2. 理论研究重要性...

【在Linux世界中追寻伟大的One Piece】poll代码改写

目录 1 -> poll代码改写 1 -> poll代码改写 结合select代码&#xff0c;将select server更改成为pollserver&#xff0c;不是一件困难的事情。 #pragma once#include <iostream> #include <string> #include <poll.h> #include <memory> #inc…...

C++builder中的人工智能(17):神经网络中的自我规则非单调(Mish)激活函数

在这篇文章中&#xff0c;我们将探讨自我规则非单调激活函数——Mish在神经网络中的应用。了解Mish函数的工作原理&#xff0c;将有助于您在使用C IDE构建C应用程序时更加得心应手。 目录 神经网络中的激活函数是什么&#xff1f;能在C中创建激活函数吗&#xff1f;自我规则非…...

Java 的 Scanner 类:控制台输入与文件扫描

Java 的 Scanner 类是一个非常方便的工具类&#xff0c;主要用于从控制台或文件中扫描输入数据。虽然它也可以用于扫描文件内容&#xff0c;但我们通常更喜欢它用于控制台输入&#xff0c;因为扫描文件可以通过文件流来完成。接下来&#xff0c;我们将通过几个简单的示例来讲解…...

使用纯HTML和CSS绘制圣诞树:打造网页中的冬日奇景

### HTML & CSS 实现节日圣诞树&#xff1a;一步步打造你的冬季主题网页 在这篇文章中&#xff0c;我们将使用纯HTML和CSS创建一棵节日圣诞树。通过简单的代码&#xff0c;您可以在网页上实现一棵带有星星、彩球装饰的圣诞树&#xff0c;为网站增添节日氛围。 ### 实现思…...

深度学习-图像评分实验(TensorFlow框架运用、读取处理图片、模型建构)

目录 0、实验准备 ①实验环境 ②需要下载的安装包 ③注意事项&#xff08;很关键&#xff0c;否则后面内容看不懂&#xff09; ④容易出现的问题 1、查看数据并读取数据。 2、PIL库里的Image包进行读取&#xff08;.resize更改图片尺寸&#xff0c;并将原始数据归一化处…...

羲和数据集收集器0.9

为了进一步完善代码,增强其文字抓取能力和文件读取能力,我们做以下改进: 增强 DOCX 文档的文本提取:不仅提取段落和文本框内容,还提取表格中的文本。 增强 PDF 文档的文本提取:不仅提取页面文本和注释,还提取表格中的文本。 优化文本清理:确保文本清理更加彻底,避免不…...

哈尔滨等保测评常见误区破解:避免陷入安全盲区

在当今信息化社会&#xff0c;网络安全已成为各行各业不可忽视的重要议题。等级保护&#xff08;简称“等保”&#xff09;作为我国网络安全的基本制度&#xff0c;旨在通过划分不同安全保护等级&#xff0c;对信息系统实施分等级的安全保护。然而&#xff0c;在实施等保测评的…...

Python学习------第四天

Python的判断语句 一、布尔类型和比较运算符 二、 if语句的基本格式 if语句注意空格缩进&#xff01;&#xff01;&#xff01; if else python判断语句的嵌套用法&#xff1a;...

【Django】配置文件 settings.py

【Django】配置文件 settings.py 和Flask框架不同&#xff0c;Django框架项目在创建的时会默认生成配置文件settings.py&#xff0c;在深入学习Django框架前&#xff0c;我们先简单了解settings.py文件内非注释代码&#xff0c; from pathlib import Path BASE_DIR Path(__f…...

量化交易系统开发-实时行情自动化交易-Okex K线数据

19年创业做过一年的量化交易但没有成功&#xff0c;作为交易系统的开发人员积累了一些经验&#xff0c;最近想重新研究交易系统&#xff0c;一边整理一边写出来一些思考供大家参考&#xff0c;也希望跟做量化的朋友有更多的交流和合作。 接下来聊聊基于Okex交易所API获取K线数…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

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.…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

高防服务器能够抵御哪些网络攻击呢?

高防服务器作为一种有着高度防御能力的服务器&#xff0c;可以帮助网站应对分布式拒绝服务攻击&#xff0c;有效识别和清理一些恶意的网络流量&#xff0c;为用户提供安全且稳定的网络环境&#xff0c;那么&#xff0c;高防服务器一般都可以抵御哪些网络攻击呢&#xff1f;下面…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

Razor编程中@Html的方法使用大全

文章目录 1. 基础HTML辅助方法1.1 Html.ActionLink()1.2 Html.RouteLink()1.3 Html.Display() / Html.DisplayFor()1.4 Html.Editor() / Html.EditorFor()1.5 Html.Label() / Html.LabelFor()1.6 Html.TextBox() / Html.TextBoxFor() 2. 表单相关辅助方法2.1 Html.BeginForm() …...