【数据结构】六、图:3.十字链表、邻接多重表、边集数组

3.十字链表(有向图)

文章目录

    • 3.十字链表(有向图)
      • 3.1性能分析
    • 4.邻接多重表(无向图)
      • 4.1性能分析
    • 5.边集数组

十字链表是有向图的一种链式存储结构。

  • 不足

对于有向图来说,邻接表是有缺陷的。了解入度就必须要遍历整个图才能知道;反之,逆邻接表解决了入度却不了解出度的情况。

  • 十字链表(Orthogonal List)

邻接表逆邻接表结合起来就是我们现在要介绍的有向图的一种存储方法:十字链表(Orthogonal List)

顶点结点结构:

datafirstinfirstout

firstin:表示作为入边表头指针,指向该顶点的入边表中第一个结点;
firstout:表示作为出边表头指针,指向该顶点的出边表中的第一个结点。

边结点结构:

tailvexheadvexinfoheadlinktaillink

tailvex:是指弧起点在顶点表的下标;
headvex:是指弧终点在顶点表中的下标;
headlink:是指入边表指针域,指向终点相同的下一条边;
taillink:是指边表指针域,指向起点相同的下一条边。

如果是网,还可以再增加一个 info 域来存储权值。

在这里插入图片描述

3.1性能分析

空间复杂度:顶点个数+边的个数 O(|V|+|E|)

在此把邻接表逆邻接表结合起来,解决了存储时候,有冗余的问题,也更容易求得顶点的出度和入度。而且它除了结构复杂一点外,其实创建图算法的时间复杂度是和邻接表相同的。

4.邻接多重表(无向图)

邻接多重表是无向图的另一种链式存储结构。

  • 不足

在邻接表中,容易求得顶点和边的各种信息,但每条边对应两条冗余信息。删除顶点、删除边等操作时,需要分别在两个顶点的边表中遍历,效率较低。

eg. 如果要删除一条边,那么在邻接表中,要在两个顶点(边的两端点)的单链表中进行边的删除。

若要删除左图的( V0 , V2 )这条边,需要对邻接表结构中右边表的阴影两个结点进行删除操作,显然这是比较烦琐的。

在这里插入图片描述

  • 邻接多重表(adjacent multiList)

顶点结点结构:

datafirstedge

data 域存储该顶点的相关信息;
firstedge 域指示第一条依附于该顶点的边。

边结点结构:

ivexjvexinfoilinkjlink

ivex和jvex是与某条边依附的两个顶点在顶点表中下标。
ilink 指向依附顶点ivex的下一条边,jlink 指向依附顶点jvex的下一条边。

如果是网,还可以再增加一个 info 域来存储权值。

在这里插入图片描述

删除一条边,就改变它的两个link指针。

在这里插入图片描述

删除一个顶点,那么就把对应的边表清空。

在这里插入图片描述

4.1性能分析

空间复杂度:顶点个数+边的个数 O(|V|+|E|)

删除边、结点等的操作很方便。

5.边集数组

边集数组是由两个数组构成。一个是存储顶点的信息;另一个是存储边的信息。

这个边数组每个数据元素由一条边的起点下标(begin)、 终点下标(end)和权(weight)组成,如下图所示:

在这里插入图片描述

显然边集数组关注的是边的集合,在边集数组中要查找一个顶点的度需要扫描整个边数组,效率并不高。因此它更适合对边依次进行处理的操作,而不适合对顶点相关的操作。

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

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

相关文章

Go语言fmt包中print相关方法

