• 本文目录导读：
• 1、邻接矩阵
• 2、邻接表
• 3、十字链表

在计算机科学中，图是一种非常重要的数据结构，在许多领域都有广泛应用。图可以用来表示各种关系，例如社交网络、道路网络、电子电路等等。因此，对于图论算法的研究和应用具有重要意义。

在C语言中，实现图论算法需要选择合适的数据结构来储存一个给定的图。本文将介绍几种常见的图储存方式，并比较它们之间的优缺点。

邻接矩阵

邻接矩阵是一种基于二维数组实现的储存方式。对于一个n个节点（或顶点）m条边（或弧） 的无向/有向 图而言, 它可以被表示为一个 n * n 的二维数组 a[n][n] ，其中 a[i][j] 表示节点i和j之间是否存在连通关系。

使用邻接矩阵进行操作时，我们可以轻易地查询两个节点之间是否存在连通路径，并且获取两点之间权值最小/最大路径长度等信息。同时也能够高效地插入新节点以及增加新边。

然而，如果原始数据集包含大量的节点和边，邻接矩阵的空间复杂度会非常高，达到O(n^2)。此外，对于稀疏图来说，在储存过程中大量冗余数据会造成空间浪费。

邻接表

与邻接矩阵不同，邻接表使用链表来储存图中每个节点所连接的其他节点。具体地说，我们可以用一个数组a[i]表示第i个节点所连接的所有其他节点。

使用邻接表时，我们能够轻易地查询一个给定节点所连向的所有其他点，并且在插入新边或删除已有边时效率也非常高。此外，在处理稀疏图时相比于邻接矩阵更为节省空间。

然而，在某些情况下操作起来可能不如直观性强、难以获取两点之间权值最小路径等信息。

十字链表

十字链表是一种针对有向图设计的储存方式。它将每个顶点拆分成两部分：出度（outdegree）和入度（indegree）。同时针对每条有向边，则可以用两个指针next_out和next_in表示其起始和终止顶点。

使用十字链表时能够快速查询某个顶点出发/到达所有其他顶点，并且能够高效地删除已有边或插入新边。但是，对于无向图和稠密图的处理可能不如邻接矩阵或邻接表高效。

以上是三种常见的图储存方式，它们各有优缺点。在具体应用中应根据实际需求选择最为适合的一种方式来储存和处理数据集。