Python Graph Representations

Introduction

In our previous lesson, we explored the Greedy Algorithm paradigm and saw how making a series of locally optimal choices can lead to a global solution for specific problems like Activity Selection. Many powerful algorithms, including greedy ones like Dijkstra's for shortest paths, operate on a data structure called a graph. Before we can learn and implement those algorithms, we must first understand how to represent a graph in our code.

Today's lesson focuses on exactly that. Your learning outcome is to: Implement graph representations (adjacency list, adjacency matrix) in Python. We will cover the two most fundamental ways to store graph data, analyze their trade-offs, and write the Python code for each. This foundational knowledge is essential for the graph traversal and search algorithms we will cover next.

What is a Graph?

At its core, a graph is a data structure used to model relationships. It consists of two components:

• Vertices (or Nodes): These are the fundamental entities or objects within the graph. Think of them as cities on a map or people in a social network.
• Edges (or Links): These are the connections between pairs of vertices. An edge represents a relationship, like a road between two cities or a friendship between two people.

Graphs can have several properties:

• Undirected vs. Directed: In an undirected graph, edges are two-way. If A is connected to B, then B is connected to A. In a directed graph, edges are one-way, indicated by arrows. An edge from A to B doesn't imply an edge from B to A.
• Unweighted vs. Weighted: In an unweighted graph, edges simply show a connection. In a weighted graph, each edge has a numerical weight, representing a cost, distance, or capacity.

To build a strong mental model of these concepts, let's watch a short video.

Now that we have a clear idea of what a graph is, let's explore how to represent one in Python.

Graph Representations

There are two primary ways to store a graph's structure in memory: an adjacency matrix and an adjacency list. The choice between them depends on the characteristics of the graph, particularly how many edges it has.

This image provides a great overview of both representations for undirected and directed graphs. We will refer back to it as we discuss each method.

1. Adjacency Matrix

An adjacency matrix is a square grid (a 2D array or list of lists in Python) of size $V\times V$, where $V$ is the number of vertices. An entry matrix[i][j] is 1 if there is an edge from vertex i to vertex j, and 0 otherwise.

• For an undirected graph, the matrix is symmetric (matrix[i][j] == matrix[j][i]).
• For a directed graph, the matrix is not necessarily symmetric.
• For a weighted graph, instead of 1, we store the edge's weight in the matrix.

Python Implementation

Let's see how to implement this using a simple list of lists in Python.

Here is a summary of the implementation for an unweighted, undirected graph with $V$ vertices:

# Number of vertices
V = 4

# Initialize a V x V matrix with all zeros
# This creates a list of V lists, where each inner list has V zeros.
adj_matrix = [[0] * V for _ in range(V)]

# Function to add an edge between two vertices u and v
def add_edge(u, v):
    # For an undirected graph, the connection is two-way
    adj_matrix[u][v] = 1
    adj_matrix[v][u] = 1

# Add edges to represent a graph
add_edge(0, 1)
add_edge(0, 2)
add_edge(1, 2)
add_edge(2, 3)

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

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

Pros and Cons of Adjacency Matrix

• Pros: Checking if an edge exists between two vertices u and v is very fast, just an $O(1)$ lookup: adj_matrix[u][v].
• Cons: It requires $O(V^2)$ space, regardless of the number of edges. This is highly inefficient for sparse graphs—graphs with many vertices but relatively few edges. Imagine a graph of 10,000 users in a social network; a $10000\times 10000$ matrix would be enormous, even if each user only has a few friends.

This space inefficiency leads us to our next representation.

2. Adjacency List

An adjacency list is often a more space-efficient way to represent a graph. It consists of a collection of lists (or a dictionary in Python), where for each vertex, we store a list of its adjacent vertices (its "neighbors").

• In Python, this is most commonly implemented with a dictionary, where keys are the vertices and values are lists of their neighbors.
• For an undirected graph, if vertex v is in the neighbor list of u, then u must be in the neighbor list of v.
• For a directed graph, we only store outgoing edges. If there's an edge from u to v, we add v to u's neighbor list.

Python Implementation

A very common and efficient way to build an adjacency list in Python is using collections.defaultdict. It behaves like a regular dictionary, but if you try to access or modify a key that doesn't exist, it automatically creates it with a default value (e.g., an empty list).

Here is a summarized Python implementation for an unweighted, undirected graph:

from collections import defaultdict

# Create an adjacency list using defaultdict
# The default value for any new key will be an empty list
adj_list = defaultdict(list)

# Function to add an edge between two vertices u and v
def add_edge(u, v):
    # For an undirected graph, add u to v's list and v to u's list
    adj_list[u].append(v)
    adj_list[v].append(u)

# Add edges to represent the same graph as before
add_edge(0, 1)
add_edge(0, 2)
add_edge(1, 2)
add_edge(2, 3)

# Print the adjacency list
for vertex, neighbors in adj_list.items():
    print(f"Vertex {vertex}: {neighbors}")

# Expected Output (order of keys and neighbors may vary):
# Vertex 0: [1, 2]
# Vertex 1: [0, 2]
# Vertex 2: [0, 1, 3]
# Vertex 3: [2]

Pros and Cons of Adjacency List

• Pros: Very space-efficient for sparse graphs. The space complexity is $O(V+E)$, where $E$ is the number of edges. This is much better than $O(V^2)$ when $E$ is much smaller than $V^2$.
• Cons: Checking if an edge exists between u and v is slower, taking $O(k)$ time, where $k$ is the number of neighbors of u (its degree). You have to scan u's neighbor list to see if v is in it.

[
  [0, 1, 1, 0],  # 0 -> 1, 0 -> 2
  [0, 0, 1, 0],  # 1 -> 2
  [0, 0, 0, 1],  # 2 -> 3
  [0, 0, 0, 0]   # 3 has no outgoing edges
]

{
  0: [1, 2],
  1: [2],
  2: [3],
  3: []
}

Which Representation to Choose?

So, when should you use one over the other? The key factor is the density of the graph.

• A dense graph is one where the number of edges $E$ is close to the maximum possible ($E\approx V^2$). Almost every vertex is connected to every other vertex.
• A sparse graph is one where the number of edges is much smaller than the maximum ($E\approx V$).

Here's a summary of the trade-offs:

In most competitive programming and real-world scenarios (like social networks, web links, road maps), graphs are sparse. Therefore, the adjacency list is the most commonly used representation.

Conclusion

Today, you've learned the two fundamental ways to represent graphs in Python, a critical step before we can start implementing graph algorithms.

Key Takeaways:

• A graph is a collection of vertices and edges that model relationships.
• An Adjacency Matrix is a $V\times V$ grid. It's fast for checking edges ($O(1)$) but uses $O(V^2)$ space, making it suitable only for dense graphs.
• An Adjacency List uses a dictionary or array of lists to map each vertex to its neighbors. It's space-efficient for sparse graphs ($O(V+E)$) and is the most common representation.
• The choice between them is a classic space-time trade-off that depends on the graph's density.

Preview of the Next Lesson:

Now that we know how to store a graph, the next logical step is to learn how to explore it. In our next lesson, we will implement Breadth-First Search (BFS) and Depth-First Search (DFS) for graph traversal. These are two of the most important algorithms in computer science, and they will operate directly on the adjacency list representation you learned today.