数据结构秘籍(二)图(含图的概念、存储以及图的两大搜索)
1 引言
线性数据结构的元素满足唯一的线性关系,每个元素(初第一个和最后一个外)只有一个直接前趋和一个直接后继。树形数据结构的元素之间有着明显的层次关系。但是图形结构的元素之间的关系是任意的。
什么是图?
简单来说,图就是由顶点的有穷非空集合和顶点之间的边组成的集合。通常表示为:G(V,E),其中,G表示一个图,V表示顶点的集合,E表示边的集合。

上图所展示的就是图,而且是一个有向图(带箭头)
2 图的基本概念
拿好友关系举例
2.1 顶点
图中的数据元素我们称之为顶点,图中至少有一个顶点(非空有穷集合)
对应到好友关系图,每一个用户就代表一个顶点。
2.2 边
顶点之间的关系用边表示。
对应到好友关系图,两个用户是好友的话,那两者之间就存在一条边。
2.3 度
度表示一个顶点包含多少条边,在有向图中,还分为出度和入度,出度表示从该顶点出去的边的条数,入度表示进入该顶点的边的条数。
对应到好友关系图,度就代表了某个人的好友数量。
2.4 无向图和有向图
边表示的是顶点之间的关系,有的关系是双向的,比如同学,A是B的同学,那么B也肯定是A的同学,那么在表示A和B的关系时,就不用关注方向,用不带箭头的边表示,这样的图就是无向图。
有的关系是有方向的,比如抖音,我关注了你,你没有关注我,这样我们之间的关系就是单向的,我们用箭头表示二者之间的关系,这样的图就是有向图。
2.5 无权图和带权图
对于一个关系,如果我们只关心关系的有无,而不关心关系有多强,那么就可以用无权图来表示二者的关系。
对于一个关系,如果我们既关心关系的有无,也关心关系的强度,比如某某某的好感度,你对人家好感度百分百,人家对你好感度百分之零(一个悲伤的故事),那么就可以用带权图来表示,带权图中每一条边用一个数值表示权值,代表关系的强度。

把上面的有向图进行加工就是一个带权有向图
3 图的存储
3.1 邻接矩阵存储
邻接矩阵将图用二维矩阵存储,是一种较为直观的表示方式。
如果第i个顶点和第j个顶点之间有关系,且关系权值为n,则A[i][j]=n。
在无向图中,我们只关心关系的有无,所以当顶点i和顶点j有关系时,A[i][j]=1,当顶点i和顶点j没有关系时,A[i][j]=0。如下图所示。

值得注意的是:无向图的邻接矩阵是一个对称矩阵,因为在无向图中,顶点i和顶点j有关系,那么就必定是双方的。

邻接矩阵存储的方式优点是简单直接(直接用一个二维数组即可),并且,在获取两个顶点之间的关系时也非常高效(直接获取指定位置的数组元素的值即可)。但是吧,这种存储方式的缺点也很明显,那就是比较浪费空间。
3.2 邻接表存储
针对上面邻接矩阵比较浪费内存空间的问题,诞生出了另外一种存储方法--邻接表。
邻接链表使用一个链表来存储某个顶点的所有后继相邻顶点。对于图中每个顶点Vi,把所有邻接于Vi的顶点Vj链成一个单链表,这个单链表称为顶点Vi的邻接表。如下图所示:


可以数一数邻接表中所存储的元素的个数以及图中边的条数:
在无向图中,邻接表元素个数等于边的条数的两倍,如左图所示的无向图中,边的条数为7,邻接表存储的元素个数为14。
在有向图中,邻接表元素个数等于边的条数,边的条数为8,那么邻接表存储的元素个数就为8.
4 图的搜索
4.1 广度优先搜索
广度优先搜索是一层一层向外扩展的

广度优先搜索的具体实现方式用到了之前学过的线性数据结构--队列。具体过程如下所示






4.2 深度优先搜索
深度优先搜索就是从原顶点开始,一直走到没有后继节点,才回溯到上一顶点,然后继续往下走。

注意:搜索顺序是不唯一的,如果给出了链表或矩阵的存储方式,如下就是用单链表存储,那么搜索顺序就是固定的。
深度优先搜索的具体实现用到了另一种线性数据结构--栈。(队列和栈可以从我线性数据结构一文中了解数据结构秘籍(一)线性数据结构(数组、链表、栈、队列一次看完)-CSDN博客)过程如下:





