If we are assuming sparse graphs, why don't we use the adjacency list representation, where we record all neighbors of a given node?

keenan

@theyComeAndGo That is effectively what you do when you encode the adjacency matrix using a sparse matrix data structure. To make this efficient, you generally need to store both the matrix and its transpose. This is equivalent to saying that you need to store a list of edges for each vertex and vertices for each edge; likewise, a list of faces for each edge and edges for each face.

If we are assuming sparse graphs, why don't we use the adjacency list representation, where we record all neighbors of a given node?

@theyComeAndGo That is effectively what you do when you encode the adjacency matrix using a sparse matrix data structure. To make this efficient, you generally need to store both the matrix and its transpose. This is equivalent to saying that you need to store a list of edges for each vertex

andvertices for each edge; likewise, a list of faces for each edgeandedges for each face.