图的存储的表示方法有哪些

图是一种非常重要的数据结构，它在很多领域应用广泛，比如计算机网络、社交网络等。图的存储方式有很多种，每一种方式都有其优缺点。本文将从多个角度分析图的存储的表示方法，帮助读者更好地了解图数据结构。

一、邻接矩阵

邻接矩阵是一种非常常用的图存储方式。它使用一个二维矩阵来表示图的关系，在矩阵中每一行和每一列代表某个顶点，如图1所示。如果该矩阵某个位置的值为1，则表示这两个顶点之间有一条边；否则，这两个顶点之间没有边。因此，邻接矩阵适用于表示稠密图。


邻接矩阵的优点是存取边的时间复杂度为O(1)，因为可以直接使用二维数组进行存取。然而，邻接矩阵需要O(n^2)的空间来存储图，其中n为图中顶点的个数。因此，当图是稀疏图时，邻接矩阵会浪费很多空间。

二、邻接表

邻接表是一种更加节省空间的图存储方式。它使用一张表来表示图的关系，其中每个顶点都有一条链表，链表中存储了与该顶点相连的边对应的顶点。如图2所示。


邻接表的优点是可以很好地表示稀疏图，并且占用的空间比邻接矩阵少得多。对于一个有n个顶点和m条边的图，邻接表的空间复杂度为O(n+m)。邻接表也比较容易扩展，可以很方便地加入新的顶点和边。

但是，邻接表的缺点是存取边的时间复杂度为O(k)，其中k是与该顶点相连的边的数量。因此，在某些场景下，邻接表的性能可能会比邻接矩阵差。

三、十字链表

十字链表是邻接表的一种变种。它不仅能够表示有向图，还能够表示无向图和混合图。十字链表将一个顶点的出边和入边分别组织成两条链表，每条边上记录了该边的起点和终点，以及该边对应的权值（如果有的话）。如图3所示。


十字链表的优点是可以很好地表示有向图和无向图，并且存储的空间比邻接矩阵和邻接表都要少。但是，由于它记录了每条边的起点和终点，因此在建立图时需要花费更多的时间。

四、邻接多重表

邻接多重表是一种用于存储无向图的数据结构。和十字链表一样，邻接多重表也是邻接表的一种变种。它将一个顶点的所有相邻节点放在同一个链表中，链表中的每个节点都存储了相邻节点的信息和该边对应的权值（如果有的话）。如图4所示。


邻接多重表的优点是可以很好地表示无向图，并且存储的空间比邻接矩阵和邻接表都要少。但是，和邻接表一样，存储的格式是链表，因此存取边的时间复杂度为O(k)，其中k是与该顶点相连的边的数量。

综上所述，邻接矩阵、邻接表、十字链表以及邻接多重表都有各自的优缺点。在选择图的存储方式时，需要根据具体的场景进行选择。如果图为稠密图，可以选择邻接矩阵；如果图为稀疏图，可以选择邻接表；如果图为有向图或无向图，可以选择十字链表或邻接多重表。