图的存储方式有几种

图是计算机科学中常用的数据结构之一。在计算机中，图通常用于表示物体之间的关系。而在图的存储中，我们需要考虑如何把这个结构表示出来。在这篇文章中，我们将探讨不同的图的存储方式及其优缺点。

1. 邻接矩阵

邻接矩阵是最常见的图的存储方式。它使用二维数组表示图的每个节点之间的关系，其中，数组的行和列代表节点，如果两个节点之间有一条边，则相应的数组的值为1。邻接矩阵在存储密集图时非常高效，因为它允许我们在O(1)的时间内检查两个节点之间是否存在一条边。

然而，邻接矩阵在存储稀疏图时效率不佳。因为矩阵中大部分元素都是0，这样会浪费大量内存空间。

2. 邻接表

邻接表存储方式使用链表来表示节点和它所连向的其他节点。每个节点都有一个指向它的链表，其中保存了它所连向的节点。邻接表在存储稀疏图时非常高效，因为它只存储了实际存在的边。

然而，邻接表在访问密集图时效率较低。因为邻接表需要在链表中进行顺序遍历，这需要O(V+E)的时间复杂度，其中V是节点数，E是边数。

3. 关联矩阵

关联矩阵使用一个二维数组表示图的每条边和每个节点之间的关系。其中，行代表节点，列代表边，如果一个节点与一条边有关系，则相应的数组值为1或-1，取决于这个节点是这条边的起点还是终点。

关联矩阵在存储有向图时非常有用，它不仅可以表示节点之间的关系，还可以表示节点之间的距离。然而，它的缺点也很明显，它需要更多的内存空间，因为其中包含了每个节点和每条边的信息。

综上所述，不同的图存储方式有不同的优缺点，可以根据具体的应用场景来选择合适的存储方式。