数据结构 - 图

今天我们开始学习目前学习到的最难最复杂的数据结构图。

在这里插入图片描述

简单回顾一下之前学习的数据结构,数组、单链表、队列等线性表中数据元素是一对一关系,而树结构中数据元素是一对多关系,而图结构中数据元素则是多对多关系,任何两个数据元素之间都有可能有关系,由此可见图结构的复杂程度。

希望通过这篇文章可以让大家很轻松的了解和学习图结构并快速入门,把一些晦涩难懂概念通过合理的组织归类使其简单明了,再配合一些图例说明,希望可以使大家茅塞顿开。

01基础概念

1、定义

是一个二元组G=(V(G),E(G))。其中V(G)是非空集,称为点集,对于V中的每个元素,我们称其为顶点或节点,简称;E(G)为V(G)各节点之间边的集合,称为边集

常用G=(V,E)表示图。

2、组成部分

上面的定义可能较为抽象,我们也可以从另一个角度来理解图,即图的内部结构,图由哪些要素组成的——。简单来说图就是由若干个点以及连接两点的边构成的图形,而上面的定义也只是在说所有的点和所有的边组成图,这样是不是就很容易理解了。

在这里插入图片描述

其中点可以代表某种事物,而边可表示两个事物之间的关系,这样我们就可以把一些实际问题转为图,然后使用软件解决问题。

3、分类

我们可以根据边是否有方向,是否带权,简单的将图分类为无向图、有向图、带权图,当然还有其他类型的图,现阶段我们就不过多介绍了,容易把自己搞晕。

(1)无向图

无向图顾名思义就是边没有方向,即两个点之间没有方向,没有顺序之分,这样的边叫作无向边,也简称。其中点也叫作端点

在这里插入图片描述

(2)有向图

有向图则指边有方向,也就代表边所连接的两点有顺序之分,其中一个为起点,则另一个则为终点,而这样的边就叫作有向边。起点和终点也叫端点

其中同一个点既可以是起点,也可以是终点。

在这里插入图片描述

对于任何图,与一个点关联的所有边数称为该点的。而对于有向图来说,以一个点为起点的边数称为该的点出度,以一个点为终点的边数称为该点的入度

如上图点A的出度为3,入度1。

(3)带权图

带权图指每个边都带有一个权重,代表边连接的两点关系的强弱、远近。同时权只是代表边的权重,并不代表边的方向,因此无论无边图还是有边图都可以是带权图。

在这里插入图片描述

02存储方式

了解了图的基本知识以后,带来了一个新的问题,这么复杂的结构我们要怎么存储下来呢?

下面我们就来介绍几种常用的存储方式邻接矩阵、邻接表、逆邻接表、十字链表。

1、邻接矩阵

邻接矩阵就是用一个二维数组来存储任意两点之间的关系,其中行列索引表示点,而行列索引所在的位置的值表示两点关系,其中两点关系可以用以下数值表示:

(1)0:表示两点之间没有边;

(2)1:表示两点之间有边;

(3)权值:表示两点之间边的权值;

如果图存在n个点,则可以用n x n的二维数组来表示图,下面我们来看看常见图的表示方式。

(1)无向图

对于无向图,如果点A与点B有边,则[A,B]与[B,A]都为1,否则都为0,因此无向图的邻接矩阵是对称的,如下图:

在这里插入图片描述

(2)有向图

对于有向图,则可以通过把行索引当作边的起点,把列当作边的终点,来表示方向,比如[A,B]为1,而[B,A]为0,如下图:

在这里插入图片描述

对于有向图,我们可以发现关于点的度有以下特性:

点的出度就是第i行元素之和;

点的入度就是第i列元素之和;

点的就是第i行元素之和 + 第i列元素之和;

(3)带权图

对于带权图,本质上和无向图与有向图相同,只是存储的值有所差别,如果两点之间有边则直接存权值,如果两点之间无边则存一个特殊值(如0、无穷),如果可以保证权值中不存在0,可以用0,否则要选一个其他特殊值,如下图:

在这里插入图片描述

总结

优点

(1)简单直观:实现简单,易于理解,尤其适合小型图。

(2)快速查找:便于判断两点之间是否有边,以及各点的度。

缺点

(1)空间浪费:空间复杂度高为O(n^2),对于稀疏图,许多元素为零,造成空间浪费。

(2)不易扩展:不便于插入和删除点,需要更新整个矩阵,时间复杂度高为O(n)。

2、邻接表

