数据结构与算法-第六章 图的应用 拓扑排序
admin
2024-04-02 19:39:12
0次

拓扑排序针对的是一种有向无环图,无环的有向图简称DAG图
有向无环图通常用来描述一个工程或系统的进行过程.
一个工程可以分为若干个子工程,只要完成了这些子工程,就可以导致整个工程的完成.

AOV网:拓扑排序

用一个有向图表示一个工程的各子工程及其相互制约关系,其中以顶点表示活动,弧表示活动之间的优先制约关系,称这种有向图为顶点表示活动的网,简称AOV网

AOE网:关键路径

用一个有向图表示一个工程的各子工程及其相互制约关系,以弧表示活动,以顶点表示活动的开始或结束事件,称这种有向图为边表示活动的网,简称AOE网

这里我们先解决拓扑排序的问题,先用到AOV网

AOV网的特点
  • 若从i到j有一条有向路径,则i是j的前驱;j是i的后继.
  • 若是网中有向边,则i是j的直接前驱;j是i的直接后继.
  • 在AOV网中不允许有回路,因为如果存在回路,则表明某项活动以自己为先决条件,显然这是荒谬的.

这样就出现了一个难题:如何判别AOV网中是否存在回路?

拓扑排序

在AOV网中没有回路的前提下,我们将全部活动排列成一个线性序列,使得若AOV网中有弧存在,则在这个序列中,i一定排在j的前面,具有这种性质的线性序列称为拓扑有序序列,相应的拓扑有序排序的算法称为拓扑排序

方法
  1. 在有向图中选一个没有前驱的顶点且输出之
  2. 从图中删除该顶点和所有以它为尾的弧
  3. 重复上述两步,直至全部顶点均已被输出;或者当图中不存在无前驱的顶点为止

故一个AOV网的拓扑排序不是唯一的

检测AOV网中是否存在环的方法

对有向图构造其顶点的拓扑有序序列,若网中所有顶点都在它的拓扑有序序列中,则该AOV网必定不存在环

词库加载错误:未能找到文件“E:\highferrum_mysql\Configuration\Dict_Stopwords.txt”。

上一篇：无问芯穹打造连接全生态伙伴的M×N大模型生态，明年将发布无穹LPU 无问芯穹科技有限公司 无问芯穹是谁的

下一篇：官方：2024赛季中冠联赛共有75家俱乐部正式报名并参赛 中冠2024球队 2023年中冠参赛俱乐部名单

相关内容

热门资讯

linux入门---制作进度条 了解缓冲区 我们首先来看看下面的操作： 我们首先创建了一个文件并在这个文件里面添加了...
C++ 机房预约系统（六）：学... 8、 学生模块 8.1 学生子菜单、登录和注销 实现步骤： 在Student.cpp的...
A.机器学习入门算法（三）：基... 机器学习算法（三）：K近邻(k-nearest neigh...
数字温湿度传感器DHT11模块... 模块实例https://blog.csdn.net/qq_38393591/article/deta...
有限元三角形单元的等效节点力 文章目录前言一、重新复习一下有限元三角形单元的理论1、三角形单元的形函数（Nÿ...
Redis 所有支持的数据结构... Redis 是一种开源的基于键值对存储的 NoSQL 数据库，支持多种数据结构。以下是...
win下pytorch安装—c... 安装目录一、cuda安装1.1、cuda版本选择1.2、下载安装二、cudnn安装三、pytorch...
MySQL基础-多表查询 文章目录MySQL基础-多表查询一、案例及引入1、基础概念2、笛卡尔积的理解二、多表查询的分类1、等...
keil调试专题篇 调试的前提是需要连接调试器比如STLINK。 然后点击菜单或者快捷图标均可进入调试模式。 如果前面...
MATLAB | 全网最详细网... 一篇超超超长，超超超全面网络图绘制教程，本篇基本能讲清楚所有绘制要点&#...
IHome主页 - 让你的浏览... 随着互联网的发展，人们越来越离不开浏览器了。每天上班、学习、娱乐，浏览器...
TCP 协议 一、TCP 协议概念 TCP即传输控制协议（Transmission Control ...
营业执照的经营范围有哪些 营业执照的经营范围有哪些 经营范围是指企业可以从事的生产经营与服务项目，是进行公司注册...
C++ 可变体(variant... 一、可变体(variant) 基础用法 Union的问题： 无法知道当前使用的类型是什...
血压计语音芯片，电子医疗设备声... 语音电子血压计是带有语音提示功能的电子血压计，测量前至测量结果全程语音播报࿰...
MySQL OCP888题解0... 文章目录1、原题1.1、英文原题1.2、答案2、题目解析2.1、题干解析2.2、选项解析3、知识点3...
【2023-Pytorch-检... （肆十二想说的一些话）Yolo这个系列我们已经更新了大概一年的时间，现在基本的流程也走走通了，包含数...
实战项目：保险行业用户分类 这里写目录标题1、项目介绍1.1 行业背景1.2 数据介绍2、代码实现导入数据探索数据处理列标签名异...
记录--我在前端干工地(thr... 这里给大家分享我在网上总结出来的一些知识，希望对大家有所帮助 前段时间接触了Th...
43 openEuler搭建A... 文章目录43 openEuler搭建Apache服务器-配置文件说明和管理模块43.1 配置文件说明...