图论基本术语

图论算法 —— 图论概述-CSDN博客

理论基础 —— 图_依附于顶点v是什么意思-CSDN博客

理论基础 —— 图 —— 图的存储结构_十字链表和链式前向星-CSDN博客

语雀版本

概括:图是计算机中常用的一种存储结构,图论是数学的一个分支,他以图为研究对象,不同情形具有不同的算法。

1 图

图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G=(V,E),其中 V 是非空有限集合, 代表顶点,E 是可以为空的有限集合,代表边。

若顶点 vi 和 vj 间的边没有方向,则称这条边为无向边,用无序偶对 (vi,vj) 表示;若顶点 vi 和 vj 间的边有方向,则称这条边为有向边(弧),用有序偶对 <vi,vj> 表示,其中 vi 称为弧尾,vj 称为弧头

若图的任意两个顶点之间的边都是无向边,则称该图为无向图;若图的任意两个顶点之间的边都是有向边,则称该图为有向图。

2 基本术语

**简单图:** 不存在顶点到其自身的边,且同一条边不重复出现

**互为邻接点:**无向图中的(vi,vj),vi和vj互为邻接点

邻接于点vj、邻接自vi、弧<vi,vj>:有向图中的弧<vi,vj>

**无向完全图:**无向图中,任意两个顶点都有边。数量为$ {n\times(n-1)}/2 $

**有向完全图:**有向图中,任意2个顶点都存在方向相反的两条弧。数量为$ {n\times(n-1)} $

**稠密图:**边数接近完全图

**稀疏图:**边数远远少于完全图

**顶点v的度TD(v):**无向图中,依附于顶点v的边数。对于n个顶点m条边的无向图,所有点的度为2m

顶点v的入度ID(v):有向图中,弧头为v的弧数量。对于n个顶点m条弧的有向图,所有点的入度为m

顶点v的入度OD(v):有向图中,弧尾为v的弧数量。对于n个顶点m条弧的有向图,所有点的出度为m

**权:**边的数值。

**网:**带权的图。

**无向图中的路径:**从一个顶点$ v_p 到另一个顶点 到另一个顶点 到另一个顶点 v_q KaTeX parse error: Expected '}', got 'EOF' at end of input: 的一个顶点序列 ({ {v_p = v_{i_0}, v_{i_1}, v_{i_2}, …, v_{i_m} = v_q} KaTeX parse error: Expected 'EOF', got '}' at position 1: }̲),这个序列代表依次经过的顶点… v_{ij-1} 和 和 v_{ij} $之间都有一条边 $ (v_{ij-1}, v_{ij}) \in E $。也就是说,序列中的每对相邻顶点之间都有一条无向边连接。

**有向图中的路径:**路径是带方向的。

**回路(环):**起点和终点相同的路径

**简单路径:**顶点不重复出现的路径

**简单回路:**除了起点终点,其他顶点不重复的回路

**路径长度:**非带权图的路径边数,带权图的加权路径边数

子图:对于图 G=(V,E) 和 G’=(V’,E’),如果,则后者为前者的子图

**连通:**如果顶点vi到vj有路径,则两个顶点连通

**连通图:**无向图中的任意两个顶点连通

连通分量:非连通图的极大连通子图极大是指包括所有连通的顶点及这些顶点相关联的所有边

**强连通图:**有向图中,任意两个顶点式相互连通的

**强连通分量:**极大强连通子图

生成树:对于连通图G,包含了G中所有顶点的一个极小连通子图极小指的是子图只有一个顶点入度为0,其余入度为1。

**生成森林:**对于一个非连通图,他由多个连通分量组成,连通分量的生成树构成了该图的生成森林。

3 存储结构

**图的存储常见的有:**邻接矩阵、邻接表、前向星、链式前向星。此外还有不太常见的十字链表和邻接多重表。

邻接矩阵

**对于一个有n个顶点的图,可以用nxn的二维矩阵G来存储边或弧。**

无向图:G[i][j]=1表示点vi和vj互为邻接点。否则为0。

