图的学习.

目录

一、图的基本概念

1.1图的种类

1.2顶点的度、入度和出度

1.3边的权和网

1.4路径、路径长度和回路

二、图的存储结构

2.1邻接矩阵法

2.2邻接表法

2.3十字链表

2.4邻接多重表

三、图的遍历

3.1广度优先搜索

3.2深度优先搜索

四、图的应用

4.1最小生成树

4.1.1普里姆算法

4.1.2克鲁斯卡尔算法

4.2最短路径

4.2.1迪杰斯特拉算法

 4.3拓扑排序

 4.4关键路径


一、图的基本概念

1.1图的种类

①有向图:v,w表示顶点,顶点间的边是有方向的。

②无向图:v,w表示顶点,顶点间的边没有方向。

③简单图:不存在重复边,不存在顶点到自身的边。

④多重图:存在重复边,存在顶点到自身的边。

⑤完全图:(简单完全图)

对于无向图,任意两个顶点之间都存在边,边的条数:(n*(n-1))/2

对于有向图,任意两个顶点之间都存在方向相反的两条弧,边的条数:n*(n-1)

子图: 顶点和边是另一个图的子集的图。

第二个图的顶点和边都是第一个图的子集,所以图2是图1的子图。

生成子图:顶点相等,边是另一个图的子集的图。

第二个图的顶点和第一个图相等,边是它的子集,所以图2是图1的生成子图。

连通图:图中任意两个顶点都是连通的。

极小连通子图:既要保持图连通又要使得边数最少的子图。

⑧生成树:包含图中全部顶点的一个极小连通子图。(边数=顶点数-1)

图2是图1的生成树。

1.2顶点的度、入度和出度

度:一个顶点连接的边数

①对于无向图:其全部顶点的度的和等于边数的2倍

②对于有向图:

·入度是以顶点v为终点的有向边的数目,出度是以顶点v为起点的有向边的数目;

·顶点的度=入度和出度之和;

·有向图的全部顶点的入度之和与出度之和=,并且=边数。

1.3边的权和网

权:边上带有数值,这样的图称为带权图或网

1.4路径、路径长度和回路

路径:顶点到另一个顶点的路线

路径长度:顶点到另一个顶点的距离

回路:从某一个顶点出发,最后又回到这个顶点

二、图的存储结构

2.1邻接矩阵法

行列与顶点有关,与边无关

①对于无向图:A[i][j]=1,(vi,vj)存在;A[i][j]=0,(vi,vj)不存在 (对称矩阵)

②对于有向图:A[i][j]=1,(vi,vj)存在;A[i][j]=0,(vi,vj)不存在

③对于带权图:A[i][j]=权值,(vi,vj)存在;A[i][j]=0或无穷大,(vi,vj)不存在

问:

①n个顶点的无向连通图用邻接矩阵表示时,该矩阵至少有2(n-1)个非零元素。

(有n-1条边,每条边表示两次)

②带权有向图G用邻接矩阵A存储,则顶点i的入度等于A中第i列非零非无穷元素之和,出度即为A中第i行非零非无穷元素之和

2.2邻接表法

①对于无向图

存储空间=O(|V|+2|E|) ,顶点存储1次,而边存储了2次。

②对于有向图

存储空间=O(|V|+|E|),边和顶点都只存储了1次。

特点:

①对于稀疏图,采用邻接表表示能够节省空间

②图的邻接表表示不唯一

③在有向图的邻接表表示中,求一个给定顶点的出度只需计算其邻接表中的结点个数。

头结点指的是顶点,表结点指的是边。

2.3十字链表

针对无向图的邻接表法结点的入度难,采用十字链表法改进

2.4邻接多重表

针对无向图中邻接表边存储2次的问题,采用邻接多重表法改进。

三、图的遍历

定义:从图中的某一点出发,按照某种搜索方法沿着图中所有顶点访问一次且仅访问一次

算法:广度优先搜索,深度优先搜索

3.1广度优先搜索

类似于二叉树的先序遍历,类似于树的层次遍历,例:

3.2深度优先搜索

类似于树的先序遍历,例:

注:如果从一个无向图的任意顶点出发进行一次广度和深度优先搜索即可访问所有顶点,那么该图一定是连通图。

四、图的应用

4.1最小生成树

带权连通无向图中,所有生成树中权值之和最小的生成树。

4.1.1普里姆算法

①任取一顶点,去掉所有边

②选择一个与当前顶点集合距离最近的顶点,并将该顶点和相应的边加入进来,同时不能形成回路。

③重复②,直至图中所有顶点都并入。

4.1.2克鲁斯卡尔算法

①去掉所有边

②选边(权最小,且不构成回路)

