您现在的位置是:首页 > 编程 > 

数据结构的图存储结构

2025-07-28 23:24:04
数据结构的图存储结构 数据结构的图存储结构我们知道,数据之间的关系有 种,分别是 "一对一"、"一对多" 和 "多对多",前两种关系的数据可分别用线性表和树结构存储,本节学习存储具有"多对多"逻辑关系数据的结构——图存储结构。图存储结构示意图 图 1 图存储结构示意图 图 1 所示为存储 V1、V2、V、V4

数据结构的图存储结构

数据结构的图存储结构

我们知道,数据之间的关系有 种,分别是 "一对一"、"一对多" 和 "多对多",前两种关系的数据可分别用线性表和树结构存储,本节学习存储具有"多对多"逻辑关系数据的结构——图存储结构。

图存储结构示意图

图 1 图存储结构示意图

图 1 所示为存储 V1、V2、V、V4 的图结构,从图中可以清楚的看出数据之间具有的"多对多"关系。例如,V1 与 V4 和 V2 建立着联系,V4 与 V1 和 V 建立着联系,以此类推。 与链表不同,图中存储的各个数据元素被称为顶点(而不是节点)。拿图 1 来说,该图中含有 4 个顶点,分别为顶点 V1、V2、V 和 V4。

图存储结构中,习惯上用 Vi 表示图中的顶点,且所有顶点构成的集合通常用 V 表示,如图 1 中顶点的集合为 V={V1,V2,V,V4}。

注意,图 1 中的图仅是图存储结构的其中一种,数据之间 "多对多" 的关系还可能用如图 2 所示的图结构表示:

有向图示意图

图 2 有向图示意图

可以看到,各个顶点之间的关系并不是"双向"的。比如,V4 只与 V1 存在联系(从 V4 可直接到 V1),而与 V 没有直接联系;同样,V 只与 V4 存在联系(从 V 可直接到 V4),而与 V1 没有直接联系,以此类推。 因此,图存储结构可细分两种表现类型,分别为无向图(图 1)和有向图(图 2)。

图存储结构基本常识

弧头和弧尾

有向图中,无箭头一端的顶点通常被称为"初始点"或"弧尾",箭头直线的顶点被称为"终端点"或"弧头"。

入度和出度

对于有向图中的一个顶点 V 来说,箭头指向 V 的弧的数量为 V 的入度(InDegree,记为 ID(V));箭头远离 V 的弧的数量为 V 的出度(OutDegree,记为OD(V))。拿图 2 中的顶点 V1来说,该顶点的入度为 1,出度为 2(该顶点的度为 )。

(V1,V2) 和 <V1,V2> 的区别

无向图中描述两顶点(V1 和 V2)之间的关系可以用 (V1,V2) 来表示,

而有向图中描述从 V1 到 V2 的"单向"关系用 <V1,V2> 来表示。 由于图存储结构中顶点之间的关系是用线来表示的,因此 (V1,V2) 还可以用来表示无向图中连接 V1 和 V2 的线,又称为边;同样,<V1,V2> 也可用来表示有向图中从 V1 到 V2 带方向的线,又称为弧。

集合 VR 的含义

并且,图中习惯用 VR 表示图中所有顶点之间关系的集合。例如,图 1 中无向图的集合 VR={(v1,v2),(v1,v4),(v1,v),(v,v4)},图 2 中有向图的集合 VR={<v1,v2>,<v1,v>,<v,v4>,<v4,v1>}。

路径和回路

无论是无向图还是有向图,从一个顶点到另一顶点途径的所有顶点组成的序列(包含这两个顶点),称为一条路径。如果路径中第一个顶点和最后一个顶点相同,则此路径称为"回路"(或"环")。 并且,若路径中各顶点都不重复,此路径又被称为"简单路径";同样,若回路中的顶点互不重复,此回路被称为"简单回路"(或简单环)。 拿图 1 来说,从 V1 存在一条路径还可以回到 V1,此路径为 {V1,V,V4,V1},这是一个回路(环),而且还是一个简单回路(简单环)。

在有向图中,每条路径或回路都是有方向的。

权和网的含义

在某些实际场景中,图中的每条边(或弧)会赋予一个实数来表示一定的含义,这种与边(或弧)相匹配的实数被称为"权",而带权的图通常称为网。如图 所示,就是一个网结构:

带权的图存储结构

图 带权的图存储结构

子图:指的是由图中一部分顶点和边构成的图,称为原图的子图。

图存储结构的分类

根据不同的特征,图又可分为完全图,连通图、稀疏图和稠密图:

完全图:若图中各个顶点都与除自身外的其他顶点有关系,这样的无向图称为完全图(如图 4a))。同时,满足此条件的有向图则称为有向完全图(图 4b))。

完全图示意图

图 4 完全图示意图

具有 n 个顶点的完全图,图中边的数量为 n(n-1)/2;

对于具有 n 个顶点的有向完全图,图中弧的数量为 n(n-1)。

  • 稀疏图和稠密图:这两种图是相对存在的,即如果图中具有很少的边(或弧),此图就称为"稀疏图";反之,则称此图为"稠密图"。 稀疏和稠密的判断条件是:e<nlogn,其中 e 表示图中边(或弧)的数量,n 表示图中顶点的数量。如果式子成立,则为稀疏图;反之为稠密图。
