我正准备进行编码面试,并且在图表上让我耳目一新.我想知道以下内容:在我看过的所有地方,假设邻接列表比大型稀疏图的邻接矩阵更有内存效率,因此在这种情况下应该是首选.此外,计算来自节点的输出边缘的数量需要矩阵中的O(N),而列表中的O(1),以及列表中的O(num相邻节点)中的相邻节点而不是O(N)表示矩阵.
这些地方包括Cormen等人的书,或StackOverFlow:使用邻接列表与邻接矩阵的图的大小？或维基百科.
但是,使用与压缩行存储表示相似的稀疏矩阵表示,内存要求仅为O(非零数)= O(边数),这与使用列表相同.来自节点的输出边缘的数量是O(1)(它直接存储在CRS中),并且相邻节点可以列在O(num相邻节点)中.
为什么不讨论它？我是否应该假设CSR 是由矩阵表示的图形的一种邻接列表表示？或者是矩阵存储器密集缺陷的论点,因为它们不考虑稀疏矩阵表示？
谢谢!