Go语言的fmt包提供了多种打印相关的函数,主要用于在控制台或其他输出目标上格式化并输出数据。下面是一些常用的print相关方法的用途和区别: 1.fmt.Print() 功能: fmt.Print() 将参数的内容按默认格式输出到标准输出(通常是控制台&#xff…

【从零开始一步步学习VSOA开发】发布订阅服务端

发布订阅服务端 概念 **发布订阅模式(Publish-Subscribe Pattern)**是一种消息传递模式,其中发布者发布消息,而订阅者接收和处理这些消息。它是一种松耦合的通信方式,允许发布者和订阅者在不知道彼此存在的情况下进行…

【C++】面向对象三大特性之—— 多态(从底层带你理解多态)

目录 前言 什么是多态 多态的定义及实现 虚函数 虚函数的重写 多态的构成条件 虚函数重写的两个例外 协变 析构函数的重写(重要!!!) override 和 final(了解) override final 重载、…

linux 查看端口占用并处理

lsof 命令 lsof -i:端口注意pid netstat 命令 netstat -tnpla | grep 端口注意pid 查看详情 ps -ef | grep 3766607删除 kill -9 PIDkill -9 3766607

【整数规划】+【0—1规划】解决优化类问题(Matlab代码)

目录 文章目录 前言 一、整数规划 分类: 二、典例讲解 1.背包问题 2.指派问题 总结 前言 如果觉得本篇文章还不错的话,给作者点个赞鼓励一下吧😁😁😁 在规划问题中,有些最优解可能是分数或小数&am…

SpringBoot+Vue3+SSE实现实时消息语音播报

目录 1、前言 2、什么是SSE 2.1、与WebSocket有什么异同? 3、代码实现 3.1、前置代码 3.2、SSE相关代码 3.3、消息类相关代码 3.4 、前端代码 4、实机演示 1、前言 有这样一个业务场景,比如有一个后台管理系统,用来监听订单的更新&…

【NUCLEO-G071RB】010——TIM6-基本定时器

NUCLEO-G071RB:010——TIM6-基本定时器 基本定时器设计目标芯片配置程序修改运行测试 基本定时器 基本定时器只能用于计时,可以配置有无上溢出中断,它基本到不支持下溢出中断。它的时钟源(应该)是TPCLK,内…

ChatGPT首次被植入人类大脑:帮助残障人士开启对话

马斯克在脑机接口中最强大的竞争对手Synchron有了新的技术进展,他们首次将ChatGPT整合到其脑机系统中,以使瘫痪患者更容易控制他们的数字设备。Synchron凭借其独特的脑机接口(BCI)技术脱颖而出,该技术巧妙地运用了成熟…

【npm】如何将自己的插件发布到npm上

前言 简单说下 npm 是什么: npm 是一个 node 模块管理工具,也是全球最大的共享源。 npm 工具与 nodejs 配套发布,便利开发人员共享代码。npm 主要包括 npm 官方网站、CLI(控制台命令行工具)、和 registry(…

「Pytorch」BF16 Mixed Precision Training

在深度学习领域,神经网络的训练性能瓶颈常常出现在 GPU显存的使用上。主要表现为两方面: 单卡上可容纳的模型和数据量有限;显存与计算单元之间的带宽和延迟限制了运算速度; 为了解决显卡瓶颈的问题,涌现了不同的解决…

Arduino控制带编码器的直流电机速度

Arduino DC Motor Speed Control with Encoder, Arduino DC Motor Encoder 作者 How to control dc motor with encoder:DC Motor with Encoder Arduino, Circuit Diagram:Driving the Motor with Encoder and Arduino:Control DC motor using Encoder feedback loop: How …

深度学习碎碎念——碎片知识1

1、什么叫模型收敛?什么叫模型欠拟合和过拟合? 什么叫模型收敛?——模型收敛是指在训练过程中,模型的损失函数逐渐减小并且趋于稳定的状态。简而言之,当模型的训练过程达到一个稳定的点,使得进一步的训练不…

CV党福音:YOLOv8实现语义分割(一)

前面我们得知YOLOv8不但可以实现目标检测任务,还包揽了分类、分割、姿态估计等计算机视觉任务。在上一篇博文中,博主已经介绍了YOLOv8如何实现分类,在这篇博文里,博主将介绍其如何将语义分割给收入囊中。 YOLOv8语义分割架构图 …

【C++】特殊类的设计与类型转换

文章目录 1. 特殊类的设计1.1 不能被拷贝的类1.2 只能在堆上创建对象的类1.3 只能在栈上创建对象的类1.4 不能被继承的类1.5 只能创建一个对象的类(单列模式) 2. 类型转换2.1 C/C的类型转换2.2 C规定的四种类型转换2.2.1 static_cast2.2.2 reinterpret_c…

【吊打面试官系列-Elasticsearch面试题】对于 GC 方面,在使用 Elasticsearch 时要注意什么?

大家好,我是锋哥。今天分享关于 【对于 GC 方面,在使用 Elasticsearch 时要注意什么?】面试题,希望对大家有帮助; 对于 GC 方面,在使用 Elasticsearch 时要注意什么? 1、SEE 2、倒排词典的索引需…

vue3使用pnpm运行项目但是运行不起来

运行项目的时候发现根本运行不起来了 尝试过创建.npmr文件 删除node_modules重新下 但是都出现问题了 创建.npmr:不管用 删除node_modules重新下:文字编译乱码,utf-8可能解析处理问题 最后解决方法: 重新创建项目&#xff0…

网络科技公司官网电商软件开发小程序网站pbootcms模板带手机端

免费授权可商用网站模板 PC端移动端后台测试数据 所有页面均都能完全自定义标题/关键词/描述,PHP程序,安全、稳定、快速,响应式同一个后台,数据即时同步,简单适用,附带测试数据!!

物流仓库安全视频智能管理方案:构建全方位、高效能的防护体系

一、背景分析 随着物流行业的快速发展和仓储需求的日益增长,仓库安全成为企业运营中不可忽视的重要环节。传统的人工监控方式不仅效率低下,且难以做到全天候、无死角覆盖,给仓库资产和人员安全带来潜在风险。因此,引入仓库安全视…

了解细胞外基质:它是啥?有啥作用?

了解细胞外基质:它是啥?有啥作用? 大家好,今天我们来阅读这篇Biofabrication methods for reconstructing extracellular matrix mimetics发表于《Bioactive Materials》上的文章。细胞外基质在人体中起着至关重要的作用&#xff…

同城门户同城分类信息网站源码discuz插件+pc端+小程序端+49款插件

同城分类信息 同城好店 同城合伙人 同城招聘 同城卡 同城活动 同城优惠抢购 同城商城 同城头条 同城抽奖 同城拼团 同城砍价 同城电话本 同城认证 同城签到 同城拼车 同城红包 同城子站点 同城相亲 同城交友 同城小程序 比较流行的同城信息门户网站源码,基于dz&…