数据结构-图

1. 感性的认识图

是是数据结构中最复杂的一种。图的概念特别特别的多,相关的算法问题也很多。如果我们一开始就讲复杂的概念,可能很多同学都学不下去,太深奥,太枯燥。我们不妨先感性的认识图。

图看起来就像下图这样:

在计算机科学中,一个图就是一些顶点的集合,这些顶点通过一系列边结对(连接)。顶点用圆圈表示,边就是这些圆圈之间的连线。顶点之间通过边连接。

注意:顶点有时也称为节点或者交点,边有时也称为链接。

一个图可以表示一个社交网络,每一个人就是一个顶点,互相认识的人之间通过边联系。

图有各种形状和大小。边可以有权重(weight),即每一条边会被分配一个正数或者负数值。考虑一个代表航线的图。各个城市就是顶点,航线就是边。那么边的权重可以是飞行时间,或者机票价格。

有了这样一张假设的航线图。从旧金山到莫斯科最便宜的路线是到纽约转机。

边可以是有方向的。在上面提到的例子中,边是没有方向的。例如,如果 Ada 认识 Charles,那么 Charles 也就认识 Ada。相反,有方向的边意味着是单方面的关系。一条从顶点 X 到 顶点 Y 的边是将 X 联向 Y,不是将 Y 联向 X。

继续前面航班的例子,从旧金山到阿拉斯加的朱诺有向边意味着从旧金山到朱诺有航班,但是从朱诺到旧金山没有(这可能意味着你要先从朱诺飞到某个地方,经过中转到达旧金山,又或者你改成开车去旧金山)。

2. 图的定义和基本概念

2.1 图的定义和表示

图是由顶点的有穷非空集合和顶点之间边的集合组成,通过表示为 G(V,E) ,其中,G 表示一个图,V 是图 G 中顶点的集合,E 是图 G 中边的集合。

以上图为例,V={1,2,3,4,5,6}, E = {<1,2>,<1,4>,<2,5>,<4,3>,<5,4>,<6,5>}。

上面的这些表示符号,主要是为了便于理论的陈述和推导。

2.2 无向图和有向图

无边图:若顶点 ViVi​到 VjVj​ 之间的边没有方向,则称这条边为无向边(Edge),用序偶对(ViVi​,VjVj​)标示。下图为无向图的一个例子:

有向图:若从顶点 ViVi​到 VjVj​ 的边是有方向的,则成这条边为有向边,也称为弧(Arc)。用有序对<ViVi​,VjVj​> 标示,ViVi​ 称为弧尾,VjVj​ 称为弧头。如果任意两条边之间都是有向的,则称该图为有向图。下图为一个有向图的例子,顶点 1,2,4 都可以到大顶点 3 ,但是顶点 3 无法到大顶点 1,2,4。

2.3 入度和出度

对于有向图中的一个顶点 V 来说,箭头指向 V 的弧的数量为 V 的入度(InDegree,记为 ID(V));箭头远离 V 的弧的数量为 V 的出度(OutDegree,记为OD(V))。

入度出度信息在欧拉图相关问题中尤其重要。

2.4 路径和回路

无论是无向图还是有向图,从一个顶点到另一顶点途经的所有顶点组成的序列(包含这两个顶点),称为一条路径。如果路径中第一个顶点和最后一个顶点相同,则此路径称为回路(或)。

在此基础上,若路径中各顶点都不重复,此路径被称为简单路径;若回路中的顶点互不重复,此回路被称为简单回路(或简单环)。

2.5 图在程序中的存储和表达

2.5.1 邻接矩阵

邻接矩阵是指用一个二维的数组来记录图中各个顶点之间是否存在边或者弧。如果顶点之间存在边或弧,在相应位置用 1 表示,反之用 0 表示;如果使用二维数组存储网中顶点之间的关系,顶点之间如果有边或者弧的存在,在数组的相应位置存储其权值;反之用 0 表示。

无向图中的边,可以理解为 2 条方向相反的边,所以,无向图邻接矩阵的内容是对称的。 vis[i][j] = vis[j][i] 。

邻接矩阵的优点是:效率高,便于理解,代码简单

邻接矩阵缺点是:占用的内存多。试想一下,如果一张图顶点很多,但是边却很少,那么对应的邻接矩阵中大多数内容都是 0 ,我们称这种情况为稀疏矩阵。如果图中有 105105 个顶点,对应的邻接矩阵数组就有 8*10101010 Byte ,约等于 80000 MB 。你的程序一定爆内存了。

2.5.2 链表法

邻接表可以解决邻接矩阵占用空间的问题。邻接表中,图的每一个顶点都是一个链表的头节点,其后连接着该顶点能够直接达到的相邻顶点。