③重复②,直至图中所有顶点都并入

 最小生成树边数=顶点数-1

4.2最短路径

4.2.1迪杰斯特拉算法

 4.3拓扑排序

·AOV网:顶点表示活动,<Vi,Vj>

·每个顶点出现且只出现一次,若存在一条从顶点A到顶点B的路径,则在排序中顶点B出现在顶点A的后面。

算法实现:

①从AOV网中选择一个没有前驱的顶点并输出

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

③重复①②直到当前AOV网为空或当前网中不存在无前驱的顶点为止

 

4.4关键路径

·AOE网:以顶点表示事件,以有向边表示活动,以边上的权值表示完成该活动的开销

·关键路径:从开始顶点到结束顶点的所有路径中,具有最大路径长度的路径

·关键活动:关键路径上的活动

算法实现:

①令ve(源点)=0,求最早发生时间ve()

ve()=Max{ve(j)+weight(vj,vk)} (从前往后算)

②令vl(汇点)=ve(汇点),求最迟发生时间vl()

vl()=Min{vl(j)-weight(vk,vj)} (从后往前算)

③根据ve()值求所有弧的最早开始时间e()

e()=ve()

④根据vl()值求所有弧的最迟开始时间l()

l()=vl()-weight(vk,vj)

⑤求AOE网中所有活动的差额d(),找出所有d()=0的活动构成关键路径

d()=l()-e()

例:

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

密码没有未来

无密码认证的好处 引领无密码未来之路万能钥匙 英国通过具体法律打击可预测密码 强密码是抵御网络威胁的第一道防线 如何破解价值百万美元的加密钱包密码 复制此链接到微信打开阅读全部以发布文章 新 GPU 在不到一小时内打开了网络上 59% 的密码。 现代计算机的能力不断增…

AGV机器人的调度开发分析(1)- 内核中的路线规划

准备开始写一个系列&#xff0c;介绍下AGV机器人的调度的开发和应用。 按照openTCS的核心内容&#xff0c;国内多家广泛应用于AGV的调度。那么架构图如下&#xff1a; Kernel中有一个是Routing&#xff0c;这是路由规划模块&#xff0c;需要实现的细节功能包括如下&#xff1a…

cesium 包络线

cesium 包络线 以下为源码直接复制可用 1、实现思路 通过turf.js中union方法来计算包络线官方地址:https://turfjs.fenxianglu.cn/ 闪烁线请查看cesium轨迹线(闪烁轨迹线) 2、示例代码 <!DOCTYPE html> <html lang="en"&g

Pwn刷题记录(不停更新)

1、CTFshow-pwn04&#xff08;基础canary&#xff09; ​ 好久没碰过pwn了&#xff0c;今天临时做一道吧&#xff0c;毕竟刚联合了WSL和VSCode&#xff0c;想着试着做一道题看看&#xff0c;结果随手一点&#xff0c;就是一个很少接触的&#xff0c;拿来刷刷&#xff1a; ​ …

计算机组成原理 —— 存储系统(DRAM和SRAM,ROM)

计算机组成原理 —— 存储系统&#xff08;DRAM和SRAM&#xff09; DRAM和SRAMDRAM的刷新DRAM地址复用ROM&#xff08;Read-Only Memory&#xff08;只读存储器&#xff09;&#xff09; 我们今天来看DRAM和SRAM&#xff1a; DRAM和SRAM DRAM&#xff08;动态随机存取存储器&…

springboot 酒庄内部管理系统(源码+sql+论文)

绪论 1.1 系统研究目的意义 随着信息技术的不断发展&#xff0c;我们现在已经步入了信息化的时代了&#xff0c;而信息时代的代表便是网络技术的日渐成熟&#xff0c;而现在网络已经和我们的生活紧密的联系起来了&#xff0c;我们不敢想象没有网络我们的生活会像怎么样&#…

六、资产安全—数据管理(CISSP)

目录 1.学习目标 2.数据管理最佳参考实践 3.数据质量维度:DAMA 4.数据生命周期控制 5.数据净化方式 6.生命周期安全控制 7.EOL、EOS、EOSL 1.学习目标 2.数据管理最佳参考实践 数据策略: 角色与责任: 数据所有权:

数据分析必备:一步步教你如何用matplotlib做数据可视化(10)

1、Matplotlib 二维箭头图 箭头图将速度矢量显示为箭头&#xff0c;其中分量(u&#xff0c;v)位于点(x&#xff0c;y)。 quiver(x,y,u,v)上述命令将矢量绘制为在x和y中每个对应元素对中指定的坐标处的箭头。 参数 下表列出了quiver()函数的参数 - x - 1D或2D阵列&#xff0c;…

