拓扑排序详解(带有C++模板)

chatgpt/2023/9/24 2:53:20

目录

介绍:

实现原理:

简答来说:

例子

模板(C++)


介绍:

        拓扑排序(Topological Sorting)是一种针对有向无环图(DAG)的节点进行排序的算法。DAG是一个图,其中所有边都是有向的,并且不存在任何环路(即没有循环)。拓扑排序可以将这种图中的节点线性排序,使得所有的有向边从排在前面的节点指向排在后面的节点。

实现原理:

  1. 找到入度为0的节点:入度是指有向图中指向某个节点的边的数量。在开始排序之前,首先找到所有入度为0的节点。这些节点是图中没有其他节点指向它们的节点,因此它们可以作为排序的起点。

  2. 从图中删除入度为0的节点:将入度为0的节点从图中删除,并将与这些节点相连的边去掉,即将这些相连节点的入度减1。

  3. 重复上述步骤:重复执行步骤1和步骤2,直到所有节点都被删除。每次找到入度为0的节点,并删除它们,直到没有节点剩余为止。

  4. 排序结果:排序完成后,被删除的节点按照删除的顺序,从头到尾组成了一个拓扑排序序列。

        拓扑排序的结果不是唯一的,因为可能存在多个入度为0的节点。在实际应用中,如果图中存在环路(非DAG),则无法进行拓扑排序,因为无法满足拓扑排序的条件。

简答来说:

        其实就是简单的bfs,但是拓扑排序中每次都要以入度为0的结点开始bfs,所以相较于普通的bfs多了一个记录每个结点入度的d[N]数组,然后每次将删除边后,读入为0的结点入队。

        入队的结点顺序,就是拓扑排序的结果,我们用top[N]数组来记录。若最后入队过的结点小于总结点数,说明有环,返回false,可以判断此图是否可以拓扑排序。

例子

模板(C++)

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;const int N = 100010;
int h[N], e[N], ne[N], idx; // 邻接表
int d[N], top[N]; // 每个节点入度,排序结果
int cnt = 0; // 记录top数组末尾位置
int n, m; // 结点个数,边数// 邻接表连边方法
void add(int a, int b)
{e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
}// 拓扑排序
bool topsort()
{queue<int> q; // 队列for (int i = 1; i <= n; i++)if (d[i] == 0) q.push(i); // 入度为 0的入队while(q.size()){int t = q.front();top[cnt++] = t; // 记录入队顺序q.pop();// bfsfor (int i = h[t]; ~i; i = ne[i]){int j = e[i];d[j]--; // 此节点入度减一if(d[j] == 0) q.push(j); // 若入度减为0,入队}}if (cnt < n) return 0; // 入队的结点小于总结点数else return 1;}int main()
{cin >> n >> m;memset(h, -1, sizeof h); // 初始化表头// 建图while(m--){int x, y; cin >> x >> y;add(x, y);d[y] ++; // 入度++}if (topsort() == 0) cout << "-1"; // 若不能排序,输出-1else{for (int i = 0; i < n; i++)  cout << top[i] <<" "; // 输出排序结果}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.exyb.cn/news/show-5314491.html

如若内容造成侵权/违法违规/事实不符,请联系郑州代理记账网进行投诉反馈,一经查实,立即删除!

相关文章

UG NX二次开发(C++)-在VS2022上配置NXOpenCPP的编程模板

文章目录 1、前言2、问题说明3、解决方案3.1 解决方案一3.2 解决方案二1、前言 在VS2022还未发布以前,采用UG NX自身带的二次开发编程模板可以在VS新建项目中看到,但是由于VS2022版本的发布,UG NX的二次开发编程模板采用原因的方式就不能正常的显示了。本文讲解以下配置VS2…

拿捏--->乘法口诀表

文章目录 前言左下角左上角右下角右上角等腰三角形 前言 九九乘法表,我们从小学就已经了解并且学习了,九九乘法表的历史距今已经有2千多年的历史了。那我们如何使用c语言来输出九九乘法口诀表呢,我们一起来看一看。 我们了解的九九乘法口诀表是这样的&#xff1a; 那我们如…

多模光模块中Lens透镜的关键作用

随着现代通信技术的飞速发展&#xff0c;多模光模块已经成为光通信系统中不可或缺的关键组件。这些模块可实现高速、高容量的数据传输&#xff0c;广泛应用于数据中心、局域网和广域网等领域。在多模光模块中&#xff0c;透镜作为其中的重要组成部分&#xff0c;扮演着至关重要…

source insight常用操作

1、窗口布局 SI窗口十分丰富&#xff0c;通过菜单栏View->Toolbars/panels选择显示那些工具栏/窗口 Source Insight 窗口介绍_sourceinsight窗口_STCNXPARM的博客-CSDN博客 2、RGB护眼色 Source Insight4.0字体大小及护眼背景配置_sourceinsight4背景色配置_ProYuan28的…

子域名收集工具OneForAll的安装与使用-Win

子域名收集工具OneForAll的安装与使用-Win OneForAll是一款功能强大的子域名收集工具 GitHub地址&#xff1a;https://github.com/shmilylty/OneForAll Gitee地址&#xff1a;https://gitee.com/shmilylty/OneForAll 安装 1、python环境准备 OneForAll基于Python 3.6.0开发和…

static关键字学习

static关键字用于共享同一份数据&#xff0c;在类里面&#xff0c;当成员变量使用了static关键字之后&#xff0c;这个变量就属于这个类&#xff0c;而不是单独属于某个对象&#xff0c;所有的这个类的实例对象的这个static关键字的属性都是同一份数据&#xff0c;在堆内存里面…

HttpRunner自动化工具之实现参数化传递

参数化实现及重复执行 参数化测试&#xff1a;在接口测试中&#xff0c;为了实现不同组数据对同一个功能模块进行测试&#xff0c;需要准备多组测试数据对模块进行测试的过程。 在httprunner中可以通过如下方式实现参数化&#xff1a; 1、在YAML/JSON 中直接指定参数列表 2、…

vue中的require

vue中的require 一、基本概念二、具体演示1.引入json2.引入图片 三、require.context引入图片&#xff1a;引入json引入模块js&#xff1a;引入vue文件&#xff1a; 一、基本概念 require 是 node 中的一个方法&#xff0c;他的作用是 用于引入模块、 JSON、或本地静态文件。r…
推荐文章