I am studying the MIT introduction to algorithms (6.006) course and I could not understand the space complexity of representing a graph in the Adjacency matrix and Adjacency list.
I have copied the following text from recitation 13 notes:
- Adjacency lists uses one node per edge, and two machine words per node. So space is (Ew) bits (w=wordsize).
- Adjacency matrix uses V^2 entries, but each entry can be just one
bit. So space can be (V^2)bits.
I understand that an adjacency list uses a table of size V in which the vertices are the indices of the table (often implemented as a hash table) and each entry has a pointer to a linked list of neighbor vertices. But I could not understand the space complexity of the above-mentioned ways for graph representation in terms of bits and word size.