0101基础概念-图-数据结构和算法(Java)
文章目录
- 1 图
- 1.1 定义
- 1.2 4种图模型
- 2 无向图
- 2.1 定义
- 2.2 术语
- 后记
1 图
1.1 定义
图是一种非线性的数据结构,表示多对多的关系。
图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V, E),其中,G表示一个图,V是图G中顶点的集合,E是图G中边的集合。
在图中需要注意的是:
-
线性表和树可以看做特殊的图。
-
线性表中我们把数据元素叫元素,树中将数据元素叫结点,在图中数据元素,我们则称之为顶点(Vertex)。
-
线性表可以没有元素,称为空表;树中可以没有节点,称为空树;但是,在图中不允许没有顶点(有穷非空性)
-
线性表中的各元素是线性关系,树中的各元素是层次关系,而图中各顶点的关系是用边来表示(边集可以为空)。
1.2 4种图模型
- 无向图
- 有向图
- 加权图
- 加权有向图
2 无向图
2.1 定义
图是由一组顶点和一组能够将两个顶点相连的边组成。
图下图2.1-1所示:
顶点一般使用0至V-1来表示一张含有V个顶点的图中的各个顶点,使用数组索引作为结点很方便。我们使用v-w或者w-v表示连接v和w的边。
特殊的图:
- 自环:一条连接一个顶点和其自身的边
- 连接同一对顶点的两条及以上的边称为平行边
含有平行边的图称为多重图;没有平行边或自环的图称为简单图。
2.2 术语
-
相邻顶点:由同一条边连接的两个顶点,称为相邻顶点,并称这条边依附于这2个顶点。
-
度数:某个顶点的度数即为依附于这个顶点的边的总数。
-
子图:有一幅图所以边的一个子集(以及他们所依附的所有顶点)组成的图。
-
路径:由边顺序连接的一系列顶点。
- 简单路径:一条没有重复顶点的路径。
-
环:一条至少含有一条边且起点和终点相同的路径。
- 简单环:一条(除起点和终点必须相同外)不含有重复顶点和边的环。
- u-v-w-x-u记法表示从u到v到w在回到u到一条环。
-
路径长度或者环的长度:路径或者边所 包含的边数。
-
连通:当两个顶点之间存在一条连接双方的路径时,我们称一个顶点和另外一个顶点连通。
- u-v-w-x记法表示u到x的一条路径
-
连通图:如果从任意一顶点都存在一条路径到达另一个任意顶点,我们称这幅图是连通图。
- 一幅非连通图由若干连通的部分组成,它们都是其极大连通子图(分量)。
-
连通图的生成树:连通图的生成树是它的一幅子图,它含有图中的所有顶点且是一颗树。
- 树是一幅无环连通图。互不相连的树组成的集合称为森林。
-
图的生成树森林:图的所有连通子图上生成树的集合。
一棵树如下图所示:
生成树森林:
当且仅当一幅含有V个结点的图G满足下列5个条件之一时,它就是一棵树:
-
G有V-1条边且不含有环;
-
G有V-1条边且时连通的;
-
G是连通的,但删除任意一条边都会使它不在连通;
-
G是无环图,但添加任意一条边都会产生一条环;
-
G中任意一堆顶点之间仅存在一条简单路径。
-
图密度:图密度是指已连接的顶点对占所有可能连接顶点对的比例。
- 稀疏图:如果一幅图中不同边的数量在顶点总数V的一个小的常数倍以内,那么我们就称这幅图是稀疏的。
- 稠密图:否则就是稠密图。
-
二分图:二分图是一种能够将所有结点分为两部分的图,其中图的每条边所连接的两个顶点分别属于不同的部分。
后记
如果小伙伴什么问题或者指教,欢迎交流。
❓QQ:806797785
⭐️源代码仓库地址:https://gitee.com/gaogzhen/algorithm
参考链接:
[1][美]Robert Sedgewich,[美]Kevin Wayne著;谢路云译.算法:第4版[M].北京:人民邮电出版社,2012.10
[2]数据结构:图的基本概念
相关文章:

0101基础概念-图-数据结构和算法(Java)
文章目录1 图1.1 定义1.2 4种图模型2 无向图2.1 定义2.2 术语后记1 图 1.1 定义 图是一种非线性的数据结构,表示多对多的关系。 图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V, E)…...

Linux基础命令和工具使用详解
Linux基础命令和工具使用详解一、grep搜索字符二、find查找文件三、ls 显示文件四、wc命令计算字数五、uptime机器启动时间负载六、ulimit用户资源七、curl http八、scp远程拷贝九、dos2unix和unix2dos十、sed 行处理10.1、简单模式10.2、替换模式十一、awk 列处理11.1、打印某…...

一个好的python文件可以有几种用途?
大家好鸭!我是小熊猫~ 这次来带大家浅浅回顾一点python小知识~ 源码资料电子书:点击此处跳转文末名片获取 python文件总共有两种用途: 一种是执行文件另一种是被当做模块导入 编写好的一个python文件可以有两种用途: 1. 脚本,…...

HDFS优化
单节点多块磁盘数据均衡 生成HDFS块均衡计划 hdfs diskbalancer -plan node1 执行均衡计划,node1.plan.json均衡计划文件 hdfs diskbalancer -execute node1.plan.json 查看当前均衡任务的执行情况 hdfs diskbalancer -query node1 取消均衡任务hdfs diskbalancer -cancel nod…...

行测-判断推理-图形推理-样式规律-黑白运算
黑白元素个数不同,优先考虑黑白运算白白白黑黑白黑白黑选A考试时,这种题不要先把规律全部推出来,再去做题,太慢了直接看要推的图,通过排除法选答案黑白元素个数不同,优先考虑黑白运算白白白黑黑白黑白黑选B…...

java+springboot+vue高校学生医疗保险管理系统
医保管理系统是对与职工健康息息相关的档案进行的系统化、自动化的管理,主要是对职工办理的医疗保险的管理,本系统能够很好的适应社会的需求,最大化的为城镇职工提供服务。医疗保险是国家社会保障体系的重要组成部分,也是社会保险…...
[已解决] AHK 映射 ESC 延迟 500 ms 的严重问题
问题描述 今天发现一个重大bug,我竟然用了一年多都不知道! CapsLock::Esc 我的 ahk 脚本将 capslock 映射为 esc,但这在vim环境中,估算响应 500ms。 也就说按下 caps 键,还要等一会,才进入normal模式 如果…...
QML state详解
1.state简介 changes(list<Change>):保存当前State下的多个Change对象,比如PropertyChanges、StateChangeScript、ParentChange等。 extend(string):表示该状态要在哪个State的基础上进行扩展,当一个…...

一起Talk Android吧(第五百零六回:如何调整组件在约束布局中的角度)
文章目录背景介绍相关属性使用方法示例程序各位看官们大家好,上一回中咱们说的例子是"如何调整组件在约束布局中的大小",这一回中咱们说的例子是"如何调整组件在约束布局中的角度"。闲话休提,言归正转, 让我们一起Talk A…...

微信投票-课后程序(JAVA基础案例教程-黑马程序员编著-第七章-课后作业)
【实验7-5】 微信投票 【任务介绍】 1.任务描述 如今微信聊天已经普及到几乎每一个人,在聊天中,经常会有人需要帮忙在某个APP中投票。本案例要求编写一个模拟微信投票的程序,通过在控制台输入指令,实现添加候选人、查看当前投票…...

duboo+zookeeper分布式架构入门
分布式 dubbo Zookeeper 分布式系统就是若干独立计算机的集合(并且这些计算机之间相互有关联,就像是一台计算机中的C盘F盘等),这些计算对于用户来说就是一个独立的系统。 zookeeper安装 下载地址:Index of /dist/z…...

黑盒测试用例设计方法-等价类划分法
目录 一、等价类的作用 二、等价类的分类 三、等价类的方法 四、等价类的原则 五、按照测试用例的完整性划分等价类 六、等价类步骤 七、案例 一、等价类的作用 为穷举测试设计测试点。 穷举:列出所有的可能情况,对其一一判断。 测试点&#x…...