如果要查询某一个顶点 i 一步能访问的顶点,那只需要便令顶点为 i 的链表即可。

如果要查询有哪些顶点一步能到达顶点 i,这就很尴尬,要访问所有顶点的玲姐表,访问量很大。

2.5.3 逆链表法

为了解决有哪些顶点一步能到达顶点 i的问题,我们可以采用逆邻接表法。逆邻接表,和邻接表是正好相反的。逆邻接表每一个顶点作为链表的头节点,后继节点所存储的是能够直接达到该顶点的相邻顶点。

但是,逆链表法在处理顶点 i 一步能到达哪些顶点问题时,又很尴尬。

2.5.4 十字链表法

既然邻接表和逆邻接表各有各的尴尬,那么,我们就引入了十字链表。十字链表的每一个顶点,都是两个链表的根节点,其中一个链表存储着该顶点能到达的相邻顶点,另一个链表存储着能到达该顶点的相邻节点。

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

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

相关文章

普林斯顿微积分读本PDF(英文版原版)

普林斯顿微积分读本PDF英文版: https://caiyun.139.com/m/i?005Chb93yVHtQ 对于大多数学生来说&#xff0c;微积分或许是他们曾经上过的倍感迷茫且最受挫折的一门课程了. 而《普林斯顿微积分读本》 不仅让学生能有效地学习微积分&#xff0c;更重要的是提供了战胜微积分的必备…

Netty学习——NIO基础与IO模型

导学 Socket和NIO的区别 Socket和NIO是Java中用于网络编程的两个不同的API&#xff0c;具有不同的设计理念和用途。以下是它们的主要区别&#xff1a; 1. 定义 Socket: Socket是Java中用于实现网络通信的传统API&#xff0c;通常被称为Java I/O&#xff08;输入/输出&#…

Cesium基础-(Entity)-(ellipse)

里边包含Vue、React框架代码详细步骤、以及代码详细解释 6、ellipse 圆与椭圆 EllipseGeometry(椭圆几何体)是 Cesium 中用于在三维空间中创建椭圆形状的类。这种椭圆形状可以位于地球表面(或其他椭球体)上,也可以在地球表面上方或下方的一定高度。EllipseGeometry 允许你…

014:无人机遥控器操作

摘要&#xff1a;本文详细介绍了无人机遥控器及其相关操作。首先&#xff0c;解释了油门、升降舵、方向舵和副翼的概念、功能及操作方式&#xff0c;这些是控制无人机飞行姿态的关键部件。其次&#xff0c;介绍了美国手、日本手和中国手三种不同的操作模式&#xff0c;阐述了遥…

Java—— CompletableFuture

CompletableFuture 1、概述1.1、Future接口1.2、CompletionStage接口 2、CompletableFuture结构2.1、字段和常量2.2、内部类 3、CompletableFuture原理3.1、设计思想3.2、获取任务结果的实现不带参数的Get方法实现带超时参数的Get方法实现立即返回结果的GetNow方法实现 3.3、开…

uniapp使用uni.createInnerAudioContext()播放指定音频并且切换

uniapp使用uni.createInnerAudioContext()播放指定音频并且切换 因为做的小程序或者h5需要视频讲解或者音乐组件的 默认展示播放按钮&#xff0c;当点击播放的时候 显示暂停音乐这样的一个效果。 在unipp中我们直接只用uni.createInnerAudioContext()代替audio&#xff0c;使用…

《TCP/IP网络编程》学习笔记 | Chapter 2:套接字类型与协议设置

《TCP/IP网络编程》学习笔记 | Chapter 2&#xff1a;套接字类型与协议设置 《TCP/IP网络编程》学习笔记 | Chapter 2&#xff1a;套接字类型与协议设置套接字协议及其数据传输特性协议&#xff08;Protocol&#xff09;创建套接字协议族&#xff08;Protocol Family&#xff0…

小林渗透入门:burpsuite+proxifier抓取小程序流量

目录 前提&#xff1a; 代理&#xff1a; proxifier&#xff1a; 步骤&#xff1a; bp证书安装 bp设置代理端口&#xff1a; proxifier设置规则&#xff1a; proxifier应用规则&#xff1a; 结果&#xff1a; 前提&#xff1a; 在介绍这两个工具具体实现方法之前&#xff0…

举重场景哑铃图像分割系统:全面改进提升

举重场景哑铃图像分割系统源码&#xff06;数据集分享 [yolov8-seg-GhostHGNetV2&#xff06;yolov8-seg-EfficientHead等50全套改进创新点发刊_一键训练教程_Web前端展示] 1.研究背景与意义 项目参考ILSVRC ImageNet Large Scale Visual Recognition Challenge 项目来源AA…

