Donate

Learn to code — free 3,000-hour curriculum

September 3, 2025/#Python

Graph Algorithms in Python:

BFS, DFS, and Beyond
Oyedele Tioluwani
Have you ever wondered how Google Maps finds
the fastest route or how Netflix recommends
what to watch? Graph algorithms are behind
these decisions.
Graphs, made up of nodes (points) and edges (connections),
are one of the most powerful data structures in computer
science. They help model relationships efficiently, from social
networks to transportation systems.

In this guide, we will explore two core traversal techniques:

Breadth-First Search (BFS) and Depth-First Search (DFS).
Moving on from there, we will cover advanced algorithms like
Dijkstra’s, A*, Kruskal’s, Prim’s, and Bellman-Ford.

Table of Contents:
1. Understanding Graphs in Python
2. Ways to Represent Graphs in Python
3. Breadth-First Search (BFS)
4. Depth-First Search (DFS)
5. Dijkstra’s Algorithm
6. A* Search
7. Kruskal’s Algorithm
8. Prim’s Algorithm
9. Bellman-Ford Algorithm
10. Optimizing Graph Algorithms in Python
11. Key Takeaways
Understanding Graphs in Python
A graph consists of nodes (vertices) and edges
(relationships).
For examples, in a social network, people are nodes and
friendships are edges. Or in a roadmap, cities are nodes and
roads are edges.

There are a few different types of graphs:

  Directed: edges have direction (one-way streets, task
scheduling).
 Undirected: edges go both ways (mutual friendships).
 Weighted: edges have values (distances, costs).
 Unweighted: edges are equal (basic subway routes).
Now that you know what graphs are, let’s look at the
different ways they can be represented in Python.

Ways to Represent Graphs in Python

Before diving into traversal and pathfinding, it’s important to
know how graphs can be represented. Different problems call
for different representations.

Adjacency Matrix
An adjacency matrix is a 2D array where each cell (i, j) shows
whether there is an edge from node i to node j.
 In an unweighted graph, 0 means no edge,
and 1 means an edge exists.
 In a weighted graph, the cell holds the edge weight.
This makes it very quick to check if two nodes are directly
connected (constant-time lookup), but it uses more memory
for large graphs.

graph = [
[0, 1, 1],
[1, 0, 1],
[1, 1, 0]
]
Here, the matrix shows a fully connected graph of 3 nodes.
For example, graph[0][1] = 1 means there is an edge from node
0 to node 1.
Adjacency List
An adjacency list represents each node along with the list of
nodes it connects to.

This is usually more efficient for sparse graphs (where not

every node is connected to every other node). It saves
memory because only actual edges are stored instead of an
entire grid.

graph = {
'A': ['B','C'],
'B': ['A','C'],
'C': ['A','B']
}
Here, node A connects to B and C, and so on. Checking
connections takes a little longer than with a matrix, but for
large, sparse graphs, it’s the better option.
Using NetworkX
When working on real-world applications, writing your own
adjacency lists and matrices can get tedious. That’s
where NetworkX comes in, a Python library that simplifies
graph creation and analysis.
With just a few lines of code, you can build graphs, visualize
them, and run advanced algorithms without reinventing the
wheel.

import networkx as nx
import matplotlib.pyplot as plt

G = nx.Graph()
G.add_edges_from([('A','B'), ('A','C'), ('B','C')])
nx.draw(G, with_labels=True)
plt.show()
This builds a triangle-shaped graph with nodes A, B, and C.
NetworkX also lets you easily run algorithms like shortest
paths or spanning trees without manually coding them.

Now that we’ve seen different ways to represent graphs, let’s

move on to traversal methods, starting with Breadth-First
Search (BFS).

Breadth-First Search (BFS)

The basic idea behind BFS is to explore a graph one layer at
a time. It looks at all the neighbors of a starting node before
moving on to the next level. A queue is used to keep track of
what comes next.

BFS is particularly useful for:

Finding the shortest path in unweighted graphs


 Detecting connected components
 Crawling web pages
Here’s an example:

from collections import deque

def bfs(graph, start):

visited = {start}
queue = deque([start])

while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)

graph = {
'A': ['B','C'],
'B': ['A','D','E'],
'C': ['A','F'],
'D': ['B'],
'E': ['B','F'],
'F': ['C','E']
}

bfs(graph, 'A')
Here’s what’s going on in this code:
  is a dict where each node maps to a list of
graph
neighbors.
 deque is used as a FIFO queue so we visit nodes level-by-
level.
 visited keeps track of nodes we’ve already processed so
we don’t loop forever on cycles.
 In the loop, we pop a node, print it, then for each