C语言中的进制转换

基础概念 进制又称数制&#xff0c;是指用一组固定的符号和统一的规则来表示数值的方法&#xff0c;在C语言中&#xff0c;可以使用不同的前缀来表示不同的进制&#xff1a; 二进制&#xff1a;以0b或0B为前缀&#xff08;部分编译器可能不支持&#xff09;八进制&#xff1a…

Go日常分享 - error类型是指针类型吗?

背景 这个问题的产生来源于小泉在开发rpc接口时返回error遇到的问题&#xff0c;开发时想在defer里对err进行最终的统一处理赋值&#xff0c;发现外层接收一直都未生效。问题可以简化为成下面的小demo。 func returnError() error {var err errordefer func() {//err errors…

物联网系统运维——数据库部署

一.MySQL 1.概要 MySQL是一种关联数据库管理系统&#xff0c;关联数据:而不是将所有数据放在一个大仓库内&#xff0c;这样就增加了速度并提高了灵活性库将数据保存在不同的表中。性能高、成本低、可靠性好&#xff0c;已经成为最流行的开源数据库。 二.MySQL安装与配置 1. …

38.MessageToMessageCodec线程安全可被共享Handler

handler被注解@Sharable修饰的。 这样的handler,创建一个实例就够了。例如: ByteToMessageCodec的子类不能被@Sharable修饰 如果自定义类是MessageToMessageCodec的子类就是线程共享的,可以被@Sharable修饰的 package com.xkj.protocol;import com.xkj.message.Message; i…

浙大宁波理工学院2024年成人高等继续教育招生简章

浙大宁波理工学院&#xff0c;这所承载着深厚学术底蕴和卓越教育理念的学府&#xff0c;正热烈开启2024年成人高等继续教育的招生之门。这里&#xff0c;是知识的殿堂&#xff0c;是智慧的摇篮&#xff0c;更是您实现个人梦想、追求更高境界的起点。 ​浙大宁波理工学院始终坚…

[最全]设计模式实战(一)UML六大原则

UML类图 UML类图是学习设计模式的基础,学习设计模式,主要关注六种关系。即:继承、实现、组合、聚合、依赖和关联。 UML类图基本用法 继承关系用空心三角形+实线来表示。实现接口用空心三角形+虚线来表示。eg:大雁是最能飞的,它实现了飞翔接口。 关联关系用实线箭头来表示…

基础算法---滑动窗口

文章目录 什么是滑动窗口1.长度最小的子数组2.无重复字符的最长子串3.最大连续1的个数4.将x减到0的最小操作数5.最小覆盖子串总结 什么是滑动窗口 滑动窗口&#xff08;Sliding Window&#xff09;是一种在计算机科学中用于解决各种子数组或子字符串问题的技术。滑动窗口技术通…

在 Mac 上恢复已删除的文件夹

“嗨&#xff0c;我刚刚运行了重复文件查找器应用程序 Gemini 来扫描我的 Mac 以清除重复文件。它找到了很多重复的文件和文件夹&#xff0c;只需单击一下&#xff0c;它就可以帮助我删除重复的文件/文件夹。但我认为它可能会删除一些有用的重复文件。我打开垃圾箱&#xff0c;…

主数据驱动的数据治理:技术解析与实践探索

数字化转型行业小伙伴可以加入我的星球&#xff0c;初衷成为各位数字化转型参考库&#xff0c;星球内容每周更新 个人工作经验资料全部放在这里&#xff0c;包含数据治理、数据要素、数据质量、数据安全、元数据、主数据、企业架构、DCMM、DSMM、CDGA、CDGP等各种数据相关材料 …

AOP应用之系统操作日志

本文演示下如何使用AOP&#xff0c;去实现系统操作日志功能。 实现步骤 引入AOP包 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-aop</artifactId><version>2.6.6</version></de…

AI大眼萌探索 AI 新世界:Ollama 使用指南【1】

在人工智能的浪潮中&#xff0c;Ollama 的出现无疑为 Windows 用户带来了一场革命。这款工具平台以其开创性的功能&#xff0c;简化了 AI 模型的开发与应用&#xff0c;让每一位爱好者都能轻松驾驭 AI 的强大力量。大家好&#xff0c;我是AI大眼萌&#xff0c;今天我们将带大家…

颠覆多跳事实验证!Causal Walk 前门调整技术引领去偏新纪元

Causal Walk: Debiasing Multi-Hop Fact Verifcation with Front-Door Adjustment 论文地址: Causal Walk: Debiasing Multi-Hop Fact Verification with Front-Door Adjustment| Proceedings of the AAAI Conference on Artificial Intelligencehttps://ojs.aaai.org/index.p…