对于邻接矩阵空间浪费以及不易扩展的问题,发展出了另一种链式存储方式——「邻接表」。

邻接表的存储思想和前面章节介绍的散列的链式存储很像。首先我们用一个数组存储所有的点,而每个点元素又作为单链表头,其后继节点则存储与头节点相邻的点元素。

(1)无向图

如下图,图中所有点都存储在数组中,而与其相邻的点存储在其后面的链表中。

点A相邻的点为点B和点C;

点C相邻的点为点A、点D和点E;

点D相邻的点为点C;

在这里插入图片描述

(2)有向图

与无向图不同的是有向图链表中存储的不是所有相邻的点,而是存储有方向的点,即以数组中的点为起的终点元素。

点A为起点的终点为点B和点C;

点B为起点的终点为点E;

点D为起点的终点不存在;

在这里插入图片描述

通过上图可以发现,邻接表对于有向图可以很直观的表示出某个点的出度,但是对于入度获取就很麻烦。

(3)带权图

带权图与无向图和有向图相比,只需要在元素中多加一个权重属性即可。

总结

优点

(1)节省空间:时间复杂度相对较低为O(m+n),m为点数量,n为边数量,对于稀疏图存储效率更高;

(2)操作灵活:插入和删除点操作方便,时间复杂度为O(1);

(3)出度易取:对于有向图获取某个点的出度非常方便,只需要找到这个点所在的数组元素位置,然后获取其链表中的元素个数即可;

缺点

(1)不便查找:判断两点之间是否有边的时间复杂度为O(V), 其中V 是该点的相邻点数量;

(2)入度难算:对于有向图点的入度的计算难度较大,时间复杂度为 O(E),其中E是图中的边的数量;

3、逆邻接表

逆邻接表从名字上就可以看出来和邻接表是逆的关系,这个逆就体现在入度和出度上。我们知道邻接表计算出度容易,计算入度难,而逆邻接表恰恰相反是计算入度容易,计算出度难。

如下图数组中存储点元素,而链表中存储的是以数组中的点为终点的起点元素。

点A为终点的起点不存在;

点B为终点的起点为点A;

点D为终点的起点为点A和点E;

在这里插入图片描述

总结

与邻接表差异在于在存储的方向正好相反,所以入度和出度计算难度正好相反,而其他则完全一样。

4、十字链表

邻接表出度计算容易,逆邻接表入度计算容易,那么有没有一种结构同时计算出度入度都容易呢?答案就是十字链表。

十字链表是邻接表和逆邻接表的结合体,每个点的边通过双向链表存储,同时记录了边的出度和入度。

下面我们详细讲解一下十字链表是怎么得到的。

(1)合并逆邻接表与邻接表

如下图我们之间把逆邻接表和邻接表拼接到一起,得到一个伪十字链表。

在这里插入图片描述

之所以称这个结合体为伪十字链表,是因为它虽然同时存储了边的两个方向,解决了出度入度计算问题,但是也引发了新的问题——存储效率低。

从上图不难看出链表中存在严重的重复存储的问题。要解决这个问题,我们先梳理一下我们得到的伪十字链表结构。

(2)链表由存点改存边

首先数组存储所有点,左侧链表存储起点元素集合,右侧链表存储终点元素集合;然后我们想为什么需要两条链表呢?因为一条链表就代表一个方向;

那第一步我们是否可以先解决方向的问题呢?而目前的结构节点只有一个点的信息,显然没有方向性,因此我们需要把链表节点改造成包含两个点的结构即起点和终点,这也意味着链表由原来存储点元素变为存储边元素。

原来点A出度链表存储点B和点C,现在改为存储[A->B]边和[A->C]边。

原来点B入度链表存储点A,现在改为存储[A->B]边。

如下图:

在这里插入图片描述

(3)删除重复元素

到这里就有条件解决重复的元素的问题了,比如上面链表中有两个[A->B]边,如果我们想把点B入度链表中[A->B]边删除,那么我们必须要有一个途径使得点B的入度链表可以和点A的出度链表中[A->B]边链接上。

首先数组元素结构应该至少包含:数据域|入边头节点指针|出边头节点指针;

然后链表节点元素结构应该至少包含:边起点下标|边终点下标|下一个入边节点指针域|下一个出边节点指针域;

下面我们进行去除重复元素,首先表里下出度链表结构,移除现有入度链表,其中入度链表中的元素指向到出度链表中,最后结果如下图:

在这里插入图片描述

