当前位置: 首页 > news >正文

数据结构--5.0.1图的存储结构

目录

一、邻接矩阵(无向图)

 二、邻接矩阵(有向图)

三、邻接矩阵(网)

四、邻接表(无向图)

五、邻接表(有向图)


 

——图的存储结构相比较线性表与树来说就复杂很多

——对于线性表来说,是一对一的关系,所以用数组或者链表均可简单存放。

        树结构是一对多的关系,所以我们要将数组和链表的特性结合在一起才能更好的存放。

——我们的图,是多对多的情况,另外图上的任何一个顶点都可以被看作第一个顶点,任一顶点的邻接点之间不存在次序关系。

——因为任意两个顶点之间都可能存在联系,因此无法以数据元素在内存中的物理位置来表示元素之间的关系(内存物理位置是线性的,图的元素关系是平面的)

一、邻接矩阵(无向图)

        考虑到图是由顶点和边或弧两部分组成,合在一起比较困难,那就是很自然地考虑到分为两个结构来分别存储。

        顶点因为不区分大小、主次,所以用一个一维数组来存储是很不错地选择。

        而边或弧由于是顶点与顶点之间的关系,一维数组肯定就搞不定了,那我们不妨考虑用一个二维数组来存储。

1、图的邻接矩阵(Adjacency Matrix)存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图的边或弧的信息。

        我们可以设置两个数组,顶点数组为vertex[4] = {V0,V1,V2,V3},边数组arc[4][4]为对称矩阵(0表示不存在顶点间的边,1表示顶点间存在边)。

 二、邻接矩阵(有向图)

        可见顶点数组vertex[4]= {V0,V1,V2,V3},弧数组arc[4][4]也是一个矩阵,但因为是有向图,所以这个矩阵并不对称,例如由V1到V0有弧,得到arc[1][0] = 1,而V0到V1没有弧,因此arc[0][1]=0。

        另外有向图也是有讲究的,要考虑入度和出度,顶点V1的入度(横为出,竖为入)为1,正好是第V1列的个数之和,顶点V1的出度为2 ,正好是第V2行的个数之和。

三、邻接矩阵(网)

        在图的术语中,我们提到了网这个概念,事实上也就是每条边上带有权的图就叫网。 

 这里  “∞”   表示一个计算机允许的,大于所有边上权值的值。

四、邻接表(无向图)

        把数组与链表结合一起来存储,这种方式在图结构也适用,我们称为邻接表(AdjacencyList)。

邻接表的处理方法是:

1、图中顶点用一个一维数组存储,当然顶点也可以用单链表来存储,不过数组可以较为容易的读取顶点信息,更加方便。 

2、图中每个顶点Vi的所有邻接点构成一个线性表,由于邻接点的个数不确定,所以我们选择用单链表来存储。

五、邻接表(有向图)

       邻接表结构类似无向图的。

相关文章:

数据结构--5.0.1图的存储结构

目录 一、邻接矩阵(无向图) 二、邻接矩阵(有向图) 三、邻接矩阵(网) 四、邻接表(无向图) 五、邻接表(有向图) ——图的存储结构相比较线性表与树来说就复…...

解决win10 wsl子系统安装的ubuntu环境中lsof,netstat命令查看端口没有任何输出的问题

最近有个以前的ssm项目需要在新电脑上运行测试一下,发现需要redis环境,看了官网说:有两种选择: 1. 要么在虚拟机比如vmware安装linux基础环境,然后再安装redis 2. 要么可以利用win10的wsl linux子系统安装ubuntu&…...

【OpenFeign】OpenFeign结合Hystrix和Sentinel实现熔断降级

OpenFeign可以与Hystrix和Sentinel结合使用&#xff0c;实现降级和熔断。 OpenFeign与Hystrix结合使用 使用OpenFeign需要引入OpenFeign的依赖&#xff1a; <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-sta…...

软件工程(十) 需求工程之需求开发与管理

前面我们学习到了需求工程的概念与分类,我们知道了需求工程主要分为需求开发和需求管理,但是没有说明到底该如何开发需求,有哪些方法去开发需求。到底该如何进行需求管理,又有哪些进行需求管理的方式。具体是如何去做的。下面我们将会详细进行描述。 1、需求开发 1.1、需…...

C++网狐服务器引入开源日志库spdlog

很多人对日志库不以为然&#xff0c;包括网狐这种十几年的公司都不重视&#xff0c;其实日志库记录的东西能在线上出问题时高效解决&#xff0c;特别是别人写的东西&#xff0c;人又走了&#xff0c;出了问题&#xff0c;还可以用日志分析快速解决。要是没有日志记录&#xff0…...

【C++】—— c++11之智能指针

前言&#xff1a; 本期&#xff0c;我们将要学习的是在c11中新提出的概念——异常指针&#xff01; 目录 &#xff08;一&#xff09;智能指针的引入 &#xff08;二&#xff09;内存泄漏 1、什么是内存泄漏&#xff0c;内存泄漏的危害 2、内存泄漏分类&#xff08;了解&a…...

html5——前端笔记

