当前位置: 首页 > 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拓扑排序 

http://www.lryc.cn/news/480475.html

相关文章:

  • FP独立站引流革命:GG斗篷技术解锁流量新策略
  • 管道(Pipes)、过滤器(Filters)和拦截器(Interceptors)
  • uniapp组件样式运行至小程序失效
  • 认识鸿蒙系统
  • Docker Compose部署Rabbitmq(Dockerfile安装延迟队列)
  • 硬件基础06 滤波器——无源、有源(含Filter Solutions、Filter Pro、MATLAB Fdatool)
  • shopify模块新增内容或图片
  • 【EMNLP2024】基于多轮课程学习的大语言模型蒸馏算法 TAPIR
  • 置信传播算法复现
  • 【在Linux世界中追寻伟大的One Piece】poll代码改写
  • C++builder中的人工智能(17):神经网络中的自我规则非单调(Mish)激活函数
  • Java 的 Scanner 类:控制台输入与文件扫描
  • 使用纯HTML和CSS绘制圣诞树:打造网页中的冬日奇景
  • 深度学习-图像评分实验(TensorFlow框架运用、读取处理图片、模型建构)
  • 羲和数据集收集器0.9
  • 哈尔滨等保测评常见误区破解:避免陷入安全盲区
  • Python学习------第四天
  • 【Django】配置文件 settings.py
  • 量化交易系统开发-实时行情自动化交易-Okex K线数据
  • 【基于轻量型架构的WEB开发】课程 12.5 数据回写 Java EE企业级应用开发教程 Spring+SpringMVC+MyBatis
  • apache-seata-2.1.0 AT模式使用篇(配置简单)
  • (金蝶云星空)客户端追踪SQL
  • OAK相机:纯视觉SLAM在夜晚的应用
  • 发送方确认
  • 如何使用HighBuilder前端开发神器
  • 发现了NitroShare的一个bug
  • 如何关闭 Ubuntu22.04 LTS 的更新提醒
  • 美术资源规范
  • UE5.4 PCG 获取地形Layer
  • 用 cURL 控制 OpenSIPS3.4