数据结构和算法-AOV与AOE网络和(逆)拓扑排序与关键路径

2023-12-18 06:28

本文主要是介绍数据结构和算法-AOV与AOE网络和(逆)拓扑排序与关键路径,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • AOV网络
  • 拓扑排序
  • 代码实现
    • 时间复杂度
  • 逆拓扑排序
    • 实现
    • DFS算法实现逆拓扑排序
    • 小结
  • AOE网络
    • 关键路径
    • 求关键路径
      • 求事件最早发生时间
      • 求事件最迟发生时间
      • 求活动最早发生时间
      • 求活动最迟发生时间
      • 求活动余量
    • 关键活动 关键路径的特性
    • 小结

AOV网络

必须是DAG图(有向无环图)
在这里插入图片描述

拓扑排序

在这里插入图片描述
在这里插入图片描述
排序序列不唯一
当前网中不存在无前驱的顶点即存在回路
在这里插入图片描述
在这里插入图片描述

代码实现

此时时邻接表存储
首先入度为0的点入栈
然后开始出栈,知道栈为空,每出一个保存到print数组中,然后将出栈的点指向的顶点入度减1,并把入度为零的顺便压入栈中
在这里插入图片描述

时间复杂度

在这里插入图片描述

逆拓扑排序

在这里插入图片描述

实现

逆邻接表
在这里插入图片描述

DFS算法实现逆拓扑排序

在这里插入图片描述
在这里插入图片描述

小结

在这里插入图片描述

AOE网络

在这里插入图片描述
在这里插入图片描述

关键路径

下图关键路径标红
在这里插入图片描述
在这里插入图片描述
按关键路径从后往前推
在这里插入图片描述
在这里插入图片描述

求关键路径

所有事件的最早发生时间就是所有活动的最早发生时间
而所有事件的最迟发生事件并不等于所有活动的最迟发生时间
所有活动的最迟发生时间需要通过活动的执行时间和所有事件的最迟发生时间来求
在这里插入图片描述

求事件最早发生时间

在这里插入图片描述

求事件最迟发生时间

在这里插入图片描述

求活动最早发生时间

在这里插入图片描述

求活动最迟发生时间

在这里插入图片描述

求活动余量

在这里插入图片描述

关键活动 关键路径的特性

缩短到一定程度时,即再缩短也无法缩短整个工程的工期了

在这里插入图片描述
在这里插入图片描述

小结

在这里插入图片描述
在这里插入图片描述

这篇关于数据结构和算法-AOV与AOE网络和(逆)拓扑排序与关键路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


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

相关文章

如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)

《如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)》:本文主要介绍如何更改pycharm缓存路径和虚拟内存分页文件位置(c盘爆红)问题,具有很好的参考价值,希望对大家有所帮助,如有... 目录先在你打算存放的地方建四个文件夹更改这四个路径就可以修改默认虚拟内存分页js文件的位置接下来从高级-

Linux网络配置之网桥和虚拟网络的配置指南

《Linux网络配置之网桥和虚拟网络的配置指南》这篇文章主要为大家详细介绍了Linux中配置网桥和虚拟网络的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 一、网桥的配置在linux系统中配置一个新的网桥主要涉及以下几个步骤:1.为yum仓库做准备,安装组件epel-re

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

python如何下载网络文件到本地指定文件夹

《python如何下载网络文件到本地指定文件夹》这篇文章主要为大家详细介绍了python如何实现下载网络文件到本地指定文件夹,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下...  在python中下载文件到本地指定文件夹可以通过以下步骤实现,使用requests库处理HTTP请求,并结合o

一文详解如何查看本地MySQL的安装路径

《一文详解如何查看本地MySQL的安装路径》本地安装MySQL对于初学者或者开发人员来说是一项基础技能,但在安装过程中可能会遇到各种问题,:本文主要介绍如何查看本地MySQL安装路径的相关资料,需... 目录1. 如何查看本地mysql的安装路径1.1. 方法1:通过查询本地服务1.2. 方法2:通过MyS

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Linux高并发场景下的网络参数调优实战指南

《Linux高并发场景下的网络参数调优实战指南》在高并发网络服务场景中,Linux内核的默认网络参数往往无法满足需求,导致性能瓶颈、连接超时甚至服务崩溃,本文基于真实案例分析,从参数解读、问题诊断到优... 目录一、问题背景:当并发连接遇上性能瓶颈1.1 案例环境1.2 初始参数分析二、深度诊断:连接状态与

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

springboot实现配置文件关键信息加解密

《springboot实现配置文件关键信息加解密》在项目配置文件中常常会配置如数据库连接信息,redis连接信息等,连接密码明文配置在配置文件中会很不安全,所以本文就来聊聊如何使用springboot... 目录前言方案实践1、第一种方案2、第二种方案前言在项目配置文件中常常会配置如数据库连接信息、Red