图的存储结构有

图是离散数学中的一个重要概念，也是许多实际问题中的建模工具。在计算机科学中，图的存储结构有多种方式，本文将从多个角度对其进行分析。

一、邻接矩阵

邻接矩阵是图的最基本且常用的存储方式之一。它使用一个二维数组来表示整个图，其中每一个元素表示一个边或弧是否存在，值为1表示存在，值为0表示不存在。图中每一个顶点对应数组的一行或一列，可以通过下标访问对应的边或弧。邻接矩阵能够快速地检索任意两个顶点之间是否有边或弧相连，其时间复杂度为O(1)，但对于稀疏图而言，矩阵中大量的0会浪费大量的存储空间。同时，邻接矩阵不能表示带权图。

二、邻接表

邻接表是一种基于链表的图存储结构，将每个顶点和它所连的边或弧连成一个链表。由于链表的大小不受限制，邻接表非常适合存储稀疏图，能够有效地节约存储空间。邻接表的时间复杂度取决于链表的长度，因此其查询效率与图的稠密程度有关。同时，邻接表可以很好地表示带权图，只需在链表中增加一个权重字段即可。

三、十字链表

十字链表是有向图的邻接表的一种扩展。它将每个顶点的入边和出边分别建立两个链表，用一个节点来表示一个边或弧，同时记录该边的起始点和终点。通过十字链表，可以快速地查找一个顶点的所有入边和出边，同时也能够很好地支持拓扑排序、最长路径等操作。

四、邻接多重表

邻接多重表是无向图的一种链式存储结构。它每个节点包含了该边的两个顶点信息以及连接两个顶点的两条链表，分别存储与该边同端点的其他边。邻接多重表适用于存储无向图，它可以较好地支持无向图的遍历和连通性判断。

综上所述，不同的图具有不同的存储结构，每种结构都有其优缺点和适用场景。通过选择合适的存储结构，可以大大提高图算法的效率。