程序员经验分享-hwhale

数据结构 图的应用

2023-11-14

生成树

定义

一个连通图的生成树是一个极小连通子图，含有图中所有顶点,但只有构成一棵树的**(n-1)**条边

性质

有**(n-1)**条边的图不一定都是生成树;

再添一条边，必定构成环;

再少一条边，一定非连通;

在这里插入图片描述

带权图的最小生成树

一个带权连通无向图G，可以有不同的生成树，每棵树的所有边上的权值之和也可能不同。

图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树。

最小生成树的生成规则

· 只使用网中的n-1条边来构造n个顶点的最小生成树
· 不能产生回路
· 各边上的权值的总和达到最小

两种最常用的算法
Kruskal(克鲁斯卡尔）

Prim（普里姆）算法

利用MST性质来构造最小生成树

若U集是V的一个非空子集，若(u0, v0)是一条最小权值的边，其中u0∈U, v0∈V-U;则(u0, v0)必在最小生成树上。

最小生成树——Kruskal算法

问题
G=(V,E)是一个具有n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树

步骤

步骤1:构造一个只有n个顶点，没有边的非连通图

步骤2:选最小权值的边加入，且不能形成回路，直到所有顶点连通

即

按边选

1、去边留顶点

2、选权最小的

3、不成环

在这里插入图片描述

最小生成树——Prim算法

问题
G=(V，E)是一个具有n个顶点的带权连通无向图

T=(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集

步骤

步骤1:构选一个U集，一个W集(V-U)

步骤2:从某顶点u0出发，找与W集中各顶点关联的权值最小的边(u0,v)，将v加入到U中，从W集中删掉

步骤3:从U集中各点，找与W集中各点关联的权值最小的边(u0, v)，将v加入到U中，从W集中删掉，直到W集为空

即

按点选

1、生成U和W集

2、找U集中各点与W集中各点权最小的

3、W中去掉，加入U

最短路径

在这里插入图片描述

单源最短路径——Dijkstra(迪杰斯特拉)算法

单源：一顶点到其余各顶点

所有顶点间的最短路径——**Floyd(弗洛伊德)**算法

多源：任意两顶点之间

非负权值的单源最短路径（Dijkstra算法）

目的

设一有向图G=(V,E)，已知各边的权值，以某指定点v0为源点，求从v0到图的其余各点的最短路径。

限定各边上的权值大于或等于0

在这里插入图片描述

算法

设置两个顶点的集合S和T，集合S中存放已找到最短路径的顶点，集合T中存放当前还未找到最短路径的顶点。初始状态时，集合S中只包含源点，设为v0

步骤1:初始化:先找出从源点v到各终点v0的直达路径(v0,vk)，即通过一条弧到达的路径。

步骤2:选择:从这些路径中找出一条长度最短的路径(v0,u)。

步骤3:调整:对其余各条路径进行适当调整。

若在图中存在弧(u,v k)，((v 0,u) +(u,v k) <(v 0,v) ,则以路径(v 0,v k)代替(v 0,v k)

在调整后的各条路径中，再找长度最短的路径，依此类推。直到所有的顶点全部加入到S中为止。

存储空间

存储图:邻接矩阵G[n] [n] (或者邻接表)

辅助数组:
数组S[n]:顶点是否已被确定最短距离
数组D[n]:每一个分量D[i]表示当前找到的从源点v到终点vi的最短路径的长度。

D[n]初始状态:
若从v0到顶点vi有边,则D[i]为该边的权值;若从v0到顶点vi无边,则D[i]为∞。

每次求得一条最短路径后,其终点v k加入集合S，然后对所有的v i∈ V-S，修改其dist[i]值。

数组Path[n]:记录相应顶点的前驱顶点

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

算法步骤

1、初始化

将源点v0加到S中，即S[v0]=true;

将v0到各个终点的最短路径长度初始化为权值，即D[i]=G.arcs [v0] [vi]，(vi∈V-S);

如果v0和顶点vi之间有弧，则将vi的前驱置为v0，即Path[i]= v0,否则path[i]=-1。

2、选择下一条最短路径的终点vk，使得:

D[k]=Min{D[i]v 0∈V-S}

3、将k加到S中，即S[vk]=true。

4、更新从v0]出发到集合V-S上任一顶点的最短路径的长度，同时更改vi的前驱为vk。
   若S[i]=false且D[k]+G.arcs[k] [i]<D[i]，则D[i]=D[k]+ G.arcs[k] [i; Path [i]=k;。

5、重复2~4 n-1次，即可按照路径长度的递增顺序，逐个求得从 v0到图上其余各顶点的最短路径。

在这里插入图片描述

算法实现

//一开始主循环，每次求得vO到某个顶点v的最短路径，将v加到s集
for(i=1;i<n;++i){//对其余n-1个顶点，依次进行计算
min= MaxInt;
for(w=0;w<n;++w)
    if(!S[w]&&D[w]<min)
      {v=w; min=D[w]3}//选择一条当前的最短路径，终点为v
S[v]=true;
//r将v加入S
for(w=0;w<n;++w)//更新从v0出发到集合V-S上所有顶点的最短路径长度
    if(!S[w]& &(D[v]+G.arcs[v][w]<D[w])){
D[w]=D[v]+G.arcs[v][w];//更新D[w]
Path [w]=v;//更改w的前驱为v
}//if
}//for
}//ShortestPath_DIJ

时间复杂度：

O(n 2)

在这里插入图片描述

顶点之间的最短路径

问题的提出

已知一个各边权值均大于0的带权有向图，对每一 对顶点vi≠vj，希望求出vi与vj之间的最短路径和最短路径长度。

解决思路

可以通过调用n次Dijkstra算法来完成，

具体方法是:每次以不同的顶点作为源点，调用狄克斯特拉算法求出从该源点到其余顶点的最短路径。重复n次就可求出每对顶点之间的最短路径。

由于迪杰斯特算法的时间复杂度为O(n2)，所以这种算法的时间复杂度为O(n3)。

拓扑结构

有向无环图

用有向图来描述一个工程或系统的进行过程。
一个工程可以分为若干个子工程，只要完成了这些子工程(活动)，就可以导致整个工程的完成。

AOV网(Activity On Vertices)——用顶点表示活动的网络 拓扑排序

AOE网(Activity On Edges)——用边表示活动的网络 关键路径

在这里插入图片描述

拓扑排序——AOV网

AOV网

用有向图表示一个工程。
用顶点表示活动，用有向边<Vi, Vj>表示活动Vi必须先于活动Vj进行。

在AOV网络中不能出现有向回路，即有向环。如果出现了有向环，则意味着某项活动应以自己作为先决条件。

对给定的AOV网络，必须先判断它是否存在有向环。

拓扑有序序列

将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。

拓扑排序

构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。

结论

如果通过拓扑排序能将AOV网络的**所有顶点**都排入拓扑有序序列中，则该网络中必定不会出现有向环。
如果AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。

过程

思想:

重复选择没有直接前驱的顶点

1、输入AOV网络。令n为顶点个数
2、选中一个没有直接前驱的顶点,输出
3、从图中删去该顶点,同时别去所有它发出的有向边
4、重复以上2、3步,直到:

全部顶点均已输出，拓扑有序序列形成，拓扑排序完成;

还有未输出的顶点，但已跳出处理循环。图中剩余顶点都有直接前驱，找不到没有前驱的顶点了。AOV网络中必定存在有向环。

步骤:
1、标入度
2、找入度为0的顶点，删掉，并删掉该点的出边
3、改入度，循环2

关键路径——AOE网

用边表示活动的网络（AOE ( Activity On Edges)网络)

前提

不存在有向环的带权有向图中

用有向边表示一个工程中的活动(Activity)

用边上权值表示活动持续时间(Duration)

应用

估算工程项目至少需要的完成时间（(工期)?

为缩短完成工程所需的时间,应当加快哪些活动?

术语

源点

表示整个工程的开始点

汇点

表示整个工程的结束点

事件结点

时刻、里程碑

有向边

活动，权值定义为活动进行所需要的时间。

方向表示起始结点事件先发生，而终止结点事件才能发生。

源点到汇点:从源点到汇点的有向路径可能不止一条，路径的长度也可能不同。完成不同路径的活动所需的时间虽然不同,但只有各条路径上所有活动都完成了，整个工程才算完成。

关键路径

完成整个工程所需的时间取决于从源点到汇点的**最长**路径长度,即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。

关键活动

要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。

关键路径上的所有活动都是关键活动。

因此,只要找到了关键活动,就可以找到关键路径。

事件Vj的最早发生时间(VE(j))

从源点v到本结点V的最长的路径。意味着事件最早能够发生的时刻。

事件Vj的最迟发生时间(VL(j))

是在保证汇点*Vn-1在VE(n-I)时刻完成的前提下，事件Vj*的允许的最迟开始时间。
不影响工程的如期完工，本结点事件必须发生的时刻。

活动ai的最早开始时间

AE((ai)= VE(j)

活动ai的起始事件点Vj的最早可能开始时间VE( j )

活动a,的最迟开始时间

AL(ai)=VL(k ) - dut(j , k )

活动ai的结束事件点Vk的最晚可能开始时间VL( j )-完成ai所需的时间

是指在不会引起时间延误的前提下,该活动允许的最迟开始时间。

时间余量

AL(a i )-AE(a i )

表示活动ai的最早可能开始时间和最迟允许开始时间的时间余量。

如何找到关键活动

AL(a i )==AE(a i )

表示活动(ai是没有时间余量的关键活动。
求每个活动的AL(ai )与AE(ai)，以判别是否AL(ai )==AE(ai)

总结:
1、求出每个事件的VE->VL
2、求出每个活动的AE ->AL
3、if (AE==AL)得到关键活动
4、由关键活动确定关键路径
5、得出结论(编短工期的方法)

在这里插入图片描述

在这里插入图片描述

举例

在这里插入图片描述

关键路径：12579,12589

AOV和AOE总结

步骤1：先使用拓扑排序得到拓扑序列(工程安排)
步骤2：按照拓扑序列，求出关键路径，得到工程的工期

VE-> VL->AE ->AL
if ( AE= =AL)得到关键活动=》关键路径

得出结论:
① 对于一个工程，可以利用AOV网络分析工程在分解时是否合理(各个子工程间有否冲突)；得到工程施工的调度顺序。
② 对于一个工程，在AOV的基础上，可以利用AOE网络分析工程的关键子工程(抓主要矛盾)，计算工程的工期。
③在不改变关键路径的前提下，提高关键活动的功效，可以缩短工期。

本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构

图论

算法

数据结构 图的应用 的相关文章

随机推荐

  • java sheet 设置名称_Java 实现 给Excel模板赋值(直接打开表格赋值或者用自定义了名称的单元格(一块区域)赋值)...

    1 需求 直接打开表格填充数据到模板后的效果可能出现表格重叠的问题 用自定义名称填充数据到模板后表格互不影响 Excel自身有一个 定义名称 的功能 1 可以给任意的单元格定义一个名称 比如定义某个单元格的名称为 testA1 如何给这个名

  • IO复用进化史

    IO复用的历史和多进程一样长 Linux很早就提供了select系统调用 可以在一个进程内维护1024个连接 后来加入poll系统调用 poll做了一系列改进后解决了1024个连接的限制问题 可以维持任意数量的连接 但是select和pol

  • QT信槽编程，QObject::connect: Cannot connect (null)报错的两种成因

    connect ui btnHelp SIGNAL clicked this SLOT OnBtnHelp connect ui btnHelp SIGNAL toggled bool this SLOT OnBtnHelpChanged

  • Python的10个常用代码简写技术

    今天我给大家整理了一份10个程序员常用的代码简写技术 看懂一种是入门 全懂就是大神 你能知道几个呢 1 三元操作符 当想写if else语句时 使用三元操作符来代替 const x 20 let answer if x gt 10 简写 c

  • unity中物体移动的几种方式

    1 简介 在unity3d中 有多种方式可以改变物体的坐标 实现移动的目的 其本质是每帧修改物体的position 2 通过Transform组件移动物体 Transform 组件用于描述物体在空间中的状态 它包括 位置 position

  • 人脸识别引擎

    最近人工智能异常火爆 各路诸侯蠢蠢欲动 特别是金融业 安防业都在追求人工智能的落地 人工智能新秀云从 商汤 旷世 老牌王者海康 华为都在建设自己的人工智能平台 人工智能领域人脸识别目前来看是最先落地的技术 本文将介绍人脸识别产品中人脸识别引

  • STM3216位编码器溢出问题

    STM3216位编码器溢出问题 STM32定时器有编码器接口 但是它的计数器只有16位 当要记录的数过大时 会溢出 下文介绍了一种方法 能有效解决因计数器位数过少引起的溢出问题 在网上搜了好多 感觉他们说的方法都不准 这个方法经过我自己验证

  • StableDiffusion负面标签自动复制

    随着人工智能AI的兴起 现在AI画图已经风靡全球 其中StableDiffusion以开源 可以本地部署 免费白嫖 引起了包括本人在内的打工人的兴趣 但使用StableDiffusion时 时常会出现诸如 三只手 三只脚 畸形的五官等问题

  • C语言--八大排序之直接插入排序算法

    排序 把无序的数据变得有序 默认升序 笔试面试排名第一的内容 1 直接 简单 插入排序 例如 扑克牌发牌时 每发一张 将牌有序插入 从当前位置开始 从后往前找比当前数字小的 找到后插入到这个小的数字后面 在找的过程中 如果发现一个比当前数字

  • 【Docker网络】容器之间的网络是如何连通的？

    一 Docker0网络详解 1 1 宿主机获取IP l0 本机地址 eth0 阿里云内网地址 docker0 docker的网卡 1 2 docker如何处理容器之间的网络的 1 3 启动一个tomcat01查看docker容器内部的IP地

  • 【STM32】将KEIL下的工程移植到IAR下

    出现问题 IAR无法识别启动文件 汇编 原因 KEIL 和 IAR 中的汇编是不一样的 参考 https blog csdn net u011303443 article details 83177726

  • ES6基础详解

    文章目录 ES6理解 1 let和const 2 解构赋值 3 promise 4 async和await 5 Set和Map 6 箭头函数 7 函数的扩展 8 扩展运算符 ES6理解 当问到ES6时 通常指的是JavaScript的ECM

  • 第五章 创建自定义窗口部件

    对已经存在的Qt窗口进行子类化或者直接对QWidget子类化可以快速创建自己的自定义窗口部件 一 自定义窗口部件 十六进制的QSpinBox 本来QSpinBox仅支持十进制数据的 现在子类化接收并显示十六进制数值 头文件 hexspinb

  • 【Flutter入门教程】从零构建电商应用（一）

    在这个系列中 我们将学习如何使用google的移动开发框架flutter创建一个电商应用 本文是flutter框架系列教程的第一部分 将学习如何安装Flutter开发环境并创建第一个Flutter应用 并学习Flutter应用开发中的核心概

  • 图像区域特征

    以 Halcon 里支持的 Region 特征为基础 做概念总结 形状特征 1 圆度 Circularity 衡量一个形状接近圆的程度 取值为 0 1 Circularity 区域面积 外接圆半径2 Circularity frac 213

  • High-Fidelity Pose and Expression Normalization for Face Recognition in the Wild

    CVPR 2015 Matlab code http www cbsr ia ac cn users xiangyuzhu projects HPEN main htm 中科院关于 人脸图像预处理 姿态和表情的归一化 算法的整体流程图如下所

  • crictl使用总结

    crictl 是 CRI 兼容的容器运行时命令行接口 crictl 是 CRI 兼容的容器运行时命令行接口 你可以使用它来检查和调试 Kubernetes 节点上的容器运行时和应用程序 crictl 和它的源代码在 cri tools 代码

  • 常用的Buck型DC-DC的原理图电路

    常用DC DC buck原理图电路 下图是比较完整的DC DC电路设计 全文将主要介绍各个元件的作用 针对该电路各位号分析 1 Vin的C1 C2主要是滤波 使得DC DC芯片输入能够得到较为干净的电 2 R1 R2是限流用的 一般是K级的

  • 2.信号和槽

    MyPushBotton mybtn new MyPushBotton mybtn gt setParent this mybtn gt setText 我自己的按钮 mybtn gt move 200 200 mybtn gt show

  • 数据结构 图的应用

    文章目录 生成树 定义 性质 带权图的最小生成树 最小生成树的生成规则 最小生成树 Kruskal算法 步骤 最小生成树 Prim算法 步骤 最短路径 非负权值的单源最短路径 Dijkstra算法 目的 算法 存储空间 算法步骤 算法实现

热门标签