阅读:0       作者:严长生

数据结构中的图存储结构

通过前面的学习,已经接触到了线性表和树两种数据结构。对于之间具有“一对一”关系的数据,可以选择使用线性表进行表示和存储;之间具有“一对多”关系的数据,可以考虑使用树进行表示和存储。除此之外,对于之间还可能具有“多对多”关系的数据,数据结构表示和存储这类数据的结构使用的是——

有关图的基本常识

图 1 有向图和无向图

顶点 :使用图表示的每个数据元素称作顶点(Vertex),图中所有顶点构成的集合习惯上用 V 表示。
例如,图 1(A) 表示的就是一个图,其中 V1、V2、V3、V4 都是构成图的顶点,用集合 V 表示为:{V1,V2,V3,V4}
VR :VR 本身是集合,存储的是任意两个顶点之间的关系。

顶点之间的关系有两种:如图 1 中的两个图所示,(A)中顶点 V1 和 V2 只有单方向的关系,只能通过 V1 找到 V2,反过来行不通,因此两顶点之间的关系表示为:<V1,V2>;另一种关系如(B),顶点之间具有双向的关系,之间用直线连通,对于V1 和 V2 顶点来说,既可以通过 V1 找到 V2,也可以通过 V2 找到 V1,两顶点之间的关系表示为:(V1,V2)

图 1(A)中,VR 集合存储的顶点之间的关系为:
{<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>};
图 1(B)中,VR 集合存储的顶点之间的关系为:
{(v1,v2),(v1,v4),(v2,v3),(v3,v4),(v3,v5)}


有向图和无向图 :之间只具有单向关系的顶点构成的图称为有向图,如图 1 (A);之间具有双向关系的顶点构成的图称为无向图,如图 1(B)。

“弧”和“边” :在有向图中,<v,w> 表示为从 v 到 w 的一条;在无向图中,(v,w)表示为顶点 v 和顶点 w 之间的一条

例如,图 1(A)为有向图,每个箭头表示从一个顶点到另一个顶点的一条弧,其中无箭头一端的顶点又被称为“弧尾”或者“初始点”;有箭头一端的顶点称为“弧头”或者“终端点”。图 1(B) 为无向图,每条直线表示顶点之间的一条边。

完全图 :对于无向图来说,如果图中每个顶点都和除自身之外的所有顶点有关系,那么就称这样的无向图为完全图。如图 2 所示就是一个完全图。

图 2 完全图

对于有 n 个顶点的完全图,其中的边的数目为:


有向完全图 :对于有向图来说,通过图中的每个顶点,都能找到图中的所有其它的顶点,那么就称这样的有向图为有向完全图。如图 3 所示就是一个有向完全图。


图 3 有向完全图
对于有 n 个顶点的有向完全图,所具有的弧的数目为:

稀疏图和稠密图 :如果图中具有很少的边或弧,就称这个图为“稀疏图”;反之,称为“稠密图”

稀疏和稠密的判断条件是:e < nlogn(e表示图中边或弧的数量,n为顶点数),满足条件即为稀疏图;反之为稠密图。

权 :图中的边或者弧有时会携带有一个与之相匹配的数,这种与边或弧相匹配的数被称为“权”。相应地,带权的图通常称为“网”(Network)。
每一条边或者弧的权往往具备某种意义,例如代表从一个顶点到另一个顶点之间的距离,等等。
子图 :图中的一部分顶点和边构成的图,称为原图的子图。

出度和入度

在有向图中,对于一个顶点 v 来说,箭头指向顶点 v 的弧的数目为该顶点的入度(InDegree,记为ID(v));箭头远离顶点 v 的弧的数目为该顶点的出度(OutDegree,记为OD(v)) 有向图顶点的度就是该顶点出度和入度的和。例如图 1(A)中,顶点 V1 的入度为 1 ,出度为 2 ,所以顶点V1的度为 3 。

路径和回路

路径 :在图中从一个顶点到另一个顶点所走过的多个顶点组成的序列,就称为“路径”。 在有向图中,路径是有向的。如果在路径中第一个顶点和最后一个顶点相同,此路径称为“回路”“环”。 如果路径中每个顶点互相都不重复,这个路径就是简单路径;同样,一个回路中顶点之间不重复出现,称为“简单回路”“简单环”。 例如,在图 1(A)中,从 V1 回到 V1 存在一条路径,为:(V1,V3,V4,V1),此路径是一个环,也是一条简单回路。

连通图

在无向图中,如果一个顶点到另一个顶点存在至少一条路径,称它们之间是连通的。 如果图中任意两个顶点之间都是连通的,则此图为连通图。例如图 1(B)就是一个连通图。 如果一个图本身不是连通图,但是图中某个子图是连通图,那么这个子图又被称为“连通分量”

注意:这里的“子图”指的是无向图中最大的连通子图。

图 4 连通分量
例如,图 4(a)中本身不是连通图,但是本身有 3 个连通分量,如(B)所示。 在有向图中,如果任意一对顶点 Vi 和 Vj,从 Vi 到 Vj 和从 Vj 到 Vi 都含有至少一条通路,那么称此图为强连通图。如果有向图的连通分量也具有此特征,则为强连通分量。 例如,图 1(A)本身不是强连通图,但是如果删除 V2 这个顶点,就是一个强连通图,如图 5 所示。

图 5 强连通图

生成树和生成森林

对于连通图来说,如果对其进行遍历,遍历过程中经过的顶点和边其实质是一棵树,在这里称之为“生成树”

由于连通图中,任意两顶点之间可能含有多条通路,所以一个连通图可能会对应多个生成树。

对于连通图来说,它的生成树须满足两个要求:
  • 包含图中所有的顶点。
  • 任意两顶点之间有且仅有一条通路。

图 6 连通图及其生成树
 
例如,图 6(A)是一个连通图,(B)为它的生成树(不唯一)。 连通图的生成树中,边的数量永远要比顶点的数量少1。如果少更多,顶点之间无法做到连通;反之,生成树中会存在回路(环)。 生成树是针对于连通图而言的,如果是非连通图,其中含有的多个连通分量,每个连通分量对应不止一棵生成树,所以非连通图对应的是由多棵生成树组成的生成森林。

图 7 非连通图的生成森林
 
例如,图 4(a)本身为非连通图,其有 3 个连通分量(如图2(b)所示),每个连通分量分别对应的生成树如图 7 所示,3 个生成树构成的为非连通图的生成森林。

本节主要设计到有关图的一些基本概念,只有了解了这些基本常识,后边章节的内容才能看得懂。