【机器学习】连续属性离散化与sklearn.preprocessing.KBinsDiscretizer

1. KBinsDiscretizer的定义 KBinsDiscretizer是 scikit-learn 库中的一个类&#xff0c;用于将连续数据离散化成区间&#xff08;bins&#xff09;。这个类通过将特征值分配到 k 个等宽的区间&#xff08;bins&#xff09;来实现离散化&#xff0c;并且可以配置不同的编码方式…

OpenGL入门002——顶点着色器和片段着色器

文章目录 一些概念坐标转换阶段顶点着色器片段着色器VBOVAO 实战简介main.cppCMakeLists.txt最终效果 一些概念 坐标转换阶段 概述&#xff1a; 模型空间、世界空间、视图空间和裁剪空间是对象在3D场景中经历的不同坐标变换阶段。每个空间对应渲染管道的一个步骤&#xff0c;…

使用 Elastic、OpenLLMetry 和 OpenTelemetry 跟踪 LangChain 应用程序

作者&#xff1a;来自 Elastic Bahubali Shetti Langchain 应用程序的使用正在增长。构建基于 RAG 的应用程序、简单的 AI 助手等的能力正在成为常态。观察这些应用程序更加困难。考虑到现有的各种选项&#xff0c;本博客展示了如何将 OpenTelemetry 检测与 OpenLLMetry 结合使…

【Linux】从零开始使用多路转接IO --- select

碌碌无为&#xff0c;则余生太长&#xff1b; 欲有所为&#xff0c;则人生苦短。 --- 中岛敦 《山月记》--- 从零开始认识五种IO模型 1 前言2 认识多路转接select3 多路转接select等待连接4 完善代码5 总结 1 前言 上一篇文章我们讲解了五种IO模型的基本概念&#xff0c;并…

客户端与微服务之间的桥梁---网关

当我们创建好了N多个微服务或者微服务的实例之后&#xff0c;每个服务暴露出不同的端口地址&#xff0c;一般对于客户端请求&#xff0c;只需要请求一个端口&#xff0c;要隔离客户端和微服务的直接关系&#xff0c;保证微服务的安全性和灵活性&#xff0c;避免敏感信息的泄露。…

docker部署nginx+nacos+redis+java镜像和容器

nginx镜像制作 Dockerfile内容&#xff1a; # 基础镜像 FROM nginx # author MAINTAINER ruoyi# 挂载目录 VOLUME /home/ruoyi/projects/ruoyi-ui # 创建目录 RUN mkdir -p /home/ruoyi/projects/ruoyi-ui # 指定路径 WORKDIR /home/ruoyi/projects/ruoyi-ui # 复制conf文件到路…

MiniWord

1.nuget 下载配置 2.引用 3. var value = new Dictionary<string, object>() { ["nianfen"] = nianfen, ["yuefen"] = yuefen, ["yuefenjian1"] = (int.Par…

SpringBoot篇(简化操作的原理)

目录 一、代码位置 二、统一版本管理&#xff08;parent&#xff09; 三、提供 starter简化 Maven 配置 四、自动配置 Spring&#xff08;引导类&#xff09; 五、嵌入式 servlet 容器 一、代码位置 二、统一版本管理&#xff08;parent&#xff09; SpringBoot项目都会继…

Jetson OrinNX平台CSI相机导致cpu load average升高问题调试

1. 前言 硬件: Orin NX JP: 5.1.2, R35.4.1 用v4l2-ctl --stream-mmap -d0 命令去获取相机数据时, 用top查看cpu使用情况, CPU占用率很低,但load average在1左右, 无任何程序运行时,load average 为0 用ps -aux 查看当前进程情况,发现有两个系统进程vi-output, …

Iceoryx2:高性能进程间通信框架(中间件)

文章目录 0. 引言1. 主要改进2. Iceoryx2 的架构3. C示例代码3.1 发布者示例&#xff08;publisher.cpp&#xff09;3.2 订阅者示例&#xff08;subscriber.cpp&#xff09; 4. 机制比较5. 架构比较6. Iceoryx vs Iceoryx2参考资料 0. 引言 Iceoryx2 是一个基于 Rust 实现的开…

获取Hive表备注

DESCRIBE EXTENDED 表名;先获取Detailed Table Information这行的data_type字段数据&#xff0c;进行正则匹配&#xff0c;拿到表备注&#xff0c;如下&#xff1a; String str ReUtil.get("parameters:\\{(?!.*?\\().*transient_lastDdlTime.*?comment(.*?)\\}&quo…