首页 > 编程语言 >数据结构与算法 第10天(图的应用)

数据结构与算法 第10天(图的应用)

时间:2024-09-06 20:24:14浏览次数:12  
标签:10 -- 路径 生成 算法 集合 顶点 数据结构

一、最小生成树

生成树:所有顶点均由边连接在一起,但不存在回路

一个图可以有多颗不同的生成树

 生成树特点:生成树的顶点个数与图的顶点个数相同;

生成树是图的极小连通子图,去掉一条边则非连通,

一个有 n个顶点的连通图的生成树有 n-1 条边;

在生成树中再加一条边必然形成回路,

生成树两点之间路径是唯一的;

无向图生成树:深度优先遍历,广度优先遍历,遍历每个点

最小生成树:所有边权值之和最小

构造最小生成树:

MST贪心算法

普里姆(Prim)算法

把所有点分为A,B两个集合,任意选一个顶点a放到A集合,其余点放到B集合

选一个B集合中,到a权值最小的点b,放入A集合

再选一个B集合中,到a或者b权值最小的点,放入A集合        以此类推。

克鲁斯卡尔(Kruskal)算法

所有边按权值排序,依次把最小的边连上,不能形成回路否则舍去选取下一条边

两种算法比较

二、最短路径

两点间最短路径

迪杰斯特拉算法

求某一个顶点到其他顶点最短距离

先找直 达的最短路径,然后再找更短的路径替换

所有顶点间最短路径

弗洛伊德(Floyd)算法

逐个加顶点试探 

三、有向无环图

AOV网:

AOE网:

四、拓扑排序

针对有向无环(DAG)图        AOV网

方法

在有向图中选一个没有前驱的顶点且输出。

从图中删除该顶点和所有以它为尾的弧。

重复上述两步,直至全部顶点均已输出;或者当图中不存在无前驱的顶点为止

拓扑序列不唯一

作用

检测AOV网中是否存在环

五、关键路径

针对有向无环(DAG)图        AOE网

源点:入度为0的顶点
汇点:出度为0的顶点

对于AOE网,关心两个问题

完成整项工程至少需要多少时间?

哪些活动是影响工程进度的关键?

关键路径 -- 路径长度最长的路径,
路径长度 -- 路径上各活动持续时间之和

几个描述量

ve(vj)-- 表示事件 vj 的最早发生时间。

v(vj)-- 表示事件 vj 的最迟发生时间。

e(i) -- 表示活动 ai 的最早开始时间

I(i)-- 表示活动 ai 的最迟开始时间

I(i)- e(i) -- 表示完成活动(ai 的时间余量

关键活动 -- 关键路径上的活动,即|(i) == e(i)(即|(i)-e(i)==0 )的活动。

标签:10,--,路径,生成,算法,集合,顶点,数据结构
From: https://blog.csdn.net/2301_79600945/article/details/141936956

相关文章

  • 使用centos7搭建RAID磁盘阵列,RAID0,RAID1,RAID5,ARID10,讲述RAID0、1、5、10的原理。
    1.RAID概念磁盘阵列(RedundantArraysofIndependentDisks,RAID),有“独立磁盘构成的具有冗余能力的阵列”之意。磁盘阵列是由很多价格较便宜的磁盘,以硬件(RAID卡)或软件(MDADM)形式组合成一个容量巨大的磁盘组,利用多个磁盘组合在一起,提升整个磁盘系统效能。利用这项技术,将数据切割......
  • 828华为云征文|华为云Flexus X实例部署安装HivisionIDPhoto一个轻量级的AI证件照制作算
    背景最近有一个开源项目非常火,就是HivisionIDPhotos一个轻量级的AI证件照制作算法github仓库https://github.com/Zeyi-Lin/HivisionIDPhotos由于最近华为云最近正在举办B2B企业节,FlexusX实例的促销力度非常大。所以购买了一个FlexusX实例。4核12G。准备安装一个,试一......
  • 数据结构 栈 队列
    系统栈:保护局部变量函数的形参和返回值函数的调用关系(保护现场,恢复现场操作,遵循先进后出,后进先出)数据结构栈(顺序栈,链式栈):同样遵遵循先进后出,后进先出原则只允许从一端进行数据的插入和删除的线性存储结构数据的插入--->入栈     数据的删除----->出栈顺序栈:......
  • 队列-数据结构
    一、队列FIFO特点:先进先出,后进后出允许从一段插入数据,另一端删除数据的线性存储结构队尾:插入数据入队队头:删除数据出队管道实质上也是一个队列。用途:缓存数据(主要是避免两者速度不匹配的,数据存取速度不匹配。)二、队列类型2.1、顺序队列顺序队列---------》假溢出--......
  • 识别并应对动态归纳类算法题:深入剖析与实战指南
    《识别并应对动态归纳类算法题:深入剖析与实战指南》在编程的世界里,算法题犹如一座座充满挑战的山峰,等待着开发者们去攀登。其中,动态归纳类算法题因其复杂性和灵活性,常常成为开发者们进阶路上的一道难关。本文将深入探讨如何识别并应对动态归纳类算法题,为大家提供一份全面的......
  • 72. 编辑距离算法实现详解
    LeetCode72.编辑距离详解一、题目描述给你两个单词word1和word2,请返回将word1转换成word2所使用的最少操作数。你可以对一个单词进行如下三种操作:插入一个字符。删除一个字符。替换一个字符。示例1:输入:word1="horse",word2="ros"输出:3解释:horse......
  • 青少年编程与数学 01-010 青少年成长管理 第五章 资源 2_2 成长资源
    青少年编程与数学01-010青少年成长管理第五章资源2_2成长资源第二节成长资源一、什么是成长资源二、成长资源的分类三、教育资源四、媒体资源五、情感资源六、物质资源分类七、社交资源八、文化资源九、环境资源十、健康资源十一、机会资源十二、资源的利用(一)儿童......
  • DFS算法专题(一)——二叉树中的深搜【回溯与剪枝的初步注入】
    目录1、DFS算法简介2、算法实战应用【leetcode】2.1计算布尔二叉树的值2.1.1算法原理 2.1.2算法代码2.2求根节点到叶节点数字之和  2.2.1算法原理​2.2.2算法代码2.3二叉树剪枝2.3.1算法原理2.3.2算法代码2.4验证二叉搜索树 2.4.1算法原理 2.4.2......
  • 人脸识别ArcFace 算法原理与实现
    在深度学习用于人脸识别方面,为了提高识别的准确率,研究者提出了ArcFace技术。ArcFace通过在Softmax损失函数上添加一种角度余弦距离的margin来提高人脸识别的准确率,ArcFace始终优于SOTA,且容易实现,计算开销可忽略不计。论文:ArcFace:AdditiveAngularMarginLossforD......
  • Windows10添加鼠标右键打开
    1打开注册表2.进入目录计算机\HKEY_CLASSES_ROOT\Directory\Background\shell\,新建项,2.1继续新建子项,重命名为command2.2修改子项中的默认,添加路径结果:ps:可以重命名。在第一个新建项中新建“字符串值”,重命名为“ICON”可以设置图标。效果图:......