数据结构——6.4 图的应用

news/2024/5/28 1:52:36/文章来源:https://blog.csdn.net/qq_48035645/article/details/137979405

6.4 图的应用

  • 概念
  1. 最小生成树

    1. 对于一个带权连通无向图G =( E),生成树不同,每棵树的权(即树中所有边上的权值之和)也可能不同。设R为G的所有生成树的集合,若T为R中边的权值之和最小的生成树,则T称为G的最小生成树 (Minimum-Spannimg-Tree.MST)

      1. 最小生成树可能有多个,但边的权值之和总是唯一且最小的

      2. 最小生成树的边数 = 顶点数 - 1。砍掉一条则不连通,增加一条边则会出现回路

      3. 如果一个连通图本身就是一棵树,则其最小生成树就是它本身

      4. 只有连通图才有生成树,非连通图只有生成森林

    2. Prim 算法(普里姆):同一个图可能有多个最小生成树

      1. 从某一个顶点开始构建生成树;

      2. 每次将代价最小的新顶点纳入生成树,直到所有顶点都纳入为止。

      3. 总结:循环:点—该点最短边—点

    3. Kruskal 算法(克鲁斯卡尔)

      1. 每次选择一条权值最小的边,使这条边的两头连通(原本已经连通的就不选)

      2. 直到所有结点都连通

      3. 总结:循环:全局最短边构成一片片岛屿—最后岛屿相连成大陆

    4. 两个算法的比较

克鲁斯卡尔算法和普林姆算法都是用于求解加权连通图的最小生成树的经典算法,但它们在实现方式和特点上有所不同。

克鲁斯卡尔算法的基本思想是按照权值从小到大的顺序选择n-1条边,并保证这些边不构成回路。它首先构造一个只含n个顶点的森林,然后根据权值从小到大从连通网中选择边加入到森林中,并使森林中不产生回路,直至森林变成一棵树为止。克鲁斯卡尔算法的时间复杂度为O(eloge),其中e为网中的边数,因此它适合于求边稀疏的网的最小生成树。

普林姆算法则是从一个起始节点开始,不断选择与当前集合相连且权值最小的边,并将其加入到集合中。在这个过程中,不断扩大当前集合的规模,直到所有的节点都被加入到集合中为止。普林姆算法的时间复杂度与图中顶点的数量有关,因此它在某些情况下可能比克鲁斯卡尔算法更高效。

