黑客必知数据结构知识:什么是图?它的存储结构是什么?

一、图的定义

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

二、图的基本概念

1,无向图:如果图中任意两个顶点之间的边都是无向边,简而言之就是没有方向的边。

2,有向图:如果图中任意两个顶点之间的边都是有向边,简而言之就是有方向的边。

3,顶点的度:是指在图中与顶点相关联的边的条数。对于有向图来说,有入度和出度之分,有向图顶点的度等于该顶点的入度和出度之和。

三、图的存储结构

图的存储结构除了要存储图中的各个顶点本身的信息之外,还要存储顶点与顶点之间的关系,因此,图的结构也比较复杂。常用的图的存储结构有邻接矩阵和邻接表等。

1,邻接矩阵法

图的邻接矩阵存储方式是用两个数组来表示图。一个一维数组存储图中顶点信息,一个二维数组(称为邻接矩阵)存储图中的边或弧的信息。也分为有向图和无向图。我们在此只看有向图。

如下图所示的左边。顶点数组为vertex[4]=,弧数组arc[4][4]为下图右边这样的一个矩阵。主对角线上数值依然为0。但因为是有向图,所以此矩阵并不对称,比如由v1到v0有弧,得到arc[1][0]=1,而v到v没有弧,因此arc[0][1]=0。

2,邻接表法

邻接表由表头节点和表节点两部分组成,图中每个顶点均对应一个存储在数组中的表头节点。如果这个表头节点所对应的顶点存在邻接节点,则把邻接节点依次存放于表头节点所指向的单向链表中。

我们来看个无向表的例子: 从上图中我们知道,顶点表的各个结点由data和firstedge两个域表示,data是数据域,存储顶点的信息,firstedge是指针域,指向边表的第一个结点,即此顶点的第一个邻接点。边表结点由adjvex和next两个域组成。adjvex是邻接点域,存储某顶点的邻接点在顶点表中的下标,next则存储指向边表中下一个结点的指针。例如:v1顶点与v0、v2互为邻接点,则在v1的边表中,adjvex分别为v0的0和v2的2。

我们再看个有向表的例子:若是有向图,邻接表结构是类似的,但要注意的是有向图由于有方向的。因此,有向图的邻接表分为出边表和入边表(又称逆邻接表),出边表的表节点存放的是从表头节点出发的有向边所指的尾节点;入边表的表节点存放的则是指向表头节点的某个顶点,如下图所示。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181129A1MBA500?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券