常用的图的存储结构有几种

在计算机科学中，图（Graph）是一种常用的数据结构，用于表示各种关系和网络。在实际应用中，图的数据量通常很大，因此采用不同的存储结构可以影响图的运算效率和程序的性能。常见的图的存储结构主要有邻接矩阵、邻接表、十字链表和邻接多重表等。下面就分别从多个角度分析这些存储结构。

邻接矩阵是图的一种常见的存储结构，可以用一个二维数组来表示。在这个二维数组中，数组的每一个元素都代表一条边的连通情况，若两个顶点之间有一条边，则对应的数组元素值为1，否则为0。这种结构适用于密集图，因为它非常紧凑，并且能够快速地判断两个点之间是否存在连通关系。

邻接表是一个由链表组成的数组。在这个数组中，每个节点有两个属性：一个存储顶点的值，另一个是指向和该顶点相邻的所有顶点的指针。这种结构适用于稀疏图，因为它比邻接矩阵更省空间，而且能够快速地查询某个顶点的所有相邻顶点。

十字链表是一种适用于有向图的存储结构，这种结构由两个部分组成：顶点表和边表。在顶点表中，每个节点包含节点的值以及两个指针，分别指向与该顶点相关联的入边和出边的链表的表头。在边表中，每个节点包含指向起始顶点和结束顶点的指针，以及指向与该边同起点或同终点的下一条边的指针。这种结构适用于具有大量指向和离开某个节点的边的有向图。

邻接多重表是一种适用于无向图的存储结构，它结合了邻接表和边表的元素。每个节点包含节点的值以及两个指针，分别指向与该顶点相关联的入边和出边的链表的表头。在边表中，每个节点包含指向起始顶点和结束顶点的指针，以及指向与该边同起点或同终点的下一条边的指针。这种结构适用于具有大量相邻顶点的无向图。

总之，对于不同的图，我们需要选择不同的存储结构。邻接矩阵适用于密集图，邻接表适用于稀疏图，十字链表适用于有向图，邻接多重表适用于无向图。