郑州大旗网站制作公司,适合小学生的新闻事件,做网站业务员,网站建设浦东目录
数据结构的图存储结构
图存储结构基本常识
弧头和弧尾
入度和出度
(V1,V2) 和 的区别,v2
集合 VR 的含义
路径和回路
权和网的含义
图存储结构的分类
什么是连通图#xff0c;#xff08;强#xff09;连通图详解
强连通图
什么是生成树#xff0c;生… 目录
数据结构的图存储结构
图存储结构基本常识
弧头和弧尾
入度和出度
(V1,V2) 和 的区别,v2
集合 VR 的含义
路径和回路
权和网的含义
图存储结构的分类
什么是连通图强连通图详解
强连通图
什么是生成树生成树生成森林详解
生成森林 数据结构的图存储结构
我们知道数据之间的关系有 3 种分别是 一对一、一对多 和 多对多前两种关系的数据可分别用线性表和树结构存储本节学习存储具有多对多逻辑关系数据的结构——图存储结构。 图 1 图存储结构示意图 图 1 所示为存储 V1、V2、V3、V4 的图结构从图中可以清楚的看出数据之间具有的多对多关系。例如V1 与 V4 和 V2 建立着联系V4 与 V1 和 V3 建立着联系以此类推。 与链表不同图中存储的各个数据元素被称为顶点而不是节点。拿图 1 来说该图中含有 4 个顶点分别为顶点 V1、V2、V3 和 V4。
图存储结构中习惯上用 Vi 表示图中的顶点且所有顶点构成的集合通常用 V 表示如图 1 中顶点的集合为 V{V1,V2,V3,V4}。 注意图 1 中的图仅是图存储结构的其中一种数据之间 多对多 的关系还可能用如图 2 所示的图结构表示 图 2 有向图示意图 可以看到各个顶点之间的关系并不是双向的。比如V4 只与 V1 存在联系从 V4 可直接找到 V1而与 V3 没有直接联系同样V3 只与 V4 存在联系从 V3 可直接找到 V4而与 V1 没有直接联系以此类推。 因此图存储结构可细分两种表现类型分别为无向图图 1和有向图图 2。
图存储结构基本常识
弧头和弧尾
有向图中无箭头一端的顶点通常被称为初始点或弧尾箭头直线的顶点被称为终端点或弧头。
入度和出度
对于有向图中的一个顶点 V 来说箭头指向 V 的弧的数量为 V 的入度InDegree记为 ID(V)箭头远离 V 的弧的数量为 V 的出度OutDegree记为OD(V)。拿图 2 中的顶点 V1来说该顶点的入度为 1出度为 2该顶点的度为 3。
(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,v3),(v3,v4)}图 2 中有向图的集合 VR{v1,v2,v1,v3,v3,v4,v4,v1}。
路径和回路
无论是无向图还是有向图从一个顶点到另一顶点途径的所有顶点组成的序列包含这两个顶点称为一条路径。如果路径中第一个顶点和最后一个顶点相同则此路径称为回路或环。 并且若路径中各顶点都不重复此路径又被称为简单路径同样若回路中的顶点互不重复此回路被称为简单回路或简单环。 拿图 1 来说从 V1 存在一条路径还可以回到 V1此路径为 {V1,V3,V4,V1}这是一个回路环而且还是一个简单回路简单环。
在有向图中每条路径或回路都是有方向的。
权和网的含义
在某些实际场景中图中的每条边或弧会赋予一个实数来表示一定的含义这种与边或弧相匹配的实数被称为权而带权的图通常称为网。如图 3 所示就是一个网结构 图 3 带权的图存储结构 子图指的是由图中一部分顶点和边构成的图称为原图的子图。
图存储结构的分类
根据不同的特征图又可分为完全图连通图、稀疏图和稠密图
完全图若图中各个顶点都与除自身外的其他顶点有关系这样的无向图称为完全图如图 4a)。同时满足此条件的有向图则称为有向完全图图 4b)。 图 4 完全图示意图
具有 n 个顶点的完全图图中边的数量为 n(n-1)/2
对于具有 n 个顶点的有向完全图图中弧的数量为 n(n-1)。 稀疏图和稠密图这两种图是相对存在的即如果图中具有很少的边或弧此图就称为稀疏图反之则称此图为稠密图。 稀疏和稠密的判断条件是enlogn其中 e 表示图中边或弧的数量n 表示图中顶点的数量。如果式子成立则为稀疏图反之为稠密图。 什么是连通图强连通图详解 前面讲过图中从一个顶点到达另一顶点若存在至少一条路径则称这两个顶点是连通着的。例如图 1 中虽然 V1 和 V3 没有直接关联但从 V1 到 V3 存在两条路径分别是 V1-V2-V3 和 V1-V4-V3因此称 V1 和 V3 之间是连通的。 图 1 顶点之间的连通状态示意图 无向图中如果任意两个顶点之间都能够连通则称此无向图为连通图。例如图 2 中的无向图就是一个连通图因为此图中任意两顶点之间都是连通的。 图 2 连通图示意图 若无向图不是连通图但图中存储某个子图符合连通图的性质则称该子图为连通分量。
前面讲过由图中部分顶点和边构成的图为该图的一个子图但这里的子图指的是图中最大的连通子图也称极大连通子图。
如图 3 所示虽然图 3a) 中的无向图不是连通图但可以将其分解为 3 个最大子图图 3b)它们都满足连通图的性质因此都是连通分量。 图 3 连通分量示意图
提示图 3a) 中的无向图只能分解为 3 部分各自连通的最大子图。
需要注意的是连通分量的提出是以整个无向图不是连通图为前提的因为如果无向图是连通图则其无法分解出多个最大连通子图因为图中所有的顶点之间都是连通的。
强连通图
有向图中若任意两个顶点 Vi 和 Vj满足从 Vi 到 Vj 以及从 Vj 到 Vi 都连通也就是都含有至少一条通路则称此有向图为强连通图。如图 4 所示就是一个强连通图。 图 4 强连通图 与此同时若有向图本身不是强连通图但其包含的最大连通子图具有强连通图的性质则称该子图为强连通分量。 图 5 强连通分量 如图 5 所示整个有向图虽不是强连通图但其含有两个强连通分量。 可以这样说连通图是在无向图的基础上对图中顶点之间的连通做了更高的要求而强连通图是在有向图的基础上对图中顶点的连通做了更高的要求。
什么是生成树生成树生成森林详解 对连通图进行遍历过程中所经过的边和顶点的组合可看做是一棵普通树通常称为生成树。 图 1 连通图及其对应的生成树 如图 1 所示图 1a) 是一张连通图图 1b) 是其对应的 2 种生成树。
连通图中由于任意两顶点之间可能含有多条通路遍历连通图的方式有多种往往一张连通图可能有多种不同的生成树与之对应。
连通图中的生成树必须满足以下 2 个条件
包含连通图中所有的顶点任意两顶点之间有且仅有一条通路 因此连通图的生成树具有这样的特征即生成树中边的数量 顶点数 - 1。
生成森林
生成树是对应连通图来说
而生成森林是对应非连通图来说的。 我们知道非连通图可分解为多个连通分量而每个连通分量又各自对应多个生成树至少是 1 棵因此与整个非连通图相对应的是由多棵生成树组成的生成森林。 图 2 非连通图和连通分量 如图 2 所示这是一张非连通图可分解为 3 个连通分量其中各个连通分量对应的生成树如图 3 所示 图 3 生成森林
注意图 3 中列出的仅是各个连通分量的其中一种生成树。
因此多个连通分量对应的多棵生成树就构成了整个非连通图的生成森林。