有向图:G[i][j]表示弧的权重。对于不邻接的2个点,用无穷大表示,即2个点的距离无穷大。如下:

   A  B  C
A  0  3  ∞
B  3  0  5
C  ∞  5  0

优点:查找某条边时,时间复杂度为O(1)。

缺点:空间复杂度高,为O(n^2)。

适用:稠密图。查找某条边的频率高的任务。

邻接表

**用链表来存储图。**
  • 顶点列表:每个顶点都有一个链表或动态数组来存储与它相邻的顶点。
  • 边列表:每条边都作为一个顶点的邻接表项存储起来,并且可以包含附加信息(如权重)。

例子:

A 和 B 的边权重是 2
A 和 C 的边权重是 3
B 和 D 的边权重是 1
C 和 D 的边权重是 4A -> (B, 2) -> (C, 3)
B -> (A, 2) -> (D, 1)
C -> (A, 3) -> (D, 4)
D -> (B, 1) -> (C, 4)

优点:空间节省,为O(n)。遍历某个点的所有出边的效率高。可以处理有重边的图

缺点:查询某条边的效率低。需要变量顶点的所有邻居。对于稠密图,优点不明显。

适用:稀疏图。遍历频繁的任务。

前向星

前面2种的中庸结构。n个数组,每个元素都是一个动态数组,记录每个顶点的出边的邻接点。
int n,m;
vector<int> edge[N];
void init(){cin>>n>>m;for(int i=0;i<m;i++){int x,y;cin>>x>>y;//边所依附的两点编号edge[x].push_back(y);//添边x->yedge[y].push_back(x);//添边y->x}
}

**优点:**资源占用比邻接矩阵低。查询效率比 邻接表高。可以处理有重边的图

**缺点:**效率低于邻接矩阵。

**适用:**都可用,能处理处理重边。更适用于稀疏图,因为稠密图用邻接矩阵最方便,且前向星此时对空间的优化不明显。

链式前向星

优化前向星的效率低问题。但增加了操作复杂度,且不好处理重边。

链式前向星通过三个数组来存储图的边,分别是:

  1. **head**** 数组**:记录每个顶点的第一条边的索引。
  2. **to**** 数组**:记录每条边的终点。
  3. **next**** 数组**:记录当前边的下一条边在 to 数组中的位置(链表的指针)。

具体来说:

  • head[u]:表示顶点 u 的第一条边的编号。
  • to[i]:表示编号为 i 的边指向的终点顶点。
  • next[i]:表示编号为 i 的边的下一条边在链表中的位置。

例子:

4个顶点5条边1 -> 2
1 -> 3
2 -> 3
2 -> 4
3 -> 4head[1] = 2
head[2] = 4
head[3] = 5
head[4] = -1  (表示顶点 4 没有出边)to[1] = 21 -> 2)
to[2] = 31 -> 3)
to[3] = 32 -> 3)
to[4] = 42 -> 4)
to[5] = 43 -> 4)next[1] = -1  (表示没有下一条边)
next[2] = 11 -> 21 -> 3 的下一条边)
next[3] = -1  (没有下一条边)
next[4] = 32 -> 32 -> 4 的下一条边)
next[5] = -1  (没有下一条边)遍历顶点1:
顶点 1 的第一条边是 head[1] 指向的边 to[2],表示 1 -> 3;
接着通过 next[2] 找到下一条边 to[1],表示 1 -> 2

优点:空间复杂度为O(m),即边数。遍历高效。

缺点:不适合稠密图 ,因为此时没有什么空间复杂度优势。反而增加了操作复杂度。

适用:稀疏图。高遍历任务。

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

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

相关文章

ffmpeg内存模型

文章目录 展示图拷贝packet 重要&#xff01;&#xff01;&#xff01;avpacket.c相关函数av_packet_alloc 简单的赋值 里面的还有没有进行初始化的指针av_packet_ref 展示图 拷贝packet 拷贝packet有两种情况 1&#xff1a; 两个packet的buf引用的是同一个数据缓冲空间&#…

NCC前端调用查询弹框

