图形表示 : adjacency list vs matrix

Question

我正在准备编码面试，并且正在刷新我对图表的看法。我想知道以下内容:在我所见过的所有地方，假设邻接列表比大型稀疏图的邻接矩阵的内存效率更高，因此在这种情况下应该是首选。此外，计算一个节点的出边数需要矩阵中的 O(N) 而列表中的 O(1)，以及列表中 O(num 相邻节点) 中的相邻节点而不是矩阵的 O(N)。
这些地方包括 Cormen 等人的书，或 StackOverFlow:Size of a graph using adjacency list versus adjacency matrix?或维基百科。

然而，使用像压缩行存储表示那样的稀疏矩阵表示，内存要求只是 O(非零数)= O(边数)，这与使用列表相同。一个节点的出边条数为O(1)(直接存储在CRS中)，相邻节点可以在O(num相邻节点)中列出。
为什么不讨论？我应该假设 CSR 是矩阵表示的图的一种邻接表表示吗？或者矩阵是内存密集型的论点是有缺陷的，因为它们不考虑稀疏矩阵表示？

谢谢!

Answer 1

不是每个人每天都使用稀疏矩阵表示(我只是碰巧这样做:)，所以我想没有人想到它们。它们是邻接表和邻接矩阵之间的一种中间体，如果选择正确的表示，其性能类似于第一种，并且对于某些图算法非常方便。

例如，要获得两跳的邻近矩阵，您只需 square the matrix .我已经用 Wikipedia link structure 的稀疏矩阵表示成功地做到了这一点。在适度的 CPU 时间。