图的存储结构是什么?各有什么特点

图的存储结构是什么？各有什么特点？

在计算机科学中，图被表示为由节点（vertex）和边（edge）构成的集合。由于其各种应用（如网络分析、图像处理等），对图的高效操作需求也在不断提高。因此，合理的图存储结构对于提高算法效率至关重要。本文将介绍常见的三种图存储结构：邻接矩阵、邻接表和十字链表，并分析它们的优缺点和适用范围。

一、邻接矩阵

邻接矩阵是图存储中最简单和最常见的结构。可以使用二维数组来表示，在其[i][j]位置上存储节点i至节点j是否连通的信息（一般用1表示相邻，0表示不相邻）。该结构的特点在于：

1. 使用简单

其实现方法直观易懂，易于理解和实现。

2. 查找快速

可以快速进行两节点间的遍历，时间复杂度为O(1)。

3. 存储占用空间大

如果节点间的边数过多，邻接矩阵会占用大量的存储空间，浪费空间。

另外当节点对多时遍历时时间会遗味为O(n^2)。所以适用于节点数量大，边数量较少的情况。

二、邻接表

邻接表是用链表存储每个节点周围节点的方法。 我们还需要一个数组（高维数组）来存储每个节点对应的链表。 如果有n个节点，则需要n个链表，当某两个节点之间存在连线时，只需要在它们对应的链表中添加元素即可。邻接表的特点在于：

1. 存储占用空间较小

只需要存储每个节点的信息和其周围节点的信息，所以它的空间利用率比邻接矩阵的高。

2. 查找有速度差异

如果节点的度数很小（即与之相连的其他节点很少），那么基于邻接表实现的查找速度可能会较快；但对于度数很大的节点，查找速度就可能会变慢（比如我们得创建很多链表，在走链表时比较费时间）;

三、十字链表

十字链表是邻接表的扩展。邻接表每个节点只能存储指向其它节点的指针，而不知道有多少条边到该节点，因此需要修改步调表来实现存储，这种方法就是十字链表。它主要使用一个数组来存储每个节点。

顾名思义，它本质上是链表，因此也是使用链表的形式连接每个节点和它周围的节点，不过它记录的是由该节点引出和到达该节点的边（这就是十字链表的名字），它的表头指针指向与该节点相邻的顶点链表。 十字链表的特点如下：

1. 存储占用空间较小

仅存储每个节点的度数和它周围节点的信息，因此它的空间利用效率非常高。

2. 可以减少时间的浪费

采用堆边加快遍历速度和内存占用，合理动态性能对于子串误差率提高具有一定的效果。

综上所述，图的存储结构具有各自的优劣，邻接矩阵适用于节点数量较少，边数量较多的情况，邻接表适用于节点数量较多，边数量较少的情况，十字链表可更好地解决更大型图的问题。