总的来说,克鲁斯卡尔算法和普林姆算法都是有效的求解最小生成树的算法,它们各有特点,可以根据具体问题的特点选择适合的算法。对于边数较少的稀疏图,克鲁斯卡尔算法可能更为合适;而对于顶点数较少的图,普林姆算法可能更具优势。在实际应用中,可以根据具体情况选择适合的算法进行求解。

  1. 最短路径问题

    1. BFS求无权图的单源最短路径(无权图)

      1. 即构建以出发顶点为根的广度优先生成树

      2. 结点的高度即为最短路径长度

      3. 原理:广度优先生成树的高度是最低的

      4. 缺点:只适用于各边权值相等的图或无权图,即求的是最短的边数

    2. Dijkstra算法:求带权图的单源最短路径(带权图、无权图)

      1. 标记起点为完成路径寻找,起点到起点的距离为0

      2. 列出其他所有点到当前标记点的距离,不直接相连的顶点距离设置为∞

      3. 将距离加在目标点到起点的距离上,若小于原来的路径数据,则更新成最小值

      4. 移到未被标记且距离值最小的点上,重复②③,直到完成。

      5. 与Prim算法的对比

        1. Prim算法每次寻找最短边,不做加法

        2. Dijkstra算法寻找短边要更新最短路径

        3. 二者执行过程相似,复杂度都是O(n²),即O(v²)

      6. 带负权值边的图中Dijkstra算法没有用

    3. Floyd算法求各顶点间最短路径(带权图、无权图)

      1. 列出图的临界矩阵

      2. 考虑一个顶点作为中转点的情况,将邻接矩阵的边更新为最小边,更新边在path矩阵的相应位置填入中转点

      3. 更新后的矩阵继续进行②,直到所有顶点都考虑过,算法完成

  2. 有向无环图(DAG图):若一个有向图中不存在环,则称为有向无环图,简称DAG图 (Directed Acyclic Graph)

    1. 有向无环图简化描述算式

    2. (https://img-home.csdnimg.cn/images/20230724024159.png?origin_url=media%2Fimage49.png&pos_id=img-TCL4uiTJ-1707574201371)

  3. AOV网

    1. AOV网中不允许存在环路(本质是DAG图)

    2. 拓扑排序

      1. 实现

        1. 从AOV网中选择一个没有前驱 (入度为0) 的顶点并输出

        2. 从网中删除该顶点和所有以它为起点的有向边。

        3. 重复1) 和2) 直到当前的AOV网为空或当前网中不存在无前驱的顶点为止(说明有回路)。

      2. 定义

        1. 拓扑排序:在图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该图的一个拓扑排序:

          1. 每个顶点出现且只出现一次。

          2. 若顶点A在序列中排在顶点B的前面,则在图中不存在从顶点B到顶点A的路径。

        2. 或定义为:拓扑排序是对有向无环图的顶点的一种排序,它使得若存在一条从顶点A到顶点B的路径,则在排序中顶点B出现在顶点A的后面。

        3. 每个AOV网都有一个或多个拓扑排序序列

      3. 时间复杂度

        1. 时间复杂度:O(V+E)

        2. 若采用邻接矩阵,则需O(V²)

      4. 逆拓扑排序

        1. 从AOV网中选择一个没有后继 (出度为0) 的顶点并输出

        2. 从网中删除该顶点和所有以它为终点的有向边。

        3. 重复1) 和2) 直到当前的AOV网为空

      5. 逆邻接表:

        1. 正常的邻接表,边表是顶点指向的点,

        2. 逆邻接表,边表是指向顶点的点

      6. DFS算法实现逆拓扑排序

  4. 关键路径

    1. AOE网的概念与性质

      1. 概念:在带权有向图中,以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销(如完成活动所需的时间)称之为用边表示活动的网络,简称AOE网(Activity On Edge NetWork)

      2. AOE网具有以下两个性质

        1. 只有在某顶点所代表的事件发生后,从该顶点出发的各有向边所代表的活动才能开始;

        2. 只有在进入某顶点的各有向边所代表的活动都已结束时,该顶点所代表的事件才能发生。

        3. 另外,有些活动是可以并行进行的

    2. AOE网的关键路径

      1. 在AOE网中

        1. 仅有一个入度为0的顶点,称为开始顶点 (源点),它表示整个工程的开始;

        2. 也仅有一个出度为0的顶点,称为结束顶点 (汇点),它表示整个工程的结束

      2. 从源点到汇点的有向路径可能有多条,所有路径中,具有最大路径长度的路径称为关键路径,而把关键路径上的活动称为关键活动

      3. 完成整个工程的最短时间就是关键路径的长度,若关键活动不能按时完成,则整个工程的完成时间就会延长

    3. 求AOE网关键路径(事件:顶点,活动:边)

      1. 两个最早:(从前往后推)

        1. 事件v_(k)的最早发生时间ve(k)——决定了所有从v_(k)开始的活动能够开工的最早时间

        2. 活动a_(i)的最早开始时间e(i)——指该活动弧的起点所表示的事件的最早发生时间

      2. 两个最迟:(从后往前推)

        1. 事件v_(k)的最迟发生时间vl(k)——它是指在不推迟整个工程完成的前提下,该事件最迟必须发生的时间

        2. 活动a_(i)的最迟开始时间1(i)——它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差

      3. 活动a_(i)的时间余量:d(i)=1(i)-e(i)——表示在不增加完成整个工程所需总时间的情况下,活动a_(i)可以拖延的时间

      4. 若一个活动的时间余量为零,则说明该活动必须要如期完成,d(i)=0即1(i)=e(i)的活动a_(i)是关键活动

      5. 由关键活动组成的路径就是关键路径

      6. 求关键路径的方法

      7. 关键活动、关键路径的特性

        1. 若关键活动耗时增加,则整个工程的工期将增长

        2. 缩短关键活动的时间,可以缩短整个工程的工期

        3. 当缩短到一定程度时,关键活动可能会变成非关键活动

        4. 可能有多条关键路径,只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期,只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。

  • 理解
  1. 最短路径一定是简单路径

  2. 最小生成树的算法基于贪心策略,每次都选取权值最小且满足条件的边,如果各边权值不同,则每次选择的新顶点也是唯一的,因此最小生成树也唯一

  3. 求关键路径过程的描述

    1. 事件最早发生时间Ve:起点为0,其他点取各入度路径长度中最大的(上一个指向该点的点的最早时间加上边的长度的最大值)

    2. 事件最晚发生时间Vl:终点为其最早发生时间,其他为各出度路径长度中最小的(上一个由该点指向点的最晚时间减去边长度的最小值)

    3. 活动最早发生时间e:边的最早发生时间,即为该有向边起点(无箭头一端)的最早发生时间

    4. 活动最晚发生时间l:边的最晚发生时间,即为该有向边终点(有箭头一端)的最晚发生时间减去该边的权值

  • 技巧
  1. 无向连通图存在权值相同的多条边时,最小生成树可能不是唯一的

  2. 无向连通图的最小生成树一定存在

  3. Dijkstra算法适合求解有回路的带权图的最短路径,也可以求两个顶点的最短路径

  4. Floyd算法求两个顶点的最短路径时,当最短路径发生改变,path_(k)会在path_(k-1)的基础上更新,因此二者会失去子集关系

  5. 能判断有向图是否有环的方法

    1. 深度优先遍历:生成树上:下一个结点是当前结点的父节点

    2. 拓扑排序:存在入度消不掉的点

  6. 若有向图的拓扑有序序列唯一,每个顶点的入度和出度不一定为1,例如下图:

  7. 拓扑排序中每一次操作都溢出当前入度为0的结点,如果一次移除若干个结点,这些结点的先后顺序不影响正确性,因此如果需要暂存,使用栈或队列都可以

  8. 顶点数大于1的强连通分量=环

  9. 若一个有向图具有有序的拓扑排序序列(0,1,2,3,…)则邻接矩阵一定上三角

  10. 有向图的邻接矩阵中,主对角线以下元素均为0,则该图的拓扑序列,存在且不唯一,例如:三点两边有向图:①→②,①→③,有两个拓扑序列

  11. 强连通分量数目的计算:

    1. 当一个顶点没有入度时表明没有别的点能够到达它,因此该点组成一个强连通分量

    2. 环构成一个强连通分量

  12. Dijkstra算法高度相似Prim算法,但是Dijkstra算法在求生成树时,未必能求到最小生成树

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