相关文章:
数据结构秘籍(二)图(含图的概念、存储以及图的两大搜索)
1 引言 线性数据结构的元素满足唯一的线性关系,每个元素(初第一个和最后一个外)只有一个直接前趋和一个直接后继。树形数据结构的元素之间有着明显的层次关系。但是图形结构的元素之间的关系是任意的。 什么是图? 简单来说&…...
前端八股——JS+ES6
前端八股:JSES6 说明:个人总结,用于个人复习回顾,将持续改正创作,已在语雀公开,欢迎评论改正。...
Python 课堂点名桌面小程序
一、场景分析 闲来无事,老婆说叫我开发一个课堂点名桌面小程序,给她在课堂随机点名学生问问题。 人生苦短,那就用 Python 给她写一个吧。 二、依赖安装 因为要用到 excel,所以安装两个依赖: pip install openpyxl…...
【Java基础】Java中new一个对象时,JVM到底做了什么?
Java中new一个对象时,JVM到底做了什么? 在Java编程中,new关键字是我们创建对象的最常用方式。但你是否想过,当你写下new MyClass()时,Java虚拟机(JVM)到底在背后做了哪些工作?今天&…...
C#中的字典怎么使用?
在C#中,Dictionary<TKey, TValue> 是一个泛型集合类,用于存储键值对(key-value pairs)。它提供了快速的查找、插入和删除操作,适合需要根据键快速查找值的场景。以下是 Dictionary 的基本用法和常见操作…...
vue框架后遗症∶被遗忘的dom操作
用多了vue、react等前端框架,不得不说用数据驱动视图来开发真的很香,但是也免不了会有不用这些框架的项目,dom操作还是很有必要的,一开始学习网页设计的时候就教过,后面一直开发项目基本上用框架。虽然有些想不起来了&…...
进程 ─── linux第10课
目录 回顾上一节 进程 基本概念 描述进程 - PCB task_struct - PCB的一种 task_ struct内容分类 组织进程 下面来介绍task_struct内部 PID 和PPID 子进程与父进程 getpid()和getppid() 杀进程 exe 和 cwd 回顾上一节 1. 如果我们写的程序要访问硬件,必定通过sy…...
线性模型 - 支持向量机
支持向量机(SVM)是一种用于分类(和回归)的监督学习算法,其主要目标是找到一个最佳决策超平面,将数据点分为不同的类别,并且使得分类边界与最近的数据点之间的间隔(margin)…...
MyBatis-Plus注解配置:@TableName、@TableId、@TableField
MyBatis-Plus 是 MyBatis 的增强工具,在 MyBatis 的基础上只做增强不做改变,为简化开发、提高效率而生。MyBatis-Plus 提供了一系列注解,用于简化数据库表与实体类之间的映射关系。以下是 @TableName、@TableId 和 @TableField 这三个常用注解的配置和使用说明。 官方文档:…...
DeepSeek接入问题-Xshell5连接Ubuntu22失败解决方案
项目场景: deepseek部署常用系统Ubuntu系统, xshell5连接Ubuntu22遇到如下问题: 问题描述 xshell5连接Ubuntu22遇到如下问题: Connecting to 172.16.46.80:22... Could not connect to 172.16.46.80 (port 22): Connection fa…...
论文阅读之基于Syn2Real域的侧扫声纳类水雷目标探测
摘要 由于现实世界数据的稀缺性,基于深度学习的水下水雷探测受到了限制。这种稀缺性导致过拟合,即模型在训练数据上表现良好,但在未见数据上表现不佳。本文提出了一种使用扩散模型的Syn2Real (Synthetic to Real)域泛…...
【Java】Tomcat日志
Tomcat日志 tomcat 日志的配置文件是tomcat目录下的/conf/logging.properties。 日志输出级别:SEVERE (最高级别) > WARNING > INFO > CONFIG > FINE > FINER(精心) > FINEST (所有内容,最低级别) 日志分类 tomcat 有五类日志 : …...
datalist 是什么?
一、datalist 是什么? datalist 是 HTML5 引入的一个表单相关元素,它本质上是一个为输入框(<input>)提供预定义选项列表的容器。从外观上看,当用户在与之关联的输入框中进行输入操作时,会自动弹出一个…...
初阶数据结构(C语言实现)——3顺序表和链表(3)
3.链表 3.1 链表的概念及结构 概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 链表的物理结构 1.从上图可看出,链式结构在逻辑上是连续的,但是在物理上不一定连续…...
Docker 数据卷管理及优化
Docker 数据卷是一个可供容器使用的特殊目录,它绕过了容器的文件系统,直接将数据存储在宿主机上。通过数据卷,可以实现数据的持久化、共享以及独立于容器生命周期的管理。 1.1 为什么要用数据卷 Docker 分层文件系统的特点 性能差ÿ…...
Hi3516CV610车牌识别算法源码之——车牌识别算法初体验
本文讲述如何使用Hi3516CV610开发板读取本地图片,运行车牌识别算法推理,得到车牌信息并打印; 下一篇将介绍Hi3516CV610开发板如何从sensor摄像头获取图像,运行车牌识别算法推理,得到车牌信息并打印; 一、准…...
使用内置命令查看笔记本电池健康状态
如何使用powercfg /batteryreport命令查看笔记本电池健康状态 在Windows系统中,了解笔记本电池的健康状态对于维护电脑性能和预测电池寿命至关重要。Windows 10和Windows 11系统提供了一个内置命令powercfg /batteryreport,可以生成一份详细的电池使用情…...
HONOR荣耀MagicBook 15 2021款 独显(BOD-WXX9,BDR-WFH9HN)原厂Win10系统
适用型号:【BOD-WXX9】 MagicBook 15 2021款 i7 独显 MX450 16GB512GB (BDR-WFE9HN) MagicBook 15 2021款 i5 独显 MX450 16GB512GB (BDR-WFH9HN) MagicBook 15 2021款 i5 集显 16GB512GB (BDR-WFH9HN) 链接:https://pan.baidu.com/s/1S6L57ADS18fnJZ1…...
transformer架构的语言模型保存的内容与格式详解
前文我们已经详细讲述了基于pytorch框架下的transformer架构如何从零开始构建一个小型字符级语言模型,构建过程中涵盖数据准备、模型架构设计、训练、评估与生成的整个流程。我们已经了解了各个部分的细节,而且已经提供了完整的python代码。现在需要了解我们构建好的模型如何…...
win本地vscode通过代理远程链接linux服务器
时间:2025.2.28 1. win本地下载nmap.exe nmap官网 https://nmap.org/或者 https://nmap.org/download#windows下载win版本并安装。 2. vscode插件Remote-SSH 插件下载Remote-SSH 3. 配置 按照图中顺序配置ssh 1.点击左侧工具栏的“小电视”图标 2.点击ssh的…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
系统设计 --- MongoDB亿级数据查询优化策略
系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log,共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题,不能使用ELK只能使用…...
现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
#Uniapp篇:chrome调试unapp适配
chrome调试设备----使用Android模拟机开发调试移动端页面 Chrome://inspect/#devices MuMu模拟器Edge浏览器:Android原生APP嵌入的H5页面元素定位 chrome://inspect/#devices uniapp单位适配 根路径下 postcss.config.js 需要装这些插件 “postcss”: “^8.5.…...
Ubuntu系统复制(U盘-电脑硬盘)
所需环境 电脑自带硬盘:1块 (1T) U盘1:Ubuntu系统引导盘(用于“U盘2”复制到“电脑自带硬盘”) U盘2:Ubuntu系统盘(1T,用于被复制) !!!建议“电脑…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
C++_哈希表
本篇文章是对C学习的哈希表部分的学习分享 相信一定会对你有所帮助~ 那咱们废话不多说,直接开始吧! 一、基础概念 1. 哈希核心思想: 哈希函数的作用:通过此函数建立一个Key与存储位置之间的映射关系。理想目标:实现…...
数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)
名人说:莫道桑榆晚,为霞尚满天。——刘禹锡(刘梦得,诗豪) 原创笔记:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 上一篇:《数据结构第4章 数组和广义表》…...
Axure零基础跟我学:展开与收回
亲爱的小伙伴,如有帮助请订阅专栏!跟着老师每课一练,系统学习Axure交互设计课程! Axure产品经理精品视频课https://edu.csdn.net/course/detail/40420 课程主题:Axure菜单展开与收回 课程视频:...