unvisited neighbor, we mark it visited and enqueue it.
And here’s the output:

A B C D E F
Now that we have seen how BFS works, let’s turn to its
counterpart: Depth-First Search (DFS).

Depth-First Search (DFS)

DFS works differently from BFS. Instead of moving level by
level, it follows one path as far as it can go before
backtracking. Think of it as diving deep down a trail, then
returning to explore the others.

We can implement DFS in two ways:

 Recursive DFS, which uses the function call stack

 Iterative DFS, which uses an explicit stack
DFS is especially useful for:

Cycle detection
 Maze solving and puzzles
 Topological sorting
Here’s an example of recursive DFS:

def dfs_recursive(graph, node, visited=None):

if visited is None:
visited = set()
if node not in visited:
print(node, end=" ")
visited.add(node)
for neighbor in graph[node]:
 dfs_recursive(graph, neighbor, visited)

graph = {
'A': ['B','C'],
'B': ['A','D','E'],
'C': ['A','F'],
'D': ['B'],
'E': ['B','F'],
'F': ['C','E']
}

dfs_recursive(graph, 'A')
 is a set that tracks nodes already processed so
visited
you don’t loop forever on cycles.
 On each call, if node hasn’t been seen, it’s printed,
marked visited, then the function recurses into each
neighbor.
Traversal order:

A B D E F C
Explanation: DFS visits B after A, goes deeper into D, then
backtracks to explore E and F, and finally visits C.

And here’s an example of iterative DFS:

def dfs_iterative(graph, start):

visited = set()
stack = [start]

while stack:
node = stack.pop()
if node not in visited:
print(node, end=" ")
visited.add(node)
stack.extend(reversed(graph[node]))

dfs_iterative(graph, 'A')
  tracks nodes you’ve already processed so you
visited
don’t loop on cycles.
 stack is LIFO (last in, first out) – you pop() the top node,
process it, then push its neighbors.
 reversed(graph[node]) pushes neighbors in reverse so
they’re visited in the original left-to-right order
(mimicking the usual recursive DFS).
Here’s the output:

A B D E F C
With BFS and DFS explained, we can now move on to
algorithms that solve more complex problems, starting with
Dijkstra’s shortest path algorithm.

Dijkstra’s Algorithm
Dijkstra’s algorithm is built on a simple rule: always visit the
node with the smallest known distance first. By repeating
this, it uncovers the shortest path from a starting node to all
others in a weighted graph that doesn’t have negative edges.

import heapq

def dijkstra(graph, start):

heap = [(0, start)]
shortest_path = {node: float('inf') for node in graph}
shortest_path[start] = 0

while heap:
cost, node = heapq.heappop(heap)
for neighbor, weight in graph[node]:
new_cost = cost + weight
if new_cost < shortest_path[neighbor]:
shortest_path[neighbor] = new_cost
heapq.heappush(heap, (new_cost, neighbor))
return shortest_path

graph = {
'A': [('B',1), ('C',4)],
 'B': [('A',1), ('C',2), ('D',5)],
'C': [('A',4), ('B',2), ('D',1)],
'D': [('B',5), ('C',1)]
}

print(dijkstra(graph, 'A'))
Here’s what’s going on in this code:

 is an adjacency list: each node maps to a list

graph
of (neighbor, weight) pairs.
 shortest_path stores the current best-known distance to
each node (∞ initially, 0 for start).
 heap (priority queue) holds frontier nodes as (cost, node),
always popping the smallest cost first.
 For each popped node, it relaxes its edges: for
each (neighbor, weight), compute new_cost.
If new_cost beats shortest_path[neighbor], update it and push
the neighbor with that cost.
And here’s the output:

{'A': 0, 'B': 1, 'C': 3, 'D': 4}

Moving on, let’s look at an extension of this algorithm: A
Search.*
A* Search
A* works like Dijkstra’s but adds a heuristic function that
estimates how close a node is to the goal. This makes it more
efficient by guiding the search in the right direction.

import heapq

def heuristic(node, goal):

heuristics = {'A': 4, 'B': 2, 'C': 1, 'D': 0}
return heuristics.get(node, 0)

def a_star(graph, start, goal):

g_costs = {node: float('inf') for node in graph}
g_costs[start] = 0
 came_from = {}

heap = [(heuristic(start, goal), start)]

while heap:
f, node = heapq.heappop(heap)

if f > g_costs[node] + heuristic(node, goal):

continue

if node == goal:
path = [node]
while node in came_from:
node = came_from[node]
path.append(node)
return path[::-1], g_costs[path[0]]

for neighbor, weight in graph[node]:

new_g = g_costs[node] + weight
if new_g < g_costs[neighbor]:
g_costs[neighbor] = new_g
came_from[neighbor] = node
heapq.heappush(heap, (new_g + heuristic(neighbor, goal),
neighbor))

return None, float('inf')

graph = {
'A': [('B',1), ('C',4)],
'B': [('A',1), ('C',2), ('D',5)],
'C': [('A',4), ('B',2), ('D',1)],
'D': []
}

print(a_star(graph, 'A', 'D'))

This one’s a little more complex, so here’s what’s going on:
  graph:
adjacency list – each node maps to [(neighbor,
weight), ...].
 heuristic(node, goal): returns an estimate h(node) (lower is
better). It’s passed goal but in this demo uses a fixed
dict.
 g_costs: best known cost from start to each node (∞
initially, 0 for start).
 heap: min-heap of (priority, node) where priority = g + h.
 came_from: backpointers to reconstruct the path once we
pop the goal.
Then in the main loop:

We pop the node with smallest priority.

 If it’s the goal, we backtrack via came_from to build the
path and return it with g_costs[goal].
 Otherwise, we relax the edges: for each (neighbor, weight),
compute new_cost = g_costs[node] + weight.
If new_cost improves g_costs[neighbor], update it,
set came_from[neighbor] = node, and push (new_cost +
heuristic(neighbor, goal), neighbor).
Output:

(['A', 'B', 'C', 'D'], 4)

Next up, let’s move from shortest paths to spanning trees.
This is where Kruskal’s algorithm comes in.

Kruskal’s Algorithm
Kruskal’s algorithm builds a Minimum Spanning Tree (MST)
by sorting all edges from smallest to largest and adding them
one at a time, as long as they don’t create a cycle. This
makes it a greedy algorithm as it always picks the cheapest
option available at each step.

The implementation uses a Disjoint Set (Union-Find) data

structure to efficiently check whether adding an edge would
create a cycle. Each node starts in its own set, and as edges
are added, sets are merged.
class DisjointSet:
def __init__(self, nodes):
self.parent = {node: node for node in nodes}
self.rank = {node: 0 for node in nodes}
def find(self, node):
if self.parent[node] != node:
self.parent[node] = self.find(self.parent[node])
return self.parent[node]
def union(self, node1, node2):
r1, r2 = self.find(node1), self.find(node2)
if r1 != r2:
if self.rank[r1] > self.rank[r2]:
self.parent[r2] = r1
else:
self.parent[r1] = r2
if self.rank[r1] == self.rank[r2]:
self.rank[r2] += 1

def kruskal(graph):
edges = sorted(graph, key=lambda x: x[2])
mst, ds = [], DisjointSet({u for e in graph for u in e[:2]})
for u,v,w in edges:
if ds.find(u) != ds.find(v):
ds.union(u,v)
mst.append((u,v,w))
return mst

graph = [('A','B',1), ('A','C',4), ('B','C',2), ('B','D',5), ('C','D',1)]

print(kruskal(graph))
Output:

[('A','B',1), ('C','D',1), ('B','C',2)]

Here, the MST includes the smallest edges that connect all
nodes without forming cycles. Now that we have seen
Kruskal’s, we can move further to analyze another algorithm.

Prim’s Algorithm
Prim’s algorithm also finds an MST, but it grows the tree step
by step. It starts with one node and repeatedly adds the
smallest edge that connects the current tree to a new node.
Think of it as expanding a connected “island” until all nodes
are included.
This implementation uses a priority queue (heapq) to
always select the smallest available edge efficiently.
import heapq

def prim(graph, start):

mst, visited = [], {start}
edges = [(w, start, n) for n,w in graph[start]]
heapq.heapify(edges)

while edges:
w,u,v = heapq.heappop(edges)
if v not in visited:
visited.add(v)
mst.append((u,v,w))
for n,w in graph[v]:
if n not in visited:
heapq.heappush(edges, (w,v,n))
return mst

graph = {
'A':[('B',1),('C',4)],
'B':[('A',1),('C',2),('D',5)],
'C':[('A',4),('B',2),('D',1)],
'D':[('B',5),('C',1)]
}
print(prim(graph,'A'))
Output:

[('A','B',1), ('B','C',2), ('C','D',1)]

Notice how the algorithm gradually expands from node A,
always picking the lowest-weight edge that connects a new
node.
Let’s now look at an algorithm that can handle graphs with
negative edges: Bellman-Ford.
Bellman-Ford Algorithm
Bellman-Ford is a shortest path algorithm that can handle
negative edge weights, unlike Dijkstra’s. It works by relaxing
all edges repeatedly: if the current path to a node can be
improved by going through another node, it updates the
distance. After V-1 iterations (where V is the number of
vertices), all shortest paths are guaranteed to be found.
This makes it slightly slower than Dijkstra’s but more
versatile. It can also detect negative weight cycles by
checking for further improvements after the main loop.