如若内容造成侵权/违法违规/事实不符,请联系编程新知网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Git 分支管理

Git 分支管理 | CoderMast编程桅杆Git 分支管理 在 Git 中,分支是指向提交对象(commits)的可变指针。它们是一系列提交的引用,其中的每个提交都包含了一组文件的状态以及指向其父提交的指针。主要的分支通常是 master 或 main&…

1.C++入门

目录 1.C关键字 2.命名空间 作用域方面的优化 a.命名空间定义 b.命名空间使用 3.C 输入&输出 1.C关键字 C有63个关键字,C语言有32个关键字,存在重叠如荧光笔标出 2.命名空间 作用域方面的优化 如果变量,函数和类的名称都存在于全…

近年数一,数二难度如何,听说24是像张宇那样的题?

直接上分数! “估分一百零几,平时李林130-140,张八110-125的样子,超越做的分数也是100出头。” 24学长说: “远离李林张八!张四没做不评价。” “李林张八暑假前做完当作打基础即可。超越才是真题难度”…

要养生也要时尚,益百分满足你的所有需求

要养生也要时尚,益百分满足你的所有需求 艾灸是个好东西,尤其是在近几年的时候,艾灸就像一阵浪潮席卷进了人们的日常生活之中,我们可以在街边看到大大小小的艾灸馆,有些评价比较高的艾灸馆门前甚至还排起了长长的队伍…

数据库服务类--Redis--未授权访问终端Getshell

免责声明:本文仅做技术交流与学习. 目录 前提条件: windows上开启redis服务: Linux上创建&开启redis服务: 操作: 1-连接靶机redis 2-写入webshell 3-访问后门 redis--->webshell Redis未授权访问漏洞复现与利用 - 知乎 (zhihu.com) 前提条件: 端口开放(6379) 目录…

51单片机之DS1302实时时钟

1.DS1302时钟芯片介绍 DS1302是由美国DALLAS公司推出的具有涓细电流充电能力的低功耗实时时钟芯片。它可以对年、月、日、周、时、分、秒进行计时,且具有闰年补偿等多种功能RTC(Real Time Clock):实时时钟,是一种集成电路,通常称…

【ARM 裸机】C 语言 led 驱动

