Previous | Next --- Slide 20 of 35
Back to Lecture Thumbnails

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 and vertices for each edge; likewise, a list of faces for each edge and edges for each face.