You have a list of cities and the roads between them. You need to find the shortest route from one city to another. Your first instinct is to write a loop — but loops do not scale when cities can connect in dozens of different paths. That is where a graph comes in.
In this tutorial, you will learn to:
- Understand what a graph is and why it matters for real-world problems
- Represent graphs using adjacency lists and adjacency matrices in Python
- Implement Breadth-First Search (BFS) and Depth-First Search (DFS) from scratch
- Apply graph traversal to solve problems like finding the shortest path
- Avoid common pitfalls that cause graph algorithms to fail on hidden test cases
Page Contents
What Is a Graph?
A graph is a data structure made up of two components: vertices (also called nodes) and edges (connections between nodes). A social network is a graph — users are vertices and friendships are edges. Road maps are graphs — cities are vertices and roads are edges.
Before diving into graph code, make sure you are comfortable with Python lists and Python dictionaries — these are the building blocks for every graph representation you will write. The collections module in the Python standard library provides defaultdict and deque, two tools that make graph implementations much cleaner.
Prerequisites
You should know the basics of Python: lists, dictionaries, loops, and functions. If you are new to data structures, this lists tutorial is a good starting point before you continue.
Graph Types: Directed vs Undirected
Before choosing a representation, understand the two fundamental graph types:
Undirected Graphs
In an undirected graph, an edge has no direction. If vertex A connects to vertex B, you can travel from A to B and from B to A with equal ease. Think of a two-way road between cities — it does not matter which direction you drive.
# Undirected graph: edge (A, B) means A ↔ B
# If A is connected to B, B is also connected to ADirected Graphs (Digraphs)
In a directed graph, edges have direction — a one-way street, essentially. If there is an edge from A to B, you can travel from A to B, but not necessarily from B to A unless there is a separate edge for that.
# Directed graph: edge A → B means you can go from A to B
# but not necessarily from B to A (unless another edge exists)Python’s official documentation on graphs uses a directed graph example in its essay on graph algorithms — the official Python graphs essay is worth reading alongside this tutorial.
How to Represent a Graph in Python
There are two primary ways to store a graph in Python. Each has strengths and tradeoffs that affect performance depending on the graph density and the operations you run most frequently.
Adjacency List — Memory Efficient for Sparse Graphs
An adjacency list stores each vertex’s neighbors in a list or set. For a sparse graph (few edges relative to the total possible edges), this representation uses far less memory than an adjacency matrix.
from collections import defaultdict
class Graph:
"""Undirected graph using an adjacency list."""
def __init__(self):
# defaultdict(list) creates an empty list for new keys automatically
self.graph = defaultdict(list)
def add_edge(self, u, v):
"""Add an undirected edge between vertices u and v."""
self.graph[u].append(v)
self.graph[v].append(u)
def __str__(self):
lines = []
for vertex, neighbors in self.graph.items():
lines.append(f"{vertex} → {neighbors}")
return "n".join(lines)
# Build a graph of Indian cities and the roads between them
g = Graph()
g.add_edge("Mumbai", "Pune")
g.add_edge("Mumbai", "Surat")
g.add_edge("Pune", "Hyderabad")
g.add_edge("Surat", "Ahmedabad")
g.add_edge("Hyderabad", "Bangalore")
print(g)Mumbai → ['Pune', 'Surat']
Pune → ['Mumbai', 'Hyderabad']
Surat → ['Mumbai', 'Ahmedabad']
Ahmedabad → ['Surat']
Hyderabad → ['Pune', 'Bangalore']
Bangalore → ['Hyderabad']Time complexity: Adding an edge is O(1). Checking if an edge exists is O(degree of vertex). For sparse graphs, this is much faster than checking a full matrix.
Adjacency Matrix — Fast Edge Lookup, High Memory Cost
An adjacency matrix stores edge information in a 2D grid. The cell at row i, column j tells you whether an edge exists between vertex i and vertex j. This makes edge-lookup O(1), but it costs O(V²) memory regardless of how many edges the graph actually has.
class GraphMatrix:
"""Undirected graph using an adjacency matrix."""
def __init__(self, vertices):
self.V = vertices # number of vertices
# Initialize a V×V matrix with zeros
self.matrix = [[0] * vertices for _ in range(vertices)]
# Optional: map vertex names to indices
self.name_to_idx = {}
self.idx_to_name = {}
def add_vertex(self, name):
"""Assign an index to a new vertex name."""
if name not in self.name_to_idx:
idx = len(self.name_to_idx)
self.name_to_idx[name] = idx
self.idx_to_name[idx] = name
def add_edge(self, u, v):
"""Add an undirected edge between vertices u and v."""
self.add_vertex(u)
self.add_vertex(v)
i, j = self.name_to_idx[u], self.name_to_idx[v]
self.matrix[i][j] = 1
self.matrix[j][i] = 1 # symmetric for undirected graph
def display(self):
names = [self.idx_to_name[i] for i in range(self.V)]
print(" " + " ".join(f"{n[:3]:>3}" for n in names))
for i, row in enumerate(self.matrix):
print(f"{names[i][:3]:>4} " + " ".join(str(x).center(3) for x in row))
g = GraphMatrix(0)
g.add_edge("Mumbai", "Pune")
g.add_edge("Mumbai", "Surat")
g.add_edge("Pune", "Hyderabad")
g.add_edge("Surat", "Ahmedabad")
g.add_edge("Hyderabad", "Bangalore")
g.display() Mun Pun Sur Ahm Hyd Ban
Mun 0 1 1 0 0 0
Pun 1 0 0 0 1 0
Sur 1 0 0 1 0 0
Ahm 0 0 1 0 0 0
Hyd 0 1 0 0 0 1
Ban 0 0 0 0 1 0Time complexity: Edge lookup is O(1). Adding a vertex is O(V²) due to matrix resizing. Space is O(V²) regardless of edge count — impractical for graphs with millions of vertices.
Adjacency List vs Adjacency Matrix — When to Use Which
| Operation | Adjacency List | Adjacency Matrix |
|---|---|---|
| Add edge | O(1) | O(1) |
| Check if edge exists | O(degree) | O(1) |
| Iterate neighbors of a vertex | O(degree) | O(V) |
| Memory (sparse graph) | O(V + E) | O(V²) |
| Memory (dense graph) | O(V + E) | O(V²) |
Rule of thumb: Use an adjacency list for real-world sparse graphs — social networks, road maps, web graphs. Use an adjacency matrix when you need constant-time edge checks and your graph is small and dense.
Breadth-First Search (BFS) — Level by Level Exploration
Breadth-First Search explores a graph level by level. Starting from a source vertex, BFS visits all immediate neighbors first, then their neighbors, and so on. This is exactly what you need when finding the shortest path in an unweighted graph.
BFS Algorithm
- Start at the source vertex and add it to a queue.
- Mark the source as visited.
- While the queue is not empty: pop a vertex, visit all its unvisited neighbors, mark them visited, and add them to the queue.
from collections import defaultdict, deque
class Graph:
"""Undirected graph for BFS and DFS traversal."""
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def bfs(self, start):
"""Breadth-First Search from start vertex. Returns visit order."""
visited = set()
queue = deque([start])
visit_order = []
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
visit_order.append(vertex)
# Add all unvisited neighbors to the queue
for neighbor in self.graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
return visit_order
# Build a graph and run BFS
g = Graph()
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "D")
g.add_edge("D", "E")
g.add_edge("E", "F")
print("BFS from A:", g.bfs("A"))BFS from A: ['A', 'B', 'C', 'D', 'E', 'F']Why BFS finds the shortest path: BFS explores vertices in order of their distance from the source. The first time you reach a vertex, you have taken the fewest possible edges. For an unweighted graph, that shortest path is optimal.
Depth-First Search (DFS) — Exploring as Deep as Possible
Depth-First Search goes as deep as possible along each branch before backtracking. It uses a stack (or recursion) to remember where to go next. DFS is useful for detecting cycles, topological sorting, and solving puzzles like mazes.
DFS Using a Stack (Iterative)
def dfs_iterative(self, start):
"""Depth-First Search using an explicit stack."""
visited = set()
stack = [start]
visit_order = []
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
visit_order.append(vertex)
# Add neighbors in reverse order for consistent ordering
for neighbor in reversed(self.graph[vertex]):
if neighbor not in visited:
stack.append(neighbor)
return visit_order
# Run both traversals on the same graph
print("DFS (iterative):", g.dfs_iterative("A"))DFS (iterative): ['A', 'C', 'D', 'E', 'F', 'B']DFS Using Recursion
def dfs_recursive(self, start, visited=None, visit_order=None):
"""Depth-First Search using recursion."""
if visited is None:
visited = set()
if visit_order is None:
visit_order = []
visited.add(start)
visit_order.append(start)
for neighbor in self.graph[start]:
if neighbor not in visited:
self.dfs_recursive(neighbor, visited, visit_order)
return visit_order
print("DFS (recursive):", g.dfs_recursive("A"))DFS (recursive): ['A', 'B', 'D', 'E', 'F', 'C']BFS vs DFS: BFS gives shortest path in unweighted graphs. DFS is better for cycle detection, topological sort, and problems where you need to explore all paths. Use BFS when you need the nearest neighbors first; use DFS when you want to go deep before branching.
Practical Example: Shortest Path Between Cities
Here is how to use BFS to find the shortest path between two cities in a graph. This is the real-world equivalent of navigation systems finding the fastest route between two points.
def shortest_path(self, start, end):
"""Find the shortest path (as a list of vertices) from start to end."""
from collections import deque
visited = {start}
queue = deque([(start, [start])]) # (current_vertex, path_so_far)
while queue:
vertex, path = queue.popleft()
if vertex == end:
return path
for neighbor in self.graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # No path found
# Map of Indian cities
route = Graph()
route.add_edge("Mumbai", "Pune")
route.add_edge("Mumbai", "Surat")
route.add_edge("Pune", "Hyderabad")
route.add_edge("Surat", "Ahmedabad")
route.add_edge("Hyderabad", "Bangalore")
route.add_edge("Ahmedabad", "Delhi")
route.add_edge("Bangalore", "Chennai")
path = route.shortest_path("Mumbai", "Bangalore")
print("Shortest path Mumbai → Bangalore:", " → ".join(path))Shortest path Mumbai → Bangalore: Mumbai → Pune → Hyderabad → BangaloreThe algorithm found that going Mumbai → Pune → Hyderabad → Bangalore (3 hops) is shorter than Mumbai → Surat → Ahmedabad → Delhi (3 hops to Delhi, then much further to Bangalore). BFS guarantees this because it explores all paths level by level.
Common Mistakes / Gotchas
- Forgetting to mark visited vertices — causes infinite loops in graphs with cycles. Always mark a vertex as visited when you add it to the queue or stack, not when you process it.
- Using a list as a queue for BFS — popping from the front of a list is O(n). Use
collections.dequeinstead;popleft()is O(1). - Mixing up directed and undirected edges — make sure you know whether your graph is directed before you implement add_edge. One missing reverse edge can silently break your shortest path algorithm.
- Not handling disconnected vertices — BFS and DFS only explore vertices reachable from the start. If you need to visit every vertex, run the traversal from each unvisited vertex.
Summary & Next Steps
You now have a solid foundation in graph data structures. You learned how to represent graphs using adjacency lists (memory efficient for sparse graphs) and adjacency matrices (fast edge lookup), and how to implement BFS and DFS traversals that solve real problems like finding the shortest path.
Graphs are the backbone of many important algorithms you will encounter in technical interviews and real projects:
- Level Order Tree Traversal — trees are special graphs where every node is reachable from a single root
- Dynamic Programming — many DP problems on graphs use BFS-like state expansion
- Dijkstra’s Algorithm — finds shortest paths when edges have weights (unlike BFS which assumes equal weights)
Frequently Asked Questions
When should I use BFS over DFS?
Use BFS when you need the shortest path in an unweighted graph or when you want to explore all neighbors at the current distance before moving further. Use DFS when you are detecting cycles, doing topological sorting, or exploring deep paths (like solving a maze). For finding shortest paths without weights, BFS is always the correct choice.
Can a graph have multiple edges between the same two vertices?
Yes — this is called a multigraph. In a multigraph, you would use a list to store multiple edge objects between the same pair of vertices instead of a single boolean or weight. For most interview problems and real-world uses, graphs are simple (at most one edge per pair) unless stated otherwise.
How do I handle a graph with weighted edges?
BFS and DFS do not account for edge weights — they assume all edges have equal cost. For weighted graphs, use Dijkstra’s Algorithm (shortest path with non-negative weights) or the Bellman-Ford Algorithm (handles negative weights). Those algorithms build on the same adjacency list structure but use a priority queue instead of a simple queue.
What is the difference between a graph and a tree?
A tree is a special type of graph with no cycles — it is a connected graph where there is exactly one path between any two vertices. Every tree is a graph, but not every graph is a tree. Binary trees, search trees, and tries are all specialized graph structures.
What are real-world applications of graphs?
Social networks (users as vertices, friendships as edges), road navigation (cities as vertices, roads as edges), web crawling (webpages as vertices, hyperlinks as edges), recommendation systems (items and users as a bipartite graph), and network routing (routers as vertices, network links as edges) are all graph problems at scale.