前面刚学习了汇编 led 驱动的编写和验证,现在开始就要进入 C 语言 led 驱动编写与验证了 ! 1、C 语言运行环境构建 1.1、设置处理器模式 使 6ULL 处于 SVC 模式下,之前已经提到了处理器的九种模式,参考:【ARM 裸机】汇编 led 驱…

关基网络战时代,赛宁网安电力网络攻防靶场全面提升电网安全防护力

随着网络空间成为与陆地、海洋、天空、太空同等重要的人类活动新领域,自网络空间向物理电网发起攻击,破坏电力等国家关键基础设施成为当前大国博弈、大规模战争的重要手段和常态进攻形式。同时,新型电力系统建设发展驱动电力系统形态和控制方…

Linux开机启动流程

Linux开机启动流程详细步骤如下图: 其中: POST:Power On Self Test --加电自检 BIOS: Basic Input Output System --基础输入输出系统 MBR: Master Boot Record --主引导记录 GRUB: GRand Uni…

基于SSM+Vue的护工预约服务小程序和后台管理系统

1、系统演示视频(演示视频) 2、需要请联系

NLP大模型的训练

NLP模型的训练主要分成两步: 1.先进行通用任务的训练;无监督的样本是无穷无尽的; 这里列举两种:MLM和NSP,NSP由于在某些论文中被证明是无效的,所以用的少; MLM: 接下来会在特定任务上进行finetune>su…

如何使用 ArcGIS Pro 快速为黑白地图配色

对于某些拍摄时间比较久远的地图,限于当时的技术水平只有黑白的地图,针对这种情况,我们可以通过现在的地图为该地图进行配色,这里为大家讲解一下操作方法,希望能对你有所帮助。 数据来源 教程所使用的数据是从水经微…

pytorch-过拟合欠拟合

目录 1. 函数表达能力2. 模型表达能力3. 欠拟合4. 过拟合5 总结 1. 函数表达能力 如下图:不同次方的函数的复杂度是不一样的,越复杂的函数表达能力越强 2. 模型表达能力 如下图:有三种复杂度的模型,分别是8层、19层和152层&am…

OpenHarmony开发实例:【 待办事项TodoList】

简介 TodoList应用是基于OpenHarmony SDK开发的安装在润和HiSpark Taurus AI Camera(Hi3516d)开发板标准系统上的应用;应用主要功能是以列表的形式,展示需要完成的日程;通过本demo可以学习到 JS UI 框架List使用; 运行效果 样例…

FebHost:CO域名在搜索引擎排名中是否高于.COM域名?

.CO 域名在搜索引擎结果中有可能取得高于 .COM 域名的排名,但要注意的是,域名的后缀本身并不会直接影响其搜索排名。决定网站在搜索引擎中的排名的主要因素是搜索引擎优化(SEO)实践的有效性,包括内容的质量、关键词的使…

ContextMenuStrip内容菜单源对象赋值学习笔记(含源码)

一、前言 MetroTileItem属于第三方控件,无法定义ContextMenuStrip属性 想实现某子项点击菜单时,与源控件(按钮metroTileItem)的某值对应,用于动态控制按钮的状态或方法 1.1 效果 二、实现方法 2.1 方法1 (代码,说明见注释) private void metroTileItem_MouseDown(o…

前端性能分析工具及使用

Lighthouse Lighthouse (谷歌浏览器的插件商店中搜索并安装,浏览器中点击F12,开发者工具中可使用)是 Google 开发的一款工具,用于分析网络应用和网页,收集现代性能指标并提供对开发人员最佳实践的意见。只要…

[图解]软件开发中的糊涂用语-04-为什么要追究糊涂用语

0 00:00:00,030 --> 00:00:05,620 今天呢,我们来说一个为什么要追究糊涂用语的问题 1 00:00:06,310 --> 00:00:06,548 2 00:00:06,548 --> 00:00:11,077 大家知道我们前些天都发了好几个视频 3 00:00:11,077 --> 00:00:13,461 追究这个糊涂用语 4 00…

(mac)Prometheus监控之Node_exporter(CPU、内存、磁盘、网络等)

完整步骤 1.启动 Prometheus 普罗米修斯 prometheus --config.file/usr/local/etc/prometheus.yml 浏览器访问 http://localhost:9090/targets 2.启动Node_exporter node_exporter 访问:http://localhost:9100 3.启动grafana brew services start grafana 访问…