4.OCR文本识别Connectionist Temporal Classification(CTC)算法
文章目录1.基础介绍2.Connectionist Temporal Classification(CTC)算法2.1 什么是Temporal Classification2.2 CTC问题描述2.2关于对齐2.3 前向后向算法2.4 推理时3.pytorch中的CTCLOSS参考资料欢迎访问个人网络日志🌹🌹知行空间🌹dz…...
误删了Ubuntu/Linux的一些默认用户目录怎么办?
用户目录:指位于 $HOME 下的一系列常用目录,例如 Documents,Downloads,Music,还有 Desktop等。本文不是讲如何恢复原有目录及其重要文件,适用于仅恢复目录功能一:仅恢复个别目录如误删了Desktop…...

ArXiv简介以及论文提交
arXiv网站简介 arXiv是一个收集物理学、数学、计算机科学、生物学与数理经济学的论文预印本的网站。其中arXiv发音同“archive”,因为“X”代表希腊字母 ,国际音标为[kai]。它于1991年8月14日成立,现由美国康奈尔大学维护。 ——维基百科 对…...
pytorch学习
目录如下: pytorch常用操作 pytorch 常用操作 pytorch 的 detach()函数 1. 什么是detach()函数 我们在将输出特征矩阵进行存储的时候,经常需要将torch.Tensor类型的数据转换成别的如numpy类型的数据,但是Tensor类型的数据是会自动计算梯度…...

【OC】块初识
Block简介 Blocks是C语言的扩充功能。可以用一句话来表示Blocks的扩充功能:带有自动变量的匿名函数。 匿名函数 所谓匿名函数就是不带有名称的函数。C语言的标准不允许存在这样的函数。例: int func(int count);它声明了名称为func的函数。下面的源代…...

3-2 创建一个至少有两个PV组成的大小为20G的名为testvg的VG
文章目录1. 在vmware添加多块20G的硬盘,并创建分区2. 创建一个至少有两个PV组成的大小为20G的名为testvg的VG,要求PE大小为16M,而后在卷组中创建大小为5G的逻辑卷testlv;挂载至/users目录3. 新建用户archlinux,要求其家目录为/users/archlinu…...

【密码学】 一篇文章讲透数字证书
【密码学】 一篇文章讲透数字证书 数字证书介绍 数字证书是一种用于认证网络通信中参与者身份和加密通信的证书,人们可以在网上用它来识别对方的身份。 我们在上一篇博客中介绍了数字签名的作用和原理,数字签名可以防止消息被否认。有了公钥算法和数字签…...

Linux 操作系统原理 — 内存管理 — 虚拟地址空间(x86 64bit 系统)
目录 文章目录目录虚拟地址格式与内核页表(四级页表)虚拟地址格式与内核页表(四级页表) 在 x86 64bit 系统中,可以描述的最长地址空间为 2^64(16EB),远远超过了目前主流内存卡的规格…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
spring:实例工厂方法获取bean
spring处理使用静态工厂方法获取bean实例,也可以通过实例工厂方法获取bean实例。 实例工厂方法步骤如下: 定义实例工厂类(Java代码),定义实例工厂(xml),定义调用实例工厂ÿ…...

苍穹外卖--缓存菜品
1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得,如果用户端访问量比较大,数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据,减少数据库查询操作。 缓存逻辑分析: ①每个分类下的菜品保持一份缓存数据…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...

免费数学几何作图web平台
光锐软件免费数学工具,maths,数学制图,数学作图,几何作图,几何,AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

PHP 8.5 即将发布:管道操作符、强力调试
前不久,PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5!作为 PHP 语言的又一次重要迭代,PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是,借助强大的本地开发环境 ServBay&am…...
微服务通信安全:深入解析mTLS的原理与实践
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言:微服务时代的通信安全挑战 随着云原生和微服务架构的普及,服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...