Adjacency List Representation in C++

The Concept of an Adjacency List

The core idea behind an adjacency list is to store only the information that actually exists. Instead of a massive $V\times V$ matrix where most entries might be zero, we maintain an array (or a vector in C++) of lists. Each index i in this array corresponds to vertex i, and the list at that index contains only the vertices that are direct neighbors of i.

This is far more space-efficient. If a vertex has only three neighbors, we store just those three, not an entire row of V elements.

Let's visualize this. The image below shows a simple undirected graph and its corresponding adjacency list. For each vertex (0, 1, 2), there is a linked list containing its neighbors. In a C++ context, we typically use a std::vector instead of a linked list for better performance and ease of use.

For a directed graph, the representation is similar, but the relationships are one-way. An edge from A to B means B will be in A's list, but A will not necessarily be in B's list.

Implementation in C++

In C++, the most common way to implement an adjacency list is with a vector of vectors: vector<vector<int>> adj;. This creates a dynamic array where adj[i] is itself a vector that will store the neighbors of vertex i.

The take U forward video provides an excellent walkthrough of this concept, tailored specifically for the context of competitive programming.

As explained in the video, for a standard problem input with $N$ vertices and $M$ edges, we would implement it as follows:

1. Initialize the main vector: vector<vector<int>> adj(N); (or N+1 for 1-based indexing).
2. Loop $M$ times to read each edge.
3. For each edge (u, v):
   • If the graph is directed, add v to u's list: adj[u].push_back(v);.
   • If the graph is undirected, add the connection in both directions: adj[u].push_back(v); and adj[v].push_back(u);.

For a clean, written summary and code snippet, the following resource is very helpful.

Representing Weighted Graphs

Just as with adjacency matrices, we can adapt adjacency lists to handle weighted graphs. Instead of storing just the integer ID of a neighbor, we need to store a pair of values: the neighbor's ID and the weight of the edge connecting to it.

In C++, std::pair<int, int> is perfect for this. Our data structure becomes vector<vector<pair<int, int>>> adj;. Now, adj[u] will be a list of pairs, where each pair is of the form {neighbor, weight}.

The take U forward video explains this extension clearly.

The process of building the list is almost identical. When you read an edge (u, v) with weight w, you simply push a pair instead of an integer.

• For a directed edge: adj[u].push_back({v, w});
• For an undirected edge: adj[u].push_back({v, w}); and adj[v].push_back({u, w});

This is also covered in the article we looked at earlier.

An Advanced Aside: Map-based Adjacency Lists

In most contest problems, vertices are conveniently numbered from 0 or 1 up to $N-1$. This makes them perfect indices for a vector. However, what if the vertex labels were large, non-sequential numbers (e.g., user IDs) or even strings? In such cases, a vector is not a suitable primary container.

Here, you can leverage your knowledge of hash maps. The C++ std::unordered_map can be used to create a map-based adjacency list: unordered_map<int, vector<int>> adj;. The key of the map is the vertex label, and the value is the list of its neighbors. This provides flexibility when dealing with unconventional vertex labeling. The Graph Input Methods article briefly touches on this under "Method 5".

Conclusion

Today, you've learned how to implement the adjacency list, the workhorse of graph representation in competitive programming. Its efficiency with sparse graphs makes it an essential tool in your arsenal.

Key Takeaways:

• An adjacency list represents a graph as an array of lists, where adj[i] stores only the direct neighbors of vertex i.
• It is most commonly implemented in C++ using vector<vector<int>> for unweighted graphs and vector<vector<pair<int, int>>> for weighted graphs.
• The primary advantage is its space efficiency. The space complexity is $O(V+E)$, which is a significant improvement over the adjacency matrix's $O(V^2)$ for sparse graphs (where $E\ll V^2$).
• The adjacency list is optimal for iterating through a vertex's neighbors, which is a fundamental operation in most graph algorithms. This takes $O(\text{degree}(v))$ time.
• The main trade-off is that checking for a specific edge (u, v) is slower than with an adjacency matrix, requiring a linear scan of u's neighbor list, taking $O(\text{degree}(u))$ time.

In our next lesson, we will formalize the comparison between the adjacency matrix and the adjacency list. We'll create a clear summary of their respective time and space complexities for different operations, helping you solidify your understanding of when to choose one over the other.