html 一、html51.1、理解html结构1.2、h1 - h6 (标题标签)1.3、p (段落和换行标签)1.4、br 换行标签1.5、文本格式化1.6、div 和 span 标签1.7、img 图像标签1.8、a 超链接标签1.9、table表格标签1.9.1、表格标签1.9.2、表格结构标签1.9.3、合并单元格 1.10、列表1.10.1、ul无序…...

如何在 Vue TypeScript 项目使用 emits 事件

Vue是构建出色的Web应用程序的最灵活、灵活和强大的JavaScript框架之一。Vue中最重要的概念和关键特性之一是能够促进应用程序组件之间的通信。让我们深入探讨一下Vue中的“emits”概念&#xff0c;并了解它们如何以流畅和无缝的方式实现父子组件之间的通信。 Vue中的emits是什…...

文件操作 黑马教程(04)

1.文本文件 写文件 #include "iostream" #include "fstream" using namespace std; /** 文件操作** 程序运行时产生的数据都属于临时数据&#xff0c;程序一旦结束都会被释放* 通过文件可以将数据持久化* C中对文件操作需要包含头文件<fstream>** 文…...

Jmeter(二十七):BeanShell PostProcessor跨线程全局变量使用

在性能测试中&#xff0c;两个相关联的接口不一定都在同一个线程组&#xff0c;遇见这种情况时&#xff0c;我们要进行跨线程组传参&#xff0c;此处用登录和查询配送单两个请求举例&#xff1b; 1、登录请求中配置json提取器&#xff0c;将接口返回的token保存在变量中&#…...

手写表格OCR识别并与大模型ChatGPT交互?

这是一张手写表格&#xff0c;姓名做了脱敏处理。现在需要对其识别&#xff0c;并分析。 直接粘贴剪切板中的表格原始图片&#xff0c;在网页中ctlV进行识别。识别结果列用分隔符|&#xff0c;可以直接粘贴到excel&#xff0c;进行数据列分隔。为了美观期间&#xff0c;也可以用…...

使用 v-for 指令和数组来实现在 Uni-app 中动态增减表单项并渲染多个数据

在 data 中定义一个数组&#xff0c;用于存储表单项的数据&#xff1a; data() {return {formItems: []} } 在模板中使用 v-for 指令渲染表单项&#xff1a; <template><div><div v-for"(item, index) in formItems" :key"index"><…...

xml

1.xml 1.1概述【理解】 万维网联盟(W3C) 万维网联盟(W3C)创建于1994年&#xff0c;又称W3C理事会。1994年10月在麻省理工学院计算机科学实验室成立。 建立者&#xff1a; Tim Berners-Lee (蒂姆伯纳斯李)。 是Web技术领域最具权威和影响力的国际中立性技术标准机构。 到目前为…...

Java中的动态代理(JDK Proxy VS CGLib)

前言 动态代理可以说是Java基础中一个比较重要的内容&#xff0c;这块内容关系到Spring框架中的AOP实现原理&#xff0c;所以特别写了一篇作为个人对这块知识的总结。这部分内容主要包括&#xff1a;JDK Proxy和CGLib的基本介绍、二者的实现原理、代码示例等。 什么是动态代理…...

Redis 7 第七讲 哨兵模式(sentinal)

哨兵模式 哨兵巡查监控后台master主机是否故障,如果出现故障根据投票时自动将某一个从库转换成新的主库,继续对外服务。 作用 1. 监控redis运行状态,包括master和slave 2. 当master down机,能自动将salve切换成新的master 应用场景 主从监控监控主从redis库运行的状态…...

Python入门教程 - 判断语句(二)

目录 一、布尔类型 二、比较运算符 三、if判断语句 一、布尔类型 True False result1 10 > 5 result2 10 < 5 print(result1) print(result2) print(type(result1)) True False <class bool> 二、比较运算符 ! > < > < 比较运算的结果是布尔…...

LeetCode-55-跳跃游戏-贪心

题目描述&#xff1a; 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 解…...

【USRP】调制解调系列4:BPSK、QPSK、8PSK、OQPSK、Pi/4DQPSK,基于labview的实现

PSK Phase Shift Keying – 相移键控 在某些调制解调器中用于数据传输的调制系统&#xff0c;在最简单的方式中&#xff0c;二进制调制信号产生0和1。载波相位来表示信号占和空或者二进制1和O。对于有线线路上较高的数据传输速率&#xff0c;可能发生4个或8个不同的相移&…...

深入探讨梯度下降:优化机器学习的关键步骤(一)

文章目录 &#x1f340;引言&#x1f340;什么是梯度下降&#xff1f;&#x1f340;损失函数&#x1f340;梯度(gradient)&#x1f340;梯度下降的工作原理&#x1f340;梯度下降的变种&#x1f340;随机梯度下降&#xff08;SGD&#xff09;&#x1f340;批量梯度下降&#xf…...

layui框架学习(40:数据表格_主要事件)

Layui数据表格模块主要通过各类事件响应工具栏操作、单元格编辑或点击等交互操作&#xff0c;本文学习table数据表格模块中的主要事件及处理方式。   头部工具栏事件。通过代码“table.on(‘toolbar(test)’, function(obj))”获取lay-filter属性为test的数据表格的头部工具栏…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...