如上图红色实线箭头表示出度链表,而彩色虚线箭头表示入度链表。

点A为终点的边不存在,点A为起点的边为 [A->B]边和[A->C]边;

点B为终点的边为[A->B]边(即红色1号虚线),点B为起点的边为 [B->E]边;

点C为终点的边为[A->C]边(即绿色2号虚线)和[E->C]边(即绿色3号虚线),点C为起点的边为[C->D]边;

总结

优点

(1)高效存储,适合复杂的有向图,支持快速遍历;

(2)快速计算出度入度;

缺点

(1)实现复杂,维护难度高;

:测试方法代码以及示例源码都已经上传至代码库,有兴趣的可以看看。https://gitee.com/hugogoos/Planner

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

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

相关文章

java.lang.NoClassDefFoundError: kotlin/jvm/JvmInline

springboot项目&#xff0c;调用接口时&#xff0c;报这个错误&#xff0c;跟踪断点发现数据库也查询到了数据&#xff0c;就是在返回时报错了&#xff0c;后来一看是pom.xml中引入了 <dependency><groupId>com.fasterxml.jackson.module</groupId><artif…

WebAPI编程(第五天,第六天,第七天)

WebAPI编程&#xff08;第五天&#xff0c;第六天&#xff0c;第七天&#xff09; **day05 - Web APIs****1.1. **元素偏移量 offset 系列1.1.1 offset 概述1.1.2 offset 与 style 区别offsetstyle 1.1.3 案例&#xff1a;获取鼠标在盒子内的坐标1.1.4 案例&#xff1a;模态框拖…

xshell连接不上linux的原因

1、首先我们确定好linux的配置&#xff0c;右键选择设置&#xff0c;将网络适配器设置成NAT模式 2、点击linux编辑&#xff0c;选择虚拟网络 打开以后选中自己要配置的服务 3、进入以后选中自己的服务&#xff0c;确保是NAT模式&#xff0c;然后配置好子网ip&#xff08;尽量ip…

进程与线程+多线程优势

区别&#xff1a; 1、进程中包含线程&#xff0c;每一个进程都至少一个线程&#xff08;主线程&#xff09; 2、进程是申请系统资源的最小单位 3、进程是CPU调度的最小单位 4、线程之间共享进程申请的系统资源 5、一个线程崩溃了会影响整个进程 进程的组织方式&#xff1…

Unity3D学习FPS游戏(8)装弹和弹夹UI显示

前言&#xff1a;实现了武器的基本发射功能&#xff0c;但是我们弹夹数量是有限&#xff0c;之前并没有做装弹和弹夹显示的功能。本篇实现装弹和弹夹显示。 装弹和弹夹UI显示 装弹目标思路和实现 弹夹UI显示目标弹夹UI的思路和实现UI代码的思路和实现 武器控制的完整代码效果补…

计算机网络——网络层导论

转发是局部功能——数据平面 路由是全局的功能——控制平面 网卡 网卡&#xff0c;也称为网络适配器&#xff0c;是计算机硬件中的一种设备&#xff0c;主要负责在计算机和网络之间进行数据传输。 一、主要功能 1、数据传输&#xff1a; 发送数据时&#xff0c;网卡将计算机…

6款IntelliJ IDEA插件,让Spring和Java开发如虎添翼

文章目录 1、SonarLint2、JRebel for IntelliJ3、SwaggerHub插件4、Lombok插件5、RestfulTool插件6、 Json2Pojo插件7、结论 对于任何Spring Boot开发者来说&#xff0c;两个首要的目标是最大限度地提高工作效率和确保高质量代码。IntelliJ IDEA 是目前最广泛使用的集成开发环境…

【MySQL】深度学习与解析 : 库的操作知识整合

前言&#xff1a;本节内容是MySQL库的操作&#xff0c; 内容较少&#xff0c; 大体内容为创建库、删除库、修改库、库备份操作。 ps:本节内容适合安装了MySQL的友友们进行观看&#xff0c; 实操更有利于记住哦。 目录 创建数据库 查看数据库列表 创建数据库 删除数据库 …

开源 AI 智能名片 2+1 链动模式 S2B2C 商城小程序与私域流量圈层

摘要&#xff1a;本文探讨了私域流量圈层的特点以及其在当今时代的重要性&#xff0c;分析了开源 AI 智能名片 21 链动模式 S2B2C 商城小程序源码在私域流量圈层构建中的作用&#xff0c;阐述了产品在圈层时代被标签化的现象&#xff0c;并以实例展示了如何利用该小程序源码打造…

