图有几种存储结构

图是一种数据结构，在计算机领域中有广泛的应用，比如社交网络中的关系图、城市道路的路径规划等。而图的存储结构是指如何在计算机中表示和储存图形数据。目前常见的图存储结构有三种：邻接矩阵、邻接表和十字链表。本文将从多个角度对这三种结构进行分析。

一、空间复杂度

邻接矩阵是最简单、直观的存储方式，它将整个图以一个二维矩阵的形式储存。其中，矩阵的行列代表图中的节点，矩阵的值表示节点间的关系（连通则为1，否则为0）。邻接矩阵的空间复杂度为O(n^2)，其中n为节点数。虽然这种方式十分容易实现，但对于大规模图会浪费大量空间，而且修改相邻节点的关系需要O(1)时间。

邻接表是一种链式结构，每个节点都对应一个链表，每个链表存储该节点相邻的节点。每个链表中存储的是与该节点相关的边信息，例如边的权重、边所指向的节点等。邻接表的空间复杂度为O(n+e)，其中n为节点数，e为边数。相比邻接矩阵，邻接表可以有效节约空间并支持较大规模的图，但是需要O(d)时间才能查找节点。其中，d是节点的度数，表示与该节点相连的边的数量。

十字链表，也称伸出型邻接表，是一种在邻接表的基础上改进的存储结构。它将每个节点拆成两个部分：正向部分和反向部分，分别存储该节点的出边和入边。由于每条边都是一个数据结构，包含了边的起点、终点以及权重等信息。因此，十字链表的空间复杂度与邻接表相同，均为O(n+e)。

二、时间复杂度

对于图的遍历、查找、插入和删除等操作，各种存储结构的时间复杂度如下所示：

- 邻接矩阵

- 查找节点关系：O(1)

- 插入、删除节点和边：O(1)

- 遍历整个图：O(n^2)

- 邻接表

- 查找节点关系：O(d)

- 插入、删除节点：O(d+e)

- 插入、删除边：O(1)

- 遍历整个图：O(n+e)

- 十字链表

- 查找节点关系：O(d)

- 插入、删除节点：O(d+e)

- 插入、删除边：O(1)

- 遍历整个图：O(n+e)

由此可见，邻接矩阵的查找速度最快，但在插入删除节点和边的操作中会变得较慢。而邻接表和十字链表由于是链式存储，所以查找速度较慢，但插入和删除节点边的操作非常快。

三、适用场景

由于三种存储结构各有优缺点，因此应根据实际需求选择合适的存储方式。

- 邻接矩阵适用于节点稠密的图，例如密集的图形结构、网格结构等。邻接矩阵在处理稠密图时，时间复杂度比较低，在查找结点关系时效率很高。

- 邻接表适用于节点少而边多的稀疏图，例如社交网络、公路网络等。邻接表可以非常高效地储存和操作稀疏图。这是因为邻接表只储存与节点相邻接的节点信息，同时，插入和删除一个节点和该节点相关所有边的复杂度为O(d + e)也比较低。

- 十字链表适用于有向图或者有向网络中的点和边，例如计算机网络拓扑结构、交通信号灯系统中的控制逻辑等。与邻接表相似，它既可以储存有向图的节点信息，也可以储存有向边的方向，因此比邻接表更加灵活。

综上所述，邻接矩阵、邻接表、十字链表都有各自优缺点，应据实际需求选择最适合的存储结构。