什么是连通图,(强)连通图详解

前面讲过,图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。例如图 1 中,虽然 V1 和 V 没有直接关联,但从 V1 到 V 存在两条路径,分别是 V1-V2-VV1-V4-V,因此称 V1 和 V 之间是连通的。

顶点之间的连通状态示意图

图 1 顶点之间的连通状态示意图

无向图中,如果任意两个顶点之间都能够连通,则称此无向图为连通图。例如,图 2 中的无向图就是一个连通图,因为此图中任意两顶点之间都是连通的。

连通图示意图

图 2 连通图示意图

若无向图不是连通图,但图中存储某个子图符合连通图的性质,则称该子图为连通分量

前面讲过,由图中部分顶点和边构成的图为该图的一个子图,但这里的子图指的是图中"最大"的连通子图(也称"极大连通子图")。

如图 所示,虽然图 a) 中的无向图不是连通图,但可以将其分解为 个"最大子图"(图 b)),它们都满足连通图的性质,因此都是连通分量。

图 连通分量示意图

提示,图 a) 中的无向图只能分解为 部分各自连通的"最大子图"。

需要注意的是,连通分量的提出是以"整个无向图不是连通图"为前提的,因为如果无向图是连通图,则其无法分解出多个最大连通子图,因为图中所有的顶点之间都是连通的。

强连通图

有向图中,若任意两个顶点 Vi 和 Vj,满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通,也就是都含有至少一条通路,则称此有向图为强连通图。如图 4 所示就是一个强连通图。

强连通图

图 4 强连通图

与此同时,若有向图本身不是强连通图,但其包含的最大连通子图具有强连通图的性质,则称该子图为强连通分量。

强连通分量

图 5 强连通分量

如图 5 所示,整个有向图虽不是强连通图,但其含有两个强连通分量。 可以这样说,连通图是在无向图的基础上对图中顶点之间的连通做了更高的要求,而强连通图是在有向图的基础上对图中顶点的连通做了更高的要求。

什么是生成树,生成树(生成森林)详解

对连通图进行遍历,过程中所经过的边和顶点的组合可看做是一棵普通树,通常称为生成树。

连通图及其对应的生成树

图 1 连通图及其对应的生成树

如图 1 所示,图 1a) 是一张连通图,图 1b) 是其对应的 2 种生成树。

连通图中,由于任意两顶点之间可能含有多条通路,遍历连通图的方式有多种,往往一张连通图可能有多种不同的生成树与之对应。

连通图中的生成树必须满足以下 2 个条件:

  1. 包含连通图中所有的顶点;
  2. 任意两顶点之间有且仅有一条通路;

因此,连通图的生成树具有这样的特征,即生成树中边的数量 = 顶点数 - 1

生成森林

生成树是对应连通图来说

而生成森林是对应非连通图来说的。 我们知道,非连通图可分解为多个连通分量,而每个连通分量又各自对应多个生成树(至少是 1 棵),因此与整个非连通图相对应的,是由多棵生成树组成的生成森林。

非连通图和连通分量

图 2 非连通图和连通分量

如图 2 所示,这是一张非连通图,可分解为 个连通分量,其中各个连通分量对应的生成树如图 所示:

生成森林

图 生成森林

注意,图 中列出的仅是各个连通分量的其中一种生成树。

因此,多个连通分量对应的多棵生成树就构成了整个非连通图的生成森林。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。 原始发表:202-08-16,如有侵权请联系 cloudcommunity@tencent 删除数据存储数据结构遍历集合

#感谢您对电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格的认可,转载请说明来源于"电脑配置推荐网 - 最新i3 i5 i7组装电脑配置单推荐报价格

本文地址:http://www.dnpztj.cn/biancheng/1265374.html

相关标签:无
上传时间: 2025-07-28 16:32:33
留言与评论(共有 15 条评论)
本站网友 延时技巧
29分钟前 发表
非连通图可分解为多个连通分量
本站网友 编程入门教程
20分钟前 发表
图存储结构可细分两种表现类型
本站网友 太监是割哪里
22分钟前 发表
此路径又被称为"简单路径";同样
本站网友 长春祛痘
4分钟前 发表
(v1
本站网友 汇丰中国
27分钟前 发表
图存储结构基本常识弧头和弧尾有向图中
本站网友 blackbird
30分钟前 发表
这是一个回路(环)
本站网友 网站运营推广
10分钟前 发表
则称此图为"稠密图"
本站网友 海狗肾
23分钟前 发表
例如
本站网友 成才网
0秒前 发表
V4 的图结构
本站网友 西电e流
25分钟前 发表
V2> 的区别无向图中描述两顶点(V1 和 V2)之间的关系可以用 (V1
本站网友 析构
24分钟前 发表
分别是 "一对一"
本站网友 上海牙齿整形
7分钟前 发表
V2) 和 <V1
本站网友 yy7752
24分钟前 发表
v1>}
本站网友 百合的功效与作用及食用方法
12分钟前 发表
可分解为 个连通分量