Welcome to Programming and Data Structures

An adjacency list is a collection of lists, where for each vertex in the graph there is a list that contains the neighbors of that vertex. In an unweighted graph, we can simply store the neighbors as a list. If we want to support weighted graphs, we can store the neighbors as a list of pairs, where each pair contains a neighbor and the weight of the edge to that neighbor.

The top level of this structure maps a vertex to a list. We can do this indirectly by first assigning an integer index to each vertex and then using an array to map from the vertex index to the list of neighbors. Or we could use a hash table to directly map from the vertex to the list of neighbors. The later choice might define the graph’s data using something like:

class Graph {
public:
    ...
private:
    unordered_map<T, list<pair<T, int>>> adjacencyList;
};

The code above uses a list to store the neighbors of each vertex (represented as a pair<T, int> of the neighbor vertex and the weight of the edge to that neighbor), but we could use a vector instead. A list is a nice choice in that it requires a minimal amount of memory to store an empty list of neighbors. And it is rare that we need to ask “what is the 3rd neighbor of vertex X?”, so we don’t need the random access that a vector provides.

Using a list would mean that the logic for hasEdge(T source, T destination) will need to iterate through the list of neighbors for the source vertex to check if the destination vertex is in that list. To check hasEdge("MTH111", "CS162"), for example, we would have to access the list of neighbors for "MTH111" and iterate through that list to see if "CS162" is in it. That would mean that the time complexity of hasEdge would be O(n) where \(n\) is the number of neighbors of the source vertex.

To make that process more efficient, in a graph where vertices have many edges (and thus many neighbors), we could use another unordered map to store the neighbors of each vertex. Thus looking up the record for "MTH111" would give us a unordered_map<string, int> that contains the mappings: { "MTH112": 1, "CS161": 1 }. In the Graph class, it would

class Graph {
public:
    ...
private:
    unordered_map<T, unordered_map<T, int>> adjacencyList;
};

This approach is known as an adjacency map representation of a graph and would allow us to check if an edge exists in O(1) time by looking up the source vertex in the top level map and then looking up the destination vertex in the second level map. However, it would use more memory than the list-based approach, especially for vertices with few neighbors.

Both the list-based and map-based adjacency list representations require space proportional to the number of vertices plus the number of edges in the graph, or \(O(V + E)\text{,}\) which is more efficient than the \(O(V^2)\) space requirement of the adjacency matrix representation for sparse graphs. They have to store a record for each vector and each edge, but they don’t have to allocate space for every possible edge like the adjacency matrix representation does. There is likely to be less memory overhead in the list-based approach (for storing next pointers) than the map-based approach (for spae space in the hash table), especially for vertices with few neighbors.

They also have the advantage that it is much easier to add or remove a vertex from the graph. To add a vertex, we can simply add a new entry to the top level map with an empty list or map of neighbors. (In the adjacency matrix representation, we would need to create a new matrix with an additional row and column for the new vertex and copy over the existing data.) Removing a vertex is more complicated as we have to not only remove the vertex from the top level map, but also remove any edges to that vertex from the neighbor lists of other vertices. But it is still more efficient than the adjacency matrix representation, where we would need to create a new matrix with one fewer row and column and copy over the existing data.