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

2023-12-18 06:28
文章标签 算法 路径 数据结构 排序 网络 关键 拓扑 aoe aov

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

文章目录

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

AOV网络

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

拓扑排序

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

代码实现

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

时间复杂度

在这里插入图片描述

逆拓扑排序

在这里插入图片描述

实现

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

DFS算法实现逆拓扑排序

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

小结

在这里插入图片描述

AOE网络

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

关键路径

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

求关键路径

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

求事件最早发生时间

在这里插入图片描述

求事件最迟发生时间

在这里插入图片描述

求活动最早发生时间

在这里插入图片描述

求活动最迟发生时间

在这里插入图片描述

求活动余量

在这里插入图片描述

关键活动 关键路径的特性

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

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

小结

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

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


http://www.chinasem.cn/article/507369。

相关文章

关于Java内存访问重排序的研究

关于Java内存访问重排序的研究

《关于Java内存访问重排序的研究》文章主要介绍了重排序现象及其在多线程编程中的影响,包括内存可见性问题和Java内存模型中对重排序的规则... 目录什么是重排序重排序图解重排序实验as-if-serial语义内存访问重排序与内存可见性内存访问重排序与Java内存模型重排序示意表内存屏障内存屏障示意表Int
阅读更多...
python获取当前文件和目录路径的方法详解

python获取当前文件和目录路径的方法详解

《python获取当前文件和目录路径的方法详解》：本文主要介绍Python中获取当前文件路径和目录的方法,包括使用__file__关键字、os.path.abspath、os.path.realp... 目录1、获取当前文件路径2、获取当前文件所在目录3、os.path.abspath和os.path.re
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
hdu2544（单源最短路径）

hdu2544（单源最短路径）

模板题： //题意：求1到n的最短路径，模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
Linux 网络编程 --- 应用层

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码： 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口，https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor
阅读更多...
usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心： 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数，若返回值为正，qsort 函数判定a>b ；为负，a<b；为0，a==b； int milkcmp(const void *va,c
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2