When should we use each type of graph representation?


#1

Question

In the context of this exercise, when should we use each type of graph representation?

Answer

You can use any graph representation that you’d like when implementing a graph. However, there are some advantages and disadvantages of using each.

Adjacency Matrix
This is usually the easiest representation to implement. Each index is a vertex, and contains another list showing its adjacency to every other vertex. Because these implement an array of arrays, lookup time is instant when searching for edges.

These are typically more useful when there are a lot of edges in the graph. When a graph is sparse without many edges, a matrix can use up a lot of unneeded memory.

Adjacency List
Adjacency lists typically implement a data structure like a hash map or python dictionary to map the vertex (keys) to their list of adjacent vertices (values). These are slower to lookup edges than for a matrix because it must go through the entire list of edges from the start.

These are better for sparse graphs, because they only store edges that exist, in contrast to matrices which pad the missing edge values with some other value, such as False or 0.

Objects
One other representation of a graph is using objects. This can be implemented using classes like a Graph and Vertex class. This implementation is usually the most complex but allows for more functionality. You can also store more information in each vertex as they are objects.