第11章 LAMP架构企业实战

Linux下LAMP(Linux+Apache+MySQL/MariaDB+Perl/PHP/Python)是一组用来搭建动态网站的开源软件架构,本身是各自独立的软件服务,放在一起使用,拥有了越来越高的兼容度,共同组成了一个强大的Web应用程序平台。 本章介绍互联网主流企业架构LAMP应用案例、PHP解释性语言详解、…

vscode php Launch built-in server and debug, PHP内置服务xdebug调试,自定义启动参数配置使用示例

在vscode中&#xff0c;当我们安装了插件 PHP Debug&#xff08;xdebug.php-debug&#xff09;或者 xdebug.php-pack 后 我们通过内置默认的 php xdebug配置启动php项目后&#xff0c;默认情况下我们在vscode中设置断点是不会生效的&#xff0c;因为我们的内置php服务默认启动时…

揭秘云计算 | 2、业务需求推动IT发展

揭秘云计算 | 1、云从哪里来&#xff1f;-CSDN博客https://blog.csdn.net/Ultipa/article/details/143430941?spm1001.2014.3001.5502 书接上文&#xff1a; 过去几十年间IT行业从大型主机过渡到客户端/服务器&#xff0c;再过渡到现如今的万物互联&#xff0c;IT可把控的资…

Golang | Leetcode Golang题解之第538题把二叉搜索树转换为累加树

题目&#xff1a; 题解&#xff1a; func getSuccessor(node *TreeNode) *TreeNode {succ : node.Rightfor succ.Left ! nil && succ.Left ! node {succ succ.Left}return succ }func convertBST(root *TreeNode) *TreeNode {sum : 0node : rootfor node ! nil {if n…

达梦数据守护集群_动态增加实时备库

目录 1、概述 2、实验环境 2.1环境信息 2.2配置信息 2.3 查看初始化参数 3、动态增加实时备库 3.1数据准备 3.2配置新备库 3.3动态增加MAL配置 3.4 关闭守护进程及监视器 3.5修改归档&#xff08;方法1&#xff1a;动态添加归档配置&#xff09; 3.6 修改归档&…

思维导图工具有哪些?10款思维导图特色介绍

电脑的普及&#xff0c;互联网的便捷。使我们平时工作、学习等场景下&#xff0c;常常离不开思维导图的辅助。思维导图是可以让我们所需要介绍的知识点以图文形式结合&#xff0c;展示出来。帮助我们方便理解。因此&#xff0c;一款好的思维导图工具&#xff0c;能让我们制作的…

7.2 设计模式

设计模式 7.3.1 设计模式的要素7.3.2 创建型设计模式7.3.3 结构性设计模式1. Adapter (适配器)2. Bridge(桥接)3.Composite(组合)4.Decorator(装饰)5.Facade(外观)6.Flyweight(享元)7.Proxy(代理)8. 结构型模式比较 7.3.4 行为型设计模式1 Chain of Responsibility 责任链模式2…

【Wi-Fi】802.11ac wave1 vs 802.11ac wave2

参考链接 difference between 11ac wave1 and wave2 | 11ac-wave1 vs 11ac-wave2 什么是802.11ac和802.11ac Wave2 - 华为 Notes&#xff5c;802.11ac Wave1与Wave2 - 知乎 802.11ac-wave1 2013年&#xff0c;IEEE发布了802.11ac标准&#xff0c;在Wave2出来之后&#xf…

【浪潮商城-注册安全分析报告-无验证方式导致安全隐患】

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 1. 暴力破解密码&#xff0c;造成用户信息泄露 2. 短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉 3. 带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造…

【MWorks】Ubuntu 系统搭建

升级 Ubuntu系统 sudo apt-get update sudo apt-get upgrade安装流程 sudo chmod x 路径/文件.run安装 sudo 路径/文件.run安装过程中两个选项都填 y 打开安装对应的文件夹 运行 syslab.sh 文件&#xff0c;运行结束后&#xff0c;就可以在左上角开始搜索到syslab了。

单测篇 - 如何mock静态常量

本文对应源码地址&#xff1a; https://github.com/nieandsun/NRSC-STUDY/tree/master/nrsc-unit-test-study 1 如何mock静态常量 先看如下代码&#xff0c;这里如何对方法中的静态常量DEMO_CONSTANT进行mock呢&#xff1f; public class Demo1StaticConstant {/**** 这里的类…