系统自带的查询模板 弹框 调启使用默认的 查询模板 是在 单据模板的 列表模板中&#xff0c;有个查询区域 &#xff0c;查询区域就是查询模板内容如果在列表页做客开 新增按钮 调启查询模板 无问题&#xff0c;但是目前需求是需要再卡片页面下调启系统标准的调启模板代码 //调…

Python用CEEMDAN-LSTM-VMD金融股价数据预测及SVR、AR、HAR对比可视化

全文链接&#xff1a;https://tecdat.cn/?p38224 分析师&#xff1a;Duqiao Han 股票市场是一个复杂的非线性系统&#xff0c;股价受到许多经济和社会因素的影响。因此&#xff0c;传统的线性或近线性预测模型很难有效、准确地预测股票指数的价格趋势。众所周知&#xff0c;深…

企业如何提高团队管理的能力?

企业如何提高团队管理的能力&#xff1f; 在当前竞争日益激烈的市场环境中&#xff0c;企业的成功不再仅仅依赖于个体的卓越能力&#xff0c;而是越来越多地依赖于团队的整体效能。一个高效、协作、富有创新精神的团队&#xff0c;能够激发员工的潜能&#xff0c;推动企业不断…

场景解决之mybatis当中resultType= map时,因某个字段为null导致返回的map的key不存在怎么处理

1、场景:通过查询数据表将返回结果封装到map当中返回,因某个字段为null,导致map当中key丢失 <select id"queryMyBonus" parameterType"com.cn.entity.student" resultType "map">SELECTb.projectName as "projectName",b.money…

客户案例 | 如何利用Ansys工具提供互联系统(以及系统的系统),从而使“软件定义汽车”成为可能

“我使用Ansys medini进行大量的分析类活动&#xff0c;因此&#xff0c;从危险分析和风险评估开始&#xff0c;我们就使用medini来开展工作。此外&#xff0c;我们也会在产品开发阶段使用该工具……比如当我们试图确定哪些类型的故障&#xff0c;以及哪些类型的条件会导致不必…

Stored procedures in PostgreSQL

select 存储过程&#xff0c;在现了解的情况&#xff0c;还是没有mysql,sqlserver等好写好用。 --postgreSQL 11.0 以下版本 create or replace FUNCTION procInsertSchool (pSchoolId Char(5),pSchoolName VarChar(100),pSchoolTelNo VarChar(8) ) RETURNS void language plp…

搭建监控系统Prometheus + Grafana

公司有个技术分享会&#xff0c;但是业务忙&#xff0c;没时间精心准备&#xff0c;所以就匆匆忙忙准备分享一下搭建&#xff08;捂脸哭&#xff09;。技术含量确实不多&#xff0c;但是分享的知识确实没问题。 以下是搭建过程&#xff1a; 一、讲解 Prometheus Prometheus 最…

字节跳动核心技术:TT推荐系统从0-1落地应用

⭕️以下就是字节跳动TT推荐系统0-1落地应用简单的描述&#xff0c;同时我还整理了其他不同大厂的项目案例拆解以及其他的AI产品项目&#xff0c;都已经脱敏了 ✅在这之前&#x1f236;一位90后产品女生用我分享的项目去面试&#xff0c;上周就已经拿下了一家大厂的offer&…

欧国联的规则,你都了解吗?

昨天威科姆主场2-1击败克劳利&#xff0c;客观来讲&#xff0c;威科姆的确也缺少很重要的球员&#xff0c;因此尽管罚丢了一个点球&#xff0c;但场面优势并不明显。好在有惊无险拿到3分晋级&#xff0c;避开了点球大战。 今天没有比赛&#xff0c;聊聊明天要猜的欧国联相关话…

Mysql 8迁移到达梦DM8遇到的报错

在实战迁移时&#xff0c;遇到两个报错。 一、列[tag]长度超出定义 在mysql中&#xff0c;tag字段的长度是varchar(20)&#xff0c;在迁移到DM8后&#xff0c;这个长度不够用了。怎么解决&#xff1f; 在迁移过程中&#xff0c;“指定对象”时&#xff0c;选择转换。 在“列映…

