直观理解：常用的图存储结构

  图的存储结构相对于计算机中常见的数据结构：线性表、集合等来说更为复杂，因为图中的顶点具有相对概念，没有固定的位置，且顶点和顶点之间通过添加和删除边，维持着不同的关系。那么一般情况下该怎么存储图的数据结构呢？这里我们列出了三种常用的图存储结构，供大家在学习和工作中进行参考。

邻接矩阵（Adjacency Matrix）

  图的邻接矩阵(Adjacency Matrix)是一种常见的图存储结构，邻接矩阵中，顶点和边是分开存储的，如果不需要保存每个顶点的数据而只考虑点和点之间的关系，那么也可以直接保存成一个二维矩阵，用来表示任意两点之间的权重距离。这种情况下，如果不存在自旋的边，那么所有主对角线全是0。在有向图中，如果两个顶点之间只有一条单向的边，那么反方向的值在矩阵中用空值或者∞表示。当每个顶点的边数量较小而顶点数量较多时，该图的邻接矩阵会非常稀疏，会造成极大的存储空间浪费。因此，只有在图中的点数量相对较少，且边数量相对较多的情况下，才推荐使用邻接矩阵的方式进行图结构存储。下面分别展示了有向图和无向图的邻接矩阵的存储结构。

有向图—邻接矩阵 无向图—邻接矩阵

邻接表（Adjacency List）

  邻接表(Adjacency List)是另一种常用的图存储结构，该结构中，使用用一个线性表存储图中的顶点，然后将与之邻接的顶点依次构成一个线性表，由于邻接点的数量通常不确定，因此经常使用链表对邻接顶点进行存储。邻接表有很多变种的存储结构，例如逆邻接表、十字链表、邻接多重表等。它们本质上都属于邻接表的范畴，没有太大区别。使用邻接表进行图结构存储，当图中顶点关联的边较多时，顶点的邻接链表往往很长，因此当查找和遍历一个点的边时往往比较费时，因此当图中顶点关联的边较多时，使用邻接表进行图操作性能往往不会太好。下面分别展示了有向图和无向图的邻接表的存储结构。

有向图—邻接表 无向图—邻接表

边集数组（Edgeset Array）

  边集数组（Edgeset Array）是目前比较流行的一种属性图存储结构，它由一个存储顶点信息的顶点数组和一个存储边信息的边数组构成，并且边数组中每个元素表示着一条边的起点索引，终点索引和权重。可以看出用这种存储结构表示图非常简洁而且灵活，是对图数据进行抽象的结果，因为图数据归根结底就是顶点和边的集合。边集数组是一种针对大规模图数据的存储结构，目前常用的大规模图计算引擎Spark GraphX、Flink Gelly以及目前常用的数据库Neo4j，Nebula Graph等底层都是采用类似边集数组及其变种的存储结构进行图结构存储。该存储结构在Out-of-Core图计算系统中比较常见，因为无论是存储在内存中还是外存中都方便读写和构造。下面分别展示了有向图和无向图的边集数组的存储结构。

有向图—边集数组 无向图—边集数组

  以上就是三种常见的图存储结构，每种存储结构都有其特定的应用场景，在实际使用时，需要根据实际的图数据分布情况和应用场景进行选择。