Graph Representations: Adjacency Lists and Matrices

What is a Graph?

Before we can represent a graph, let's establish some common language. A graph consists of a set of vertices (or nodes) and a set of edges that connect pairs of vertices.

To get a quick and clear introduction to the essential terminology, please watch the beginning of the following video.

To summarize the key terms you'll encounter constantly:

• Vertex (or Node): An entity in a graph. In competitive programming problems, these are often represented by integers (from 0 to N-1) or sometimes strings.
• Edge: A connection between two vertices.
• Undirected Graph: Edges are two-way. If you can go from A to B, you can also go from B to A.
• Directed Graph (Digraph): Edges are one-way, represented with arrows. Going from A to B does not imply you can go from B to A.
• Neighbors: Two vertices are neighbors if they are connected by an edge.

How to Store a Graph in Code?

In competitive programming, you're usually given the graph structure as an edge list—a simple list of pairs representing the connections. For example: edges = [[0, 1], [1, 2], [2, 0]].

While this format is easy to read, it's not efficient for algorithms. To find all neighbors of node 1, you'd have to scan the entire list. Therefore, our first step is always to convert this edge list into a more useful structure. The two primary choices are the adjacency matrix and the adjacency list.

1. Adjacency Matrix

An adjacency matrix is a 2D array, typically of size $V\times V$ where $V$ is the number of vertices. We represent an edge between vertex i and vertex j by setting the value at matrix[i][j] to 1 (or the edge weight in a weighted graph). If there is no edge, the value is 0.

• For an undirected graph, the matrix is symmetric across its diagonal (i.e., matrix[i][j] == matrix[j][i]).
• For a directed graph, matrix[i][j] = 1 represents an edge from i to j, but this does not imply that matrix[j][i] is also 1.

Implementation

Let's see how to build an adjacency matrix from an edge list.

Here is a Python function that demonstrates the process for a directed graph:

def build_adj_matrix(n, edges):
    """
    Builds an adjacency matrix for a graph.

    Args:
        n (int): The number of vertices (labeled 0 to n-1).
        edges (list of lists): The edge list, e.g., [[u1, v1], [u2, v2]].

    Returns:
        list of lists: A n x n adjacency matrix.
    """
    # Initialize an n x n matrix with zeros
    matrix = [[0 for _ in range(n)] for _ in range(n)]

    for u, v in edges:
        # For a directed edge from u to v
        matrix[u][v] = 1
        
        # For an undirected graph, you would also add the reverse edge:
        # matrix[v][u] = 1

    return matrix

# Example: 4 vertices, directed edges
num_vertices = 4
edge_list = [[0, 1], [0, 2], [1, 2], [2, 3]]
adj_matrix = build_adj_matrix(num_vertices, edge_list)

# Print the matrix
for row in adj_matrix:
    print(row)

# Expected Output:
# [0, 1, 1, 0]
# [0, 0, 1, 0]
# [0, 0, 0, 1]
# [0, 0, 0, 0]

Pros and Cons

• Pro: Checking for an edge between two vertices u and v is extremely fast: it's an O(1) lookup (matrix[u][v]).
• Con: It requires $O(V^2)$ space, which is very inefficient for sparse graphs (graphs with many fewer edges than the maximum possible). Most graphs in competitive programming are sparse.
• Con: Finding all neighbors of a vertex requires iterating through an entire row, which takes O(V) time.

2. Adjacency List

The adjacency list is the most common representation in competitive programming. It consists of an array or dictionary where the entry for each vertex u contains a list of its neighbors.

Implementation

In Python, this is most efficiently implemented using a dictionary or a list of lists. For competitive programming, collections.defaultdict(list) is particularly powerful, as it simplifies the code for adding edges. You may recall defaultdict from our first module on Python tools.

Watch the following clip to see a practical demonstration of building an adjacency list from an edge list using defaultdict.

Here’s a summary of the implementation for a directed graph:

from collections import defaultdict

def build_adj_list(n, edges):
    """
    Builds an adjacency list for a graph using a defaultdict.

    Args:
        n (int): The number of vertices (labeled 0 to n-1).
        edges (list of lists): The edge list.

    Returns:
        defaultdict: A dictionary where keys are vertices and values are lists of neighbors.
    """
    adj_list = defaultdict(list)

    for u, v in edges:
        # For a directed edge from u to v
        adj_list[u].append(v)
        
        # For an undirected graph, you would also add the reverse edge:
        # adj_list[v].append(u)

    return adj_list

# Example: 4 vertices, directed edges
num_vertices = 4
edge_list = [[0, 1], [0, 2], [1, 2], [2, 3]]
adj_list = build_adj_list(num_vertices, edge_list)

# Print the adjacency list
for i in range(num_vertices):
    print(f"{i}: {adj_list[i]}")

# Expected Output:
# 0: [1, 2]
# 1: [2]
# 2: [3]
# 3: []

Pros and Cons

• Pro: It is space-efficient for sparse graphs. The space complexity is $O(V+E)$, where E is the number of edges.
• Pro: Iterating through all neighbors of a vertex is very efficient; it's proportional to the number of neighbors (the degree of the vertex).
• Con: Checking for a specific edge between u and v is slower than with a matrix. It takes O(degree(u)) time, as you have to scan the list of u's neighbors.

Which Representation to Choose?

For competitive programming, time and memory limits are strict. Since most problems feature sparse graphs, the adjacency list is the standard, default choice. Its efficiency in storing data and iterating through neighbors is crucial for the performance of algorithms like BFS and DFS, which we will cover next.

Conclusion

Congratulations on completing your first lesson on graphs! You've learned the fundamental prerequisite for almost every graph problem you'll encounter.

Key Takeaways:

• Graphs are represented by vertices and edges, and can be directed or undirected.
• The Adjacency Matrix uses a $V\times V$ grid. It's fast for checking edges but uses a lot of memory ($O(V^2)$), making it suitable only for dense graphs.
• The Adjacency List uses a list or dictionary to map each vertex to its neighbors. It's memory-efficient for sparse graphs ($O(V+E)$) and is the standard representation for competitive programming.
• In Python, collections.defaultdict(list) is an excellent tool for building an adjacency list from an edge list.

Up Next:
Now that we know how to store a graph, we can start exploring it. In our next lesson, we will implement our first major graph traversal algorithm: Depth-First Search (DFS). You will see how the adjacency list representation makes implementing DFS both elegant and efficient.