Graph
If you just need the code, here's how to build an adjacency list from a list of edges. This is the setup almost every graph problem starts with:
from collections import defaultdict
edges = [(0, 1), (1, 2), (1, 4), (3, 4)]
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # leave this out for a directed graph
print(graph[1]) # the neighbors of node 1, O(1)
print(dict(graph))The rest of this page explains what a graph is, how to store weights, and when you'd want an adjacency matrix instead.
What is a graph?
Graphs are used to represent series of relationships between a set of objects.
There are two main parts that make up a graph:
- Nodes (a.k.a Vertices) are the objects of the graph. Each node usually contains a unique value.
- Edges show how two nodes relate to each other. Edges can have different characteristics:
Unweighted vs Weighted:
An unweighted edge simply shows a connection exists between two nodes.
Example: Node A is connected to Node B.
A weighted edge shows a connection exists, and provides extra information like distance or cost of that connection.
Example: Node A is connected to Node B with a distance of 50.
Undirected (bidirected) vs Directed
An undirected edge represents a connection where you can travel in both directions.
Example: You can go from Node A to Node B, and from Node B to Node A.
A directed edge represents a connection where you can only travel in one specified direction.
Example: You can go from Node A to Node B, but NOT from Node B to Node A directly.
Examples of questions that we could use graphs to solve are:
- What's the shortest distance between two nodes in a given weighted graph?
- Is there a valid path to travel from one specific node to another specific node in a given directed graph?
- Does a certain value exist in a given graph?
Creating a graph: adjacency list or adjacency matrix
In Python, you can create a graph using an
adjacency matrix (2D array)
A matrix where each cell (i, j) indicates whether there's an edge from node i to node j.
matrix = [
[0, 1, 1],
[1, 0, 0],
[1, 0, 0],
]In this simple graph,
matrix[0][1]andmatrix[1][0]are 1, which means there's an edge between node 0 and node 1. Also,matrix[0][2]andmatrix[2][0]are 1, which means there's an edge between node 0 and node 2.adjacency list (dictionary of lists)
A dictionary where each key is a node, and the value is a list of nodes that the node is connected to.
graph = {
0: [1, 2],
}In this simple graph, there's an edge between node 0 and 1, and an edge between node 0 and 2.
Note
We recommend using adjacency lists since they're easier to understand and use. However, it's still worthwhile to familiarize yourself with adjacency matrices since some problems may provide an adjacency matrix graph to work with.
Examples of creating graphs
Unweighted Undirected Graph
Creating an unweighted undirected graph using an adjacency matrix:
num_nodes = 6 # number of nodes in the graph
edges = [(0, 1), (1, 2), (1, 4), (3, 4)]
# In one line:
# - [0] * num_nodes: Create an inner list with num_nodes elements, all set to 0.
# - [0] * num_nodes for _ in range(num_nodes): Create the inner list for num_nodes times.
# - [[0] * num_nodes for _ in range(num_nodes)]: Put the inner lists into an outer list.
# This creates a matrix of num_nodes x num_nodes where each cell has 0.
adj_matrix = [[0] * num_nodes for _ in range(num_nodes)]
# Populate the graph.
for edge in edges:
u, v = edge
adj_matrix[u][v] = 1
adj_matrix[v][u] = 1 # Only include for undirected graph
# Print the graph.
for row in adj_matrix:
print(row)
from collections import defaultdict
edges = [(0, 1), (1, 2), (1, 4), (3, 4)]
adj_list = defaultdict(list)
# Populate the graph.
for edge in edges:
u, v = edge
adj_list[u].append(v)
adj_list[v].append(u) # Only include for undirected graph
# Print the graph.
print(adj_list)
Creating an unweighted directed graph using an adjacency matrix:
num_nodes = 6 # number of nodes in the graph
edges = [(0, 1), (1, 2), (3, 4), (4, 1)] # edges are directed (from, to)
# In one line:
# - [0] * num_nodes: Create an inner list with num_nodes elements, all set to 0.
# - [0] * num_nodes for _ in range(num_nodes): Create the inner list for num_nodes times.
# - [[0] * num_nodes for _ in range(num_nodes)]: Put the inner lists into an outer list.
# This creates a matrix of num_nodes x num_nodes where each cell has 0.
adj_matrix = [[0] * num_nodes for _ in range(num_nodes)]
# Populate the graph.
for edge in edges:
u, v = edge
adj_matrix[u][v] = 1
# Print the graph.
for row in adj_matrix:
print(row)
from collections import defaultdict
edges = [(0, 1), (1, 2), (3, 4), (4, 1)] # edges are directed (from, to)
adj_list = defaultdict(list)
# Populate the graph.
for edge in edges:
u, v = edge
adj_list[u].append(v)
# Print the graph.
print(adj_list)
Creating a weighted directed graph using an adjacency matrix:
num_nodes = 6 # number of nodes in the graph
edges = {
(0, 1): 5, # 0 -> 1 (weight 5)
(1, 2): 4, # 1 -> 2 (weight 4)
(3, 4): 6, # 3 -> 4 (weight 6)
(4, 1): 2 # 4 -> 1 (weight 2)
}
# In one line:
# - [0] * num_nodes: Create an inner list with num_nodes elements, all set to 0.
# - [0] * num_nodes for _ in range(num_nodes): Create the inner list for num_nodes times.
# - [[0] * num_nodes for _ in range(num_nodes)]: Put the inner lists into an outer list.
# This creates a matrix of num_nodes x num_nodes where each cell has 0.
adj_matrix = [[0] * num_nodes for _ in range(num_nodes)]
# Populate the graph.
# edges.items() returns [((0, 1), 5), ((1, 2), 4), ...]
for edge, weight in edges.items():
u, v = edge
adj_matrix[u][v] = weight
# Print the graph.
for row in adj_matrix:
print(row)
from collections import defaultdict
edges = {
(0, 1): 5, # 0 -> 1 (weight 5)
(1, 2): 4, # 1 -> 2 (weight 4)
(3, 4): 6, # 3 -> 4 (weight 6)
(4, 1): 2 # 4 -> 1 (weight 2)
}
adj_list = defaultdict(list)
# Populate the graph.
for edge, weight in edges.items():
u, v = edge
adj_list[u].append((v, weight))
# Print the graph.
print(adj_list)
Get the neighbors of a node in an adjacency matrix
O(n)In an undirected graph, you need to traverse over either the column or row corresponding to the node.
In a directed graph, you traverse over the row (for outgoing edges) or column (for incoming edges).
# Get the neighbors of a node u in adjacency matrix.
def get_neighbors(adj_matrix, u):
neighbors = []
for v in range(len(adj_matrix)):
if adj_matrix[u][v] == 1:
neighbors.append(v)
return neighbors
adj_matrix = [
[0, 1, 0, 0, 0],
[1, 0, 1, 0, 1],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 1],
[0, 1, 0, 1, 0]
]
u = 1
print(f"The neighbors of {u} are: {get_neighbors(adj_matrix, u)}")Getting neighboring nodes in an adjacency list
O(1)The adjacency list stores all the neighbors of each key node, so we can just look up the node in the dictionary and return its value.
# Get the neighbors of a node u in adjacency list.
def get_neighbors(adj_list, u):
if u in adj_list:
return adj_list[u]
return []
adj_list = {
0: [1],
1: [0, 2, 4],
2: [1],
4: [1, 3],
3: [4]
}
u = 1
print(f"The neighbors of {u} are: {get_neighbors(adj_list, u)}")Adjacency list vs adjacency matrix
Both store the same graph. They're just fast at different things:
- Space: an adjacency list takes O(V + E), one entry per node plus one per edge. A matrix always takes O(V2), even when the graph has very few edges.
- Getting a node's neighbors: the list hands them to you directly. The matrix makes you scan a whole row, which is O(V).
- Checking one edge: the matrix wins here.
matrix[u][v]tells you in O(1) whether u connects to v. With a list, you'd searchgraph[u].
BFS and DFS spend all their time asking for neighbors, so use an adjacency list unless the problem hands you a matrix. Grid problems like Number of Islands are different: the grid already tells you each cell's neighbors (up, down, left, right), so you walk the grid directly and don't build a graph at all.