Ai创作新风标!仅需三步,利用ai工具免费制作抖音爆款的动物融合视频(含完整的步骤)

有位家人想要学习动物融合的视频,群里有人口述分享但是家人还是有点不是很明白。所以本篇就手把手把这个制作教程分享出来。 整体制作流程相对还是比较简单的,难度在于如何写提示词让画面按照预期的方式进行合并,这个就和昨天的烟火秀一样。后面我思考一下如何把这种调整提示词…

常见的噪声模型+图像中噪声模型的估计+常见的滤波方法(C++)

常见空间域噪声模型 1.1 高斯噪声 高斯噪声的概率密度函数表示为&#xff1a; 1.2 瑞利噪声 1.3 伽马噪声 1.4 指数噪声 1.5 均匀分布噪声 1.6 脉冲&#xff08;椒盐&#xff09;噪声 图像中噪声判别 对于上述六种噪声&#xff0c;椒盐噪声与其他噪声图像差别较大&#xf…

RAFT: Recurrent All-Pairs Field Transforms for Optical Flow用于光流估计的循环全对场变换

背景&#xff1a; 1.光流估计是一个长期存在的计算机视觉问题&#xff0c;对于理解视频内容至关重要。 2.光流估计面临的挑战包括快速移动的物体、遮挡、运动模糊和无纹理表面。 3.传统方法通常将光流估计视为一个手工优化问题&#xff0c;但这些方法在处理各种特殊情况时存…

大数据面试题--kafka夺命连环问(后10问)

目录 16、kafka是如何做到高效读写&#xff1f; 17、Kafka集群中数据的存储是按照什么方式存储的&#xff1f; 18、kafka中是如何快速定位到一个offset的。 19、简述kafka中的数据清理策略。 20、消费者组和分区数之间的关系是怎样的&#xff1f; 21、kafka如何知道哪个消…

【Android、IOS、Flutter、鸿蒙、ReactNative 】约束布局

Android XML 约束布局 参考 TextView居中 TextView 垂直居中并且靠右 TextView 宽高设置百分比 宽和高的比例 app:layout_constraintDimensionRatio"h,2:1" 表示子视图的宽高比为2:1&#xff0c;其中 h表示保持宽度不变&#xff0c;高度自动调整。 最大宽度 设…

【机器学习】平均绝对误差(MAE:Mean Absolute Error)

平均绝对误差 (Mean Absolute Error, MAE) 是一种衡量预测值与实际值之间平均差异的统计指标。它在机器学习、统计学等领域中广泛应用&#xff0c;用于评估模型的预测精度。与均方误差 (MSE) 或均方误差根 (RMSE) 不同&#xff0c;MAE 使用误差的绝对值&#xff0c;因此它在处理…

【Qt】在 Qt Creator 中使用图片资源方法(含素材网站推荐)

先准备图片资源 推荐一个好用的图标素材网站&#xff0c;有很多免费资源。 Ic, fluent, animal, dog, filled icon - Free download 其他辅助工具&#xff0c;类似 AI 抠图去背景&#xff0c;实测效果还行&#xff0c;但是非免费。 美图秀秀-在线一键抠图&#xff0c;无需P…

Dial-insight:利用高质量特定领域数据微调大型语言模型防止灾难性遗忘

摘要 大型语言模型&#xff08;LLM&#xff09;的性能很大程度上依赖于底层数据的质量&#xff0c;特别是在专业领域。在针对特定领域应用微调LLM时&#xff0c;一个常见的挑战是模型泛化能力的潜在下降。为了解决这些问题&#xff0c;我们提出了一种两阶段方法来构建提示词&a…

品融电商:新形势下电商平台如何助力品牌长期经营

品融电商&#xff1a;新形势下电商平台如何助力品牌长期经营 在过去几年中&#xff0c;随着内容电商的兴起&#xff0c;一批新兴品牌通过精准的内容种草和互动营销迅速打开市场&#xff0c;实现了从“0到1”的品牌起步阶段。比如&#xff0c;新品牌SIINSIIN通过小红书等内容电商…