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

数据结构--5.1图的存储结构(十字链表、邻接多重表、边集数组)

目录

一、十字链表(Orthogonal List)

二、邻接多重表

三、边集数组

四、深度优先遍历


 

一、十字链表(Orthogonal List)

重新定义顶点表结点结构: 

datafirstInfirstOut

重新定义边表结构结点:

tailVexheadVexheadLinktailLink

       十字链表的好处就是因为把邻接表和逆邻接表整合在了一起,这样既容易找到Vi为尾的弧,也容易找到以Vi为头的弧,因而容易求得顶点的出度和入度。

        十字链表除了结构复杂一点外,其实创建图算法的时间复杂度是和邻接表相同的,因此,在有向图的应用中,十字链表也是非常好的数据结构模型。

二、邻接多重表

        我们可以仿照十字链表的方式,对边表结构进行改装,重新定义的边表结构如下:

iVexiLinkjVexjLink

        其中iVex和jVex是与某条边依附的两个顶点在顶点表中的下标。iLink指向依附顶点iVex的下一条边,jLink指向依附顶点jVex的下一条边。

        也就是说在邻接多重表里边,边表存放的是一条边,而不是一个顶点。 

三、边集数组

        边集数组是由两个一维数组构成的,一个是存储顶点的信息,另一个是存储边的信息,这个边数组每个数据元素由一条边的起点下标(begin),终点下标(end)和权(weight)组成。

四、深度优先遍历

        深度优先遍历(DepthFirstSearch),也有称为深度优先搜索,简称为DFS。

相关文章:

数据结构--5.1图的存储结构(十字链表、邻接多重表、边集数组)

目录 一、十字链表(Orthogonal List) 二、邻接多重表 三、边集数组 四、深度优先遍历 一、十字链表(Orthogonal List) 重新定义顶点表结点结构: datafirstInfirstOut 重新定义边表结构结点: tailV…...

mac上 Kratos 配置 protoc

前言 protoc 是 protobuf 文件(.proto)的编译器,可以借助这个工具把 .proto 文件转译成各种编程语言对应的源码,包含数据类型定义、调用接口等。 protoc 在设计上把 protobuf 和不同的语言解耦了,底层用 c 来实现 protobuf 结构的存储&#x…...

【c++5道练习题】①

目录 一、有限制的累加 二、计算日期到天数转换 三、仅仅反转字母 四、 字符串的第一个唯一字符 五、字符串最后一个单词的长度 一、有限制的累加 题述: 求123...n,要求不能使用乘除法、for、while、if、else、switch、case等关键字以及条件判断语句…...

最佳实践:TiDB 业务读变慢分析处理

作者:李文杰 网易游戏计费 TiDB 负责人 在使用或运维管理 TiDB 的过程中,大家几乎都遇到过 SQL 变慢的问题,尤其是查询相关的读变慢问题。读变慢的问题大部分情况下都遵循一定的规律,通过经验的积累可以快速的定位和优化&#xff…...

【ES6】Getter和Setter

JavaScript中的getter和setter方法可以用于访问和修改对象的属性。这些方法可以通过使用对象字面量或Object.defineProperty()方法来定义。 以下是使用getter和setter方法的示例&#xff1a; <!DOCTYPE html> <script>const cart {_wheels: 4,get wheels(){retu…...

3DS Max中绘制圆锥箭头

3DS Max中绘制圆锥箭头 绘制结果绘制过程步骤一&#xff1a;绘制立体圆锥方法1方法2 步骤二&#xff1a;圆锥体调参&#xff08;模型尺寸设置&#xff09;1圆锥体参数说明2圆锥体参数调整 步骤三&#xff1a;绘制圆柱体步骤四&#xff1a;圆柱体调参步骤五&#xff1a;圆锥与圆…...

虚拟机Ubuntu20.04 网络连接器图标开机不显示怎么办

执行以下指令&#xff1a; sudo service network-manager stop sudo rm /var/lib/NetworkManager/NetworkManager.state sudo service network-manager start...

你真的知道什么是USB Server吗?一分钟了解

很多公司都在用USB Server&#xff0c;效率大幅提高&#xff0c;但也还有不少人不知道USB Server到底是什么、干嘛用的。 USB Serve是帮助企业远程连接和集中管控USB设备的服务器 它的主要用途就是异地远程连接USB。 如&#xff0c;虚拟化环境的加密狗、前置机连接&#xff0…...

Node.js 中间件是怎样工作的?

express自带路由功能&#xff0c;可以侦听指定路径的请求&#xff0c;除此之外&#xff0c;express最大的优点就是【中间件】概念的灵活运用&#xff0c;使得各个模块得以解耦&#xff0c;像搭积木一样串起来就可以实现复杂的后端逻辑。除此之外&#xff0c;还可以利用别人写好…...