def bellman_ford(graph, start):

dist = {node: float('inf') for node in graph}
dist[start] = 0
for _ in range(len(graph)-1):
for u in graph:
for v,w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return dist

graph = {
'A':[('B',4),('C',2)],
'B':[('C',-1),('D',2)],
'C':[('D',3)],
'D':[]
}
print(bellman_ford(graph,'A'))
Output:

{'A': 0, 'B': 4, 'C': 2, 'D': 5}

Here, the shortest path to each node is found, even though
there’s a negative edge (B → C with weight -1). If there had
been a negative cycle, Bellman-Ford would detect it by
noticing that distances keep improving after V-1 iterations.
With the main algorithms explained, let’s move on to some
practical tips for making these implementations more
efficient in Python.
Optimizing Graph Algorithms in Python
When graphs get bigger, little tweaks in how you write your
code can make a big difference. Here are a few simple but
powerful tricks to keep things running smoothly.

1. Use deque for BFS

If you use a regular Python list as a queue, popping items
from the front takes longer the bigger the list gets.
With collections.deque, you get instant (O(1)) pops from both
ends. It’s basically built for this kind of job.
from collections import deque

queue = deque([start]) # fast pops and appends

2. Go Iterative with DFS
Recursive DFS looks neat, but Python doesn’t like going too
deep – you’ll hit a recursion limit if your graph is very large.
The fix? Write DFS in an iterative style with a stack. Same
idea, no recursion errors.
def dfs_iterative(graph, start):
visited, stack = set(), [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
stack.extend(graph[node])
3. Let NetworkX Do the Heavy Lifting
For practice and learning, writing your own graph code is
great. But if you’re working on a real-world problem – say
analyzing a social network or planning routes – the NetworkX
library saves tons of time. It comes with optimized versions
of almost every common graph algorithm plus nice
visualization tools.
import networkx as nx

G = nx.Graph()
G.add_edges_from([('A','B'), ('A','C'), ('B','D'), ('C','D')])

print(nx.shortest_path(G, source='A', target='D'))

Output:
['A', 'B', 'D']
Instead of worrying about queues and stacks, you can let
NetworkX handle the details and focus on what the results
mean.

Key Takeaways
 An adjacency matrix is fast for lookups but is memory-
heavy.
 An adjacency list is space-efficient for sparse graphs.
 NetworkX makes graph analysis much easier for real-
world projects.
 BFS explores layer by layer, DFS explores deeply before
backtracking.
 Dijkstra’s and A* handle shortest paths.
 Kruskal’s and Prim’s build spanning trees.
 Bellman-Ford works with negative weights.
Conclusion
Graphs are everywhere, from maps to social networks, and
the algorithms you have seen here are the building blocks for
working with them. Whether it is finding paths, building
spanning trees, or handling tricky weights, these tools open
up a wide range of problems you can solve.

Keep experimenting and try out libraries like NetworkX when

you are ready to take on bigger projects.
Python developer Studying Mechanical Engineering Machine
Learning enthusiast

If this article was helpful, share it.

Learn to code for free. freeCodeCamp's open source
curriculum has helped more than 40,000 people get jobs as
developers. Get started

freeCodeCamp is a donor-supported tax-exempt 501(c)(3) charity

organization (United States Federal Tax Identification Number: 82-
0779546)

Our mission: to help people learn to code for free. We accomplish this by
creating thousands of videos, articles, and interactive coding lessons - all
freely available to the public.

Donations to freeCodeCamp go toward our education initiatives, and help

pay for servers, services, and staff.

You can make a tax-deductible donation here.

Trending Books and Handbooks

 REST APIs
 Clean Code
 TypeScript
 JavaScript
 AI Chatbots
 Command Line
 GraphQL APIs
 CSS Transforms
 Access Control
 REST API Design
 PHP
 Java
  Linux
 React
 CI/CD
 Docker
 Golang
 Python
 Node.js
 Todo APIs
 JavaScript Classes
 Front-End Libraries
 Express and Node.js
 Python Code Examples
 Clustering in Python
 Software Architecture
 Programming Fundamentals
 Coding Career Preparation
 Full-Stack Developer Guide
 Python for JavaScript Devs

Mobile App

Our Charity
Publication powered by HashnodeAboutAlumni NetworkOpen
SourceShopSupportSponsorsAcademic HonestyCode of ConductPrivacy PolicyTerms
of ServiceCopyright Policy