Adjacency Lists for Graph Traversal

Welcome to our new module on graph algorithms. In the previous module, we explored the Union-Find data structure, culminating in its application to a complex merging problem. We saw how grouping disparate elements into connected components is a powerful technique. Now, we will build on this idea of "connections" by diving into the world of graphs, a fundamental structure for modeling networks and relationships.

This lesson kicks off our journey by tackling a crucial first step: representing graphs in code. Our learning outcome is to represent a graph using an adjacency list for traversal algorithms. Before we can run any algorithm like finding the shortest path or detecting cycles, we must have an efficient way to store the graph's structure in memory. The choice of representation has a profound impact on an algorithm's performance, and for the kind of problems you'll face in coding interviews, making the right choice is paramount.

What is a Graph? A Quick Refresher

At its core, a graph is a simple and powerful concept: it's a collection of nodes (or vertices) connected by edges. You've already encountered specialized forms of graphs, like linked lists and trees. Now, we'll deal with their most general form, which allows for complex connections, including cycles.

To prepare for the different scenarios you might encounter, it's useful to formally review the basic terminology and types of graphs.

In most coding challenges, a graph is not given to you as a pre-built object. Instead, you'll typically receive the number of nodes (n) and a list of edges, which is simply a list of pairs of nodes that are connected. Our first job is to convert this raw input into a more useful structure.

Storing a Graph: Adjacency Matrix vs. Adjacency List

There are two primary ways to represent a graph in memory: the adjacency matrix and the adjacency list. Understanding the trade-offs between them is crucial for any programmer.

1. Adjacency Matrix: This is a V x V matrix (where V is the number of vertices), where matrix[i][j] = 1 signifies an edge from vertex i to j. For weighted graphs, the entry would be the edge's weight instead of 1.
2. Adjacency List: This is an array or hash map where each index or key i corresponds to a vertex, and it stores a list of all vertices adjacent to i (i.e., its neighbors).

The following article provides a clear, detailed comparison of these two approaches.

As you read, pay close attention to the terms sparse and dense. A graph is sparse if it has relatively few edges (E is close to V), and dense if it has many edges (E is close to V²). Most graphs modeling real-world problems—social networks, road maps, dependencies—are sparse.

This is why the adjacency list is the de facto standard for competitive programming and interviews. Its O(V + E) space usage is far more efficient than the O(V²) required by an adjacency matrix for sparse graphs. Furthermore, traversal algorithms need to iterate over the neighbors of a node, an operation that is much faster with an adjacency list.

Let's look at a visual representation. The image below shows a simple weighted, undirected graph and how it is stored using both methods.

A weighted undirected graph represented as both an adjacency list and an adjacency matrix. Notice how the adjacency list for node 'C' directly lists its neighbors (A, B, D, F) and the corresponding edge weights, while the matrix requires a full row.

The conceptual model for an adjacency list is often an array where each element points to a linked list of its neighbors.

This drawing illustrates the core idea of an adjacency list: an array of vertices, where each entry points to a list containing its neighbors.

Practical Implementation: Building an Adjacency List

Now let's turn theory into practice. Your most common task will be to construct an adjacency list from an edge list. In Python, the most idiomatic and efficient way to do this is with a hash map (a dict), where keys are the node identifiers and values are lists of their neighbors.

This short guide from Hello Interview provides a direct and practical code example.

While the approach of pre-initializing a dictionary with empty lists for all nodes works perfectly, Python's collections module offers an even more convenient tool: defaultdict. A defaultdict(list) automatically creates an empty list for a key the first time it is accessed, simplifying the code.

Greg Hogg's video demonstrates this exact technique.

Here is a complete, commented Python function that encapsulates this pattern for building an adjacency list for an unweighted, undirected graph:

from collections import defaultdict

def build_adj_list(n, edges):
    """
    Builds an adjacency list representation of a graph.

    Args:
        n (int): The number of nodes, typically labeled 0 to n-1.
        edges (List[List[int]]): A list of edges, where each edge is a pair [u, v].

    Returns:
        defaultdict: A dictionary where keys are nodes and values are lists of their neighbors.
    """
    adj = defaultdict(list)
    
    # For an undirected graph, each edge [u, v] implies two connections:
    # u is a neighbor of v, and v is a neighbor of u.
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
        
    return adj

# Example usage:
num_nodes = 5
edge_list = [[0, 1], [0, 2], [1, 3], [1, 4]]
graph = build_adj_list(num_nodes, edge_list)

# The resulting adjacency list will be:
# {
#   0: [1, 2],
#   1: [0, 3, 4],
#   2: [0],
#   3: [1],
#   4: [1]
# }
# Note: Nodes without edges won't appear as keys, but defaultdict handles this gracefully.

For a directed graph, you would simply omit the second append: adj[u].append(v). For a weighted graph, you would append tuples or pairs: adj[u].append((v, weight)). With this structure in place, you are perfectly set up to run traversal algorithms like Breadth-First Search (BFS) or Depth-First Search (DFS).

Conclusion

In this lesson, we established the foundational skill for tackling graph problems: representing them in code. We analyzed the trade-offs between adjacency matrices and adjacency lists and concluded that the latter is superior for the sparse graphs common in algorithmic challenges.

Key Takeaways:

• A graph is a set of vertices connected by edges. They can be directed or undirected, weighted or unweighted.
• The adjacency matrix uses O(V²) space, making it inefficient for sparse graphs, but offers O(1) edge existence checks.
• The adjacency list is the preferred representation for most interview problems. It uses space-efficient O(V + E) memory and allows for fast iteration over a node's neighbors.
• In Python, an adjacency list is best implemented using a defaultdict(list), which simplifies the code for building the graph from an edge list.

This representation is the starting point for nearly every graph algorithm. In our next lesson, we will leverage it to implement Dijkstra's algorithm, a classic method for finding the shortest path from a single source to all other nodes in a weighted graph. You will see firsthand how the adjacency list makes finding and processing neighbors a highly efficient operation.