表示图的三种常用的存储结构

在计算机科学中，图是一种有向或无向的数据结构，它由一组顶点和一组连接这些顶点的边组成。例如，社交网络中的人和他们之间的联系，经济网络中的公司和他们之间的合作，这些都可以通过图来表示。为了在程序中处理图，我们需要将图存储在内存中，那么表示图的存储方式有哪些呢？本文将介绍三种常用的存储结构：邻接矩阵、邻接表以及关联数组。

一、邻接矩阵

邻接矩阵是最简单也最直观的图的存储结构之一。它是一个二维数组，数组的行和列分别表示图中每个顶点的编号。如果图是无向图并且存在边 (i, j) 以及 (j, i)，则数组的 (i, j) 与 (j, i) 都应该设置为 1。如果图是有向图，则只需设置数组的 (i, j) 为1。

示例如下，假设图的顶点个数为4，下面是邻接矩阵的表示：

```

1 2 3 4

+--------

1 | 0 1 0 1

2 | 1 0 1 1

3 | 0 1 0 0

4 | 1 1 0 0

```

邻接矩阵的优点是可以快速地查找两个顶点是否存在边。但是，对于稀疏图，邻接矩阵会浪费很多空间，因为大部分数组元素都是0。此外，邻接矩阵只适用于边数比较少的图，因为如果边数太多，矩阵的大小会非常大，导致不可行。

二、邻接表

邻接表是一种存储稀疏图的数据结构，它将每个顶点的所有边存储为一个链表。图中所有链表的头结点组成了一个数组，其中，数组的下标就是顶点的编号。因为每个链表只存储与它相邻的顶点，所以邻接表的空间复杂度正比于边的数量。

示例如下，同样假设图的顶点个数为4，下面是邻接表的表示：

```

1 -> 2 -> 4

2 -> 1 -> 3 -> 4

3 -> 2

4 -> 1 -> 2

```

邻接表的优点是可以有效地存储稀疏图。另外，它的空间复杂度取决于边数，因此可以适用于存储数量巨大，边数不可估量的图。

三、关联数组

如果图的顶点可以用字符串或其它复杂数据类型来表示，那么关联数组（也称为字典或哈希表）是一种更合适的存储方式。关联数组基于键值对的思想，它将每个顶点表示为一个键，然后将与该顶点有关系的顶点表示为值的列表。关联数组可以使用任何哈希函数来实现，这意味着它可以快速地插入和查找。

示例如下，图的顶点用字符串表示：

```

"A" -> ["B", "C"]

"B" -> ["A", "C", "D"]

"C" -> ["A", "B"]

"D" -> ["B"]

```

关联数组的优点是可以存储各种类型的顶点，而且可以根据键值快速地查找，但是其空间复杂度仍然与边数成正比。

综上所述，邻接矩阵适用于边数比较少，且图的结构比较简单的情况；邻接表适用于存储稀疏图；关联数组适用于图的顶点用字符串或其它复杂数据类型表示的情况。在实际应用中，应选择适合的存储方式以提高程序的效率和减少内存的使用。