Presentation of graphs: adjacency versus matrix list

Question

I am preparing for a coding interview and updating my view on the charts. I was interested in the following: in all places that I saw, it is assumed that adjacency lists are more memory efficient than adjacency matrices for large sparse graphs, and therefore should be preferred in this case. In addition, calculating the number of outgoing edges from a node requires O (N) in the matrix, while O (1) in the list, and also which are neighboring nodes in O (several neighboring nodes) for the list instead of O (N) for the matrix.
Such places include Cormen et al. book or StackOverFlow: Chart size using adjacency list versus adjacency matrix? or Wikipedia.

However, using a sparse matrix representation similar to the representation of a compressed series, the memory requirement is only in O (number of nonzero) = O (number of edges), which is the same as using lists. The number of outgoing edges from a node is O (1) (it is directly stored in CRS), and adjacent nodes can be listed in O (several neighboring nodes).
Why is it not being discussed? Should I assume that CSR is a kind of representation of a graph adjacency list represented by a matrix? Or is the argument that matrices are insufficient for memory because they do not take into account sparse representations of matrices?

Thanks!

Answer 1

Not every time they use sparse matrix representations (I just do it :), so, I think, no one thought about them. They are a kind of intermediate between adjacency lists and adjacency matrices, and the performance is similar to the first if you choose the correct representation and are very convenient for some graph algorithms.

For example, to get the proximity matrix for two jumps, you are just a square matrix . I have successfully done this with sparse matrix representations of the Wikipedia structure in a minimal amount of processor time.