CSR与邻接表的内存开销对比

邻接列表（Adjacency List） 和 压缩稀疏行（CSR，Compressed Sparse Row） 是两种常见的图表示方法，它们的空间效率在不同情况下有所差异。具体来说，哪个表示法更节省空间，取决于图的稀疏程度和实际的存储需求。

1. 邻接列表（Adjacency List）

在邻接列表中，每个顶点有一个列表，存储与该顶点相邻的所有顶点。每个顶点的邻接列表可能包含不同数量的邻居，因此每个顶点的存储大小是变化的。

结构：

• 每个顶点存储一个列表（或者数组），该列表包含与之相邻的顶点的索引。
• 每个顶点的邻接列表的大小取决于该顶点的度（即与它相连的边的数量）。

空间复杂度：

• 总空间复杂度是 O(V + E)，其中 V 是顶点数，E 是边数。
• 每个边在图中被存储了两次（一次在起点，一次在终点），如果图是无向图，每条边会在两个顶点的邻接列表中都出现一次。

2. 压缩稀疏行（CSR，Compressed Sparse Row）

CSR 是一种将稀疏矩阵压缩存储的方式，广泛应用于图的存储，尤其是在矩阵形式表示的图（例如邻接矩阵）中。它将图的邻接信息压缩成三个数组：values、columns 和 row_ptr。

结构：

• row_ptr：一个数组，表示每个顶点的邻接列表在 columns 和 values 数组中的起始位置。它的大小为 V + 1。
• columns：一个数组，存储所有的邻接顶点的列索引（即，边的目标顶点）。
• values：一个数组，存储边的权重（如果有的话），或者如果是无权图，存储每条边的标记或简单值。

空间复杂度：

• 总空间复杂度是 O(V + E)，其中 V 是顶点数，E 是边数。
• 相比邻接列表，CSR 不会为每个顶点存储一个完整的列表，而是将所有顶点的邻接信息压缩到两个数组（columns 和 values），使用 row_ptr 数组来记录每个顶点的起始位置。

3. 比较空间效率

稀疏图：

• CSR 更节省空间：对于一个稀疏图，特别是当图的边远少于顶点数时，CSR 更能有效利用空间。因为在 CSR 中，我们将所有邻接信息都压缩到两个数组中，row_ptr 数组仅包含 V + 1 个元素，而 columns 和 values 数组只包含图中的边的信息（即 E 个元素）。因此，CSR 在存储时更紧凑。
• 邻接列表也很节省空间：在稀疏图中，邻接列表的空间开销通常也比较小，因为每个顶点的邻接列表只会存储实际的邻接顶点（即边的数量）。但对于每个顶点，都会有额外的存储空间开销，用来存储指向邻接顶点的指针或容器（如 std::vector）。

稠密图：

• CSR 可能不如邻接列表节省空间：在稠密图中（即边的数量接近顶点数的平方），图的邻接信息几乎会填满整个存储空间。此时，CSR 和邻接列表的空间差异可能不太显著，甚至邻接列表可能更简单高效，因为它能够较自然地表示每个顶点的邻接关系，而无需进行压缩。

4. 总结：

• CSR 更节省空间：在稀疏图的情况下，CSR 相比邻接列表更节省空间。因为它通过压缩存储方式（将所有的边集中在 columns 和 values 数组中）减少了存储开销，而邻接列表对于每个顶点都会分配一个单独的存储结构（如数组或列表）。
• 邻接列表在稠密图下可能更高效：如果图较为稠密，邻接列表的存储可能与 CSR 的存储开销差不多，或者邻接列表在某些实现中可能更简单。

因此，CSR 在大多数稀疏图的应用场景中更节省空间，但对于非常稠密的图或要求简单结构的场景，邻接列表 可能会更灵活且开销较小。