图的基本存储结构有哪些

图（Graph）是离散数学中的重要概念，它由节点（vertex）和边（edge）组成，表示事物之间的关系。在计算机科学中，图被广泛应用于算法、数据结构、网络等领域。本文将从多个角度分析图的基本存储结构，帮助读者更好地理解和应用图。

一、邻接矩阵

邻接矩阵是最直接的图存储结构，它用一个二维数组表示图的所有边。如果节点 i 和节点 j 之间有边相连，那么邻接矩阵中对应位置的值为 1，否则为 0。例如，下面的图的邻接矩阵表示如下：

```

1 2 3

1 0 1 1

2 1 0 0

3 1 0 0

```

这意味着节点 1 与节点 2、3 相连，节点 2 只与节点 1 相连，节点 3 只与节点 1 相连。邻接矩阵的好处在于可以方便地查找任意两个节点之间的关系，例如是否有路径相连、路径的长度等，但是当图的节点数较多时，矩阵会变得非常稀疏，浪费存储空间，因此邻接矩阵适合稠密图。

二、邻接表

邻接表是一种链表的形式，对于每个节点，它包含一个链表，记录与它相连的所有节点。例如，下面的图的邻接表表示如下：

```

1 -> 2 -> 3

2 -> 1

3 -> 1

```

这意味着节点 1 与节点 2、3 相连，当我们访问节点 1 时，可以通过它的链表快速地遍历到与它相连的所有节点。邻接表的好处在于可以用较少的空间表示稀疏图，但是对于稠密图，由于每个节点都要维护一个链表，因此空间会较大。

三、邻接多重表

邻接多重表是邻接表的改进版，它将每条边都表示为两个节点之间的一个结构体，结构体中包含了指向它们各自的下一条边的指针。例如，下面的图的邻接多重表表示如下：

```

Vertex|Edge

-------------

1 | 2 -> 3

2 | 1

3 | 1

```

这意味着节点 1 与节点 2、3 之间有一条边，当我们访问这条边时，可以通过结构体的指针快速地找到下一条边，提高遍历的效率。邻接多重表的好处在于可以用较少的空间存储无向图，但是对于有向图，需要增加一个反向链表才能表示。

四、十字链表

十字链表是邻接多重表的变种，它记录了有向图中每个节点的入度和出度，并且可以用链表的形式存储相邻的节点。例如，下面的图的十字链表表示如下：

```

Out | In

Vertex->Vertex

----------------

1 -> 2 -> 3

2 -> 1 |

3 -> 1 |

```

这意味着节点 1 有两条出边以及两条入边，当我们访问它的某条边时，可以直接从它的出边链表或入边链表中找到对应的节点。十字链表的好处在于可以用较少的空间存储有向图，但是对于稠密的有向图，空间仍然会很大。

综上所述，邻接矩阵、邻接表、邻接多重表、十字链表都是常见的图存储结构，每种结构都有其优点和缺点，应根据实际需求来选择。对于稠密图，适合使用邻接矩阵；对于稀疏图，适合使用邻接表和邻接多重表；对于有向图，适合使用十字链表。在实际应用中，我们还可以结合不同的存储结构，根据具体情况进行组合使用。