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

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)&#xf…...

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&#xff08;list<Change>&#xff09;&#xff1a;保存当前State下的多个Change对象,比如PropertyChanges、StateChangeScript、ParentChange等。 extend&#xff08;string&#xff09;&#xff1a;表示该状态要在哪个State的基础上进行扩展,当一个…...

一起Talk Android吧(第五百零六回:如何调整组件在约束布局中的角度)

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

微信投票-课后程序(JAVA基础案例教程-黑马程序员编著-第七章-课后作业)

【实验7-5】 微信投票 【任务介绍】 1.任务描述 如今微信聊天已经普及到几乎每一个人&#xff0c;在聊天中&#xff0c;经常会有人需要帮忙在某个APP中投票。本案例要求编写一个模拟微信投票的程序&#xff0c;通过在控制台输入指令&#xff0c;实现添加候选人、查看当前投票…...

duboo+zookeeper分布式架构入门

分布式 dubbo Zookeeper 分布式系统就是若干独立计算机的集合&#xff08;并且这些计算机之间相互有关联&#xff0c;就像是一台计算机中的C盘F盘等&#xff09;&#xff0c;这些计算对于用户来说就是一个独立的系统。 zookeeper安装 下载地址&#xff1a;Index of /dist/z…...

黑盒测试用例设计方法-等价类划分法

目录 一、等价类的作用 二、等价类的分类 三、等价类的方法 四、等价类的原则 五、按照测试用例的完整性划分等价类 六、等价类步骤 七、案例 一、等价类的作用 为穷举测试设计测试点。 穷举&#xff1a;列出所有的可能情况&#xff0c;对其一一判断。 测试点&#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参考资料欢迎访问个人网络日志&#x1f339;&#x1f339;知行空间&#x1f339;&#x1f3…...

误删了Ubuntu/Linux的一些默认用户目录怎么办?

用户目录&#xff1a;指位于 $HOME 下的一系列常用目录&#xff0c;例如 Documents&#xff0c;Downloads&#xff0c;Music&#xff0c;还有 Desktop等。本文不是讲如何恢复原有目录及其重要文件&#xff0c;适用于仅恢复目录功能一&#xff1a;仅恢复个别目录如误删了Desktop…...

ArXiv简介以及论文提交

arXiv网站简介 arXiv是一个收集物理学、数学、计算机科学、生物学与数理经济学的论文预印本的网站。其中arXiv发音同“archive”&#xff0c;因为“X”代表希腊字母 &#xff0c;国际音标为[kai]。它于1991年8月14日成立&#xff0c;现由美国康奈尔大学维护。 ——维基百科 对…...

pytorch学习

目录如下&#xff1a; pytorch常用操作 pytorch 常用操作 pytorch 的 detach()函数 1. 什么是detach()函数 我们在将输出特征矩阵进行存储的时候&#xff0c;经常需要将torch.Tensor类型的数据转换成别的如numpy类型的数据&#xff0c;但是Tensor类型的数据是会自动计算梯度…...

【OC】块初识

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

3-2 创建一个至少有两个PV组成的大小为20G的名为testvg的VG

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

【密码学】 一篇文章讲透数字证书

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

Linux 操作系统原理 — 内存管理 — 虚拟地址空间(x86 64bit 系统)

目录 文章目录目录虚拟地址格式与内核页表&#xff08;四级页表&#xff09;虚拟地址格式与内核页表&#xff08;四级页表&#xff09; 在 x86 64bit 系统中&#xff0c;可以描述的最长地址空间为 2^64&#xff08;16EB&#xff09;&#xff0c;远远超过了目前主流内存卡的规格…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

基于Flask实现的医疗保险欺诈识别监测模型

基于Flask实现的医疗保险欺诈识别监测模型 项目截图 项目简介 社会医疗保险是国家通过立法形式强制实施&#xff0c;由雇主和个人按一定比例缴纳保险费&#xff0c;建立社会医疗保险基金&#xff0c;支付雇员医疗费用的一种医疗保险制度&#xff0c; 它是促进社会文明和进步的…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

渲染学进阶内容——模型

最近在写模组的时候发现渲染器里面离不开模型的定义,在渲染的第二篇文章中简单的讲解了一下关于模型部分的内容,其实不管是方块还是方块实体,都离不开模型的内容 🧱 一、CubeListBuilder 功能解析 CubeListBuilder 是 Minecraft Java 版模型系统的核心构建器,用于动态创…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

3403. 从盒子中找出字典序最大的字符串 I

3403. 从盒子中找出字典序最大的字符串 I 题目链接&#xff1a;3403. 从盒子中找出字典序最大的字符串 I 代码如下&#xff1a; class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...

爬虫基础学习day2

# 爬虫设计领域 工商&#xff1a;企查查、天眼查短视频&#xff1a;抖音、快手、西瓜 ---> 飞瓜电商&#xff1a;京东、淘宝、聚美优品、亚马逊 ---> 分析店铺经营决策标题、排名航空&#xff1a;抓取所有航空公司价格 ---> 去哪儿自媒体&#xff1a;采集自媒体数据进…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...