图数据的存储

发布时间:2024年01月18日

图是一种比较复杂的数据结构,为适应图数据的增删改查,采用的存储结构有邻接矩阵、邻接表、十字链表、邻接多重表、边集数组等。

一 邻接矩阵

用两个数组来表示图,其中一个数组存储顶点信息,另一个二维数组存储边信息,即一个顶点数组和一个边数组,这个二维的边数组存储的就是邻接矩阵。

无向图的邻接矩阵是一个对称矩阵,主对角线为零,行或列的和称为顶点的度。有向图的邻接矩阵则不一定对称。

无向图的邻接矩阵:

有向图的邻接矩阵:

优点:简单直观,适用于稠密图,快速检查两个顶点之间是否有边连接。

缺点:对于稀疏图,浪费了大量存储资源。且在邻接矩阵中添加顶点时必须重新按照新的行或列创建,然后将已有的数据复制到新的矩阵中。

二 邻接链表

邻接链表中,图中的所有顶点采用一个专门的数组存储,每个顶点的临边采用链表存储,链表的起止地址信息也会存储顶点数组中。有向图的临界表中的单链表只存储了出度节点。

邻接表中每个结点的单链表长度就是该节点的出度,带权邻接表只需给边结点增加一个存储权值的数据域即可。

无向图邻接链表:

   1
  / \
 2 - 3
 | /
 4

1: 2 -> 3
2: 1 -> 3 -> 4
3: 1 -> 2 -> 4
4: 2 -> 3

有向图邻接链表:

  1
  ↓
  2 → 3
 ↗ ↙
 4

1: → 2
2: → 3
3: 
4: → 2

优点:适用于稀疏图,节省存储空间;插入或删除边的操作相对较为高效。

缺点:需要额外的空间存储链表,查找节点之间是否有边的操作相对慢。

三 十字链表

十字链表也叫做正交链表,是为了存储有向图专门设计的一种存储结构,综合了邻接表和逆邻接表,多占了一些空间,但计算出度和入度都非常方便,并且创建图的时间复杂度和邻接表相比并没有增加。

每个顶点节点设置两个指针域,一个指向入边表的指针,另一个指向出边表的指针。

   1
 ↗ ↑ ↖
 2  -  3
 ↓  ↘ ↓
 4     5


#节点结构
+-----+
|  1  |
+-----+
| OUT | --> (2, w1) --> (3, w2)
| IN  | --> (2, w3) --> (4, w4) --> (5, w5)
+-----+

#出边表
Outgoing Edge List for Node 1:
(2, w1) --> (3, w2)

#入边表
Incoming Edge List for Node 1:
(2, w3) --> (4, w4) --> (5, w5)

四 邻接多重表

邻接多重表是邻接表针对无向图进一步优化的产物。邻接表对顶点的操作很方便,但对边的操作很不方便,如删掉一条边,由于邻接表中的每一条边都涉及两个顶点,所以删除一条边需要操作两个顶点。

邻接多重表的设计使每一条边都用一个点表示。邻接多重表和十字链表略有相似,都通过边节点结构中的指针域相互指向,使边界点的数目可以等于边的数目,而不是边数目的二倍。

文章来源:https://blog.csdn.net/qq_44858786/article/details/135652271
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。