Spring MVC: 请求参数的获取

Spring MVC 前言通过 RequestParam 注解获取请求参数RequestParam用法 通过 ServletAPI 获取请求参数通过实体类对象获取请求参数附 前言 在 Spring MVC 介绍中&#xff0c;谈到前端控制器 DispatcherServlet 接收客户端请求&#xff0c;依据处理器映射 HandlerMapping 配置调…...

别再头疼反弹Shell失败了,这篇文章带你找到问题根源

别再头疼反弹Shell失败了&#xff0c;这篇文章带你找到问题根源 在渗透测试中&#xff0c;反弹shell失败的原因可以有多种。以下是一些常见的原因&#xff1a; **1.防火墙和网络过滤器&#xff1a;**目标系统可能配置了防火墙或网络过滤器&#xff0c;以限制对外部系统的连接…...

第五章 树与二叉树 四、线索树(手算与代码实现)

一、定义 1.线索树是一种二叉树&#xff0c;它在每个节点上增加了两个指针&#xff0c;分别指向其前驱和后继。 2.这些指针称为“线索”&#xff0c;因此线索树也叫做“线索化二叉树”。 3.在线索树中&#xff0c;所有的叶子节点都被线索化&#xff0c;使得遍历树的过程可以…...

服务器前后端学习理解

个人兴趣&#xff0c;突然想起来记录一下 1. 背景 想做一个最简单的网页&#xff0c;点击按钮后&#xff0c;访问服务器的redis数据库&#xff0c;读取一个为hello的值并显示 首先用js写了一个脚本&#xff0c;使用redis包&#xff0c;读取到了数据&#xff0c;并使用consol.l…...

python-数据分析-numpy、pandas、matplotlib的常用方法

一、numpy import numpy as np1.numpy 数组 和 list 的区别 输出方式不同 里面包含的元素类型 2.构造并访问二维数组 使用 索引/切片 访问ndarray元素 切片 左闭右开 np.array(list) 3.快捷构造高维数组 np.arange() np.random.randn() - - - 服从标准正态分布- - - …...

ChatGPT⼊门到精通(5):ChatGPT 和Claude区别

⼀、Claude介绍 Claude是Anthropic开发的⼀款⼈⼯智能助⼿。 官⽅⽹站&#xff1a; ⼆、Claude能做什么 它可以通过⾃然语⾔与您进⾏交互,理解您的问题并作出回复。Claude的主要功能包括: 1、问答功能 Claude可以解答⼴泛的常识问题与知识问题。⽆论是历史上的某个事件,理科…...

ChatGPT 总结数据分析的所有知识点

ChatGPT功能非常多,特别是对某个行业,某个方向,某个技术进行总结那是相当专业的。 如下图。 直接用一个指令便总结出来数据分析当中的所有知识点内容。 AIGC ChatGPT ,BI商业智能, 可视化Tableau, PowerBI, FineReport, 数据库Mysql Oracle, Office, Python ,ETL Ex…...

hadoop-HDFS

1.HDFS简介 2.1 Hadoop分布式文件系统-HDFS架构 2.2 HDFS组成角色及其功能 &#xff08;1&#xff09;Client&#xff1a;客户端 &#xff08;2&#xff09;NameNode (NN)&#xff1a;元数据节点 管理文件系统的Namespace元数据 一个HDFS集群只有一个Active的NN &#xff…...

0202hdfs的shell操作-hadoop-大数据学习

文章目录 1 进程启停管理2 文件系统操作命令2.1 HDFS文件系统基本信息2.2 介绍2.3 创建文件夹2.4 查看指定文件夹下的内容2.5 上传文件到HDFS2.6 查看HDFS文件内容2.7 下载HDFS文件2.8 HDFS数据删除操作 3 HDFS客户端-jetbrians产品插件3.1 Big Data Tools 安装3.2 配置windows…...

生活小记-挂号信

"挂号信"通常指的是在邮寄过程中通过挂号邮寄服务寄送的信件&#xff0c;相对于普通信件有一些特殊的特点和服务。以下是挂号信与其他信件&#xff08;例如普通信件&#xff09;之间的区别&#xff1a; 跟踪和确认&#xff1a; 挂号信&#xff1a;通过挂号邮寄服务寄…...

3D点云处理:基于PCA的计算点云位姿(占位待整理)

文章目录 文章目录&#xff1a;3D视觉个人学习目录微信&#xff1a;dhlddxB站: Non-Stop_...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

【SQL学习笔记1】增删改查+多表连接全解析(内附SQL免费在线练习工具)

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...

Docker拉取MySQL后数据库连接失败的解决方案

在使用Docker部署MySQL时&#xff0c;拉取并启动容器后&#xff0c;有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致&#xff0c;包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因&#xff0c;并提供解决方案。 一、确认MySQL容器的运行状态 …...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...