Graph Algorithms (BFS, DFS, Shortest Paths) using Python
Data Structures and Algorithms in Python is beginner-friendly introduction to common data structures (linked lists, stacks, queues, graphs) and algorithms (search, sorting, recursion, dynamic programming) in Python, designed to help you prepare for coding interviews and assessments.
This tutorial is an executable Jupyter notebook. Click the Open in Colab button at the top of this page to execute the code.
Jupyter Notebooks: This notebook is made of cells. Each cell can contain code written in Python or explanations in plain English. You can execute code cells and view the results instantly within the notebook. Jupyter is a powerful platform for experimentation and analysis. Don't be afraid to mess around with the code & break things - you'll learn a lot by encountering and fixing errors. You can use the "Kernel > Restart & Clear Output" menu option to clear all outputs and start again from the top.
Question: Write a function to add an edge to a graph represented as an adjacency list.
Question: Write a function to remove an edge from a graph represented as a adjacency list.
Graph Traversal
Breadth-First Search
A real-world graph:
Breadth-fist search tree (starting from Frankfurt):
Question: Implement breadth-first search given a source node in a graph using Python.
BFS pseudocode (Wikipedia):
1 procedure BFS(G, root) is
2 let Q be a queue
3 label root as discovered
4 Q.enqueue(root)
5 while Q is not empty do
6 v := Q.dequeue()
7 if v is the goal then
8 return v
9 for all edges from v to w in G.adjacentEdges(v) do
10 if w is not labeled as discovered then
11 label w as discovered
12 Q.enqueue(w)
Question: Write a program to check if all the nodes in a graph are connected
num_nodes3 = 9
edges3 = [(0, 1), (0, 3), (1, 2), (2, 3), (4, 5), (4, 6), (5, 6), (7, 8)]
num_nodes3, len(edges3)(9, 8) Depth-first search
Question: Implement depth first search from a given node in a graph using Python.
DFS pseudocode (Wikipedia):
procedure DFS_iterative(G, v) is
let S be a stack
S.push(v)
while S is not empty do
v = S.pop()
if v is not labeled as discovered then
label v as discovered
for all edges from v to w in G.adjacentEdges(v) do
S.push(w)
Question: Write a function to detect a cycle in a graph
# Graph with weights
num_nodes5 = 9
edges5 = [(0, 1, 3), (0, 3, 2), (0, 8, 4), (1, 7, 4), (2, 7, 2), (2, 3, 6),
(2, 5, 1), (3, 4, 1), (4, 8, 8), (5, 6, 8)]
num_nodes5, len(edges5)(9, 10)
num_nodes6 = 5
edges6 = [(0, 1), (1, 2), (2, 3), (2, 4), (4, 2), (3, 0)]
num_nodes6, len(edges6)(5, 6)Question: Define a class to represent weighted and directed graphs in Python.
Shortest Paths
Question: Write a function to find the length of the shortest path between two nodes in a weighted directed graph.
Dijkstra's algorithm (Wikipedia):
- Mark all nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
- Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes. Set the initial node as current.[16]
- For the current node, consider all of its unvisited neighbours and calculate their tentative distances through the current node. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 6, and the edge connecting it with a neighbour B has length 2, then the distance to B through A will be 6 + 2 = 8. If B was previously marked with a distance greater than 8 then change it to 8. Otherwise, the current value will be kept.
- When we are done considering all of the unvisited neighbours of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
- If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
- Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new "current node", and go back to step 3.
def update_distances(graph, current, distance, parent=None):
"""Update the distances of the current node's neighbors"""
neighbors = graph.data[current]
weights = graph.weight[current]
for i, node in enumerate(neighbors):
weight = weights[i]
if distance[current] + weight < distance[node]:
distance[node] = distance[current] + weight
if parent:
parent[node] = current
def pick_next_node(distance, visited):
"""Pick the next univisited node at the smallest distance"""
min_distance = float('inf')
min_node = None
for node in range(len(distance)):
if not visited[node] and distance[node] < min_distance:
min_node = node
min_distance = distance[node]
return min_node num_nodes7 = 6
edges7 = [(0, 1, 4), (0, 2, 2), (1, 2, 5), (1, 3, 10), (2, 4, 3), (4, 3, 4), (3, 5, 11)]
num_nodes7, len(edges7)(6, 7) Binary Heap
A data structure to maintain the running minimum/maximum of a set of numbers, supporting efficient addition/removal.
Heap operations:
- Insertion - $O(log N)$
- Min/Max - $O(1)$ (depending on type of heap)
- Deletion - $O(log N)$
- Convert a list to a heap - $O(n)$
Python's built-in heap: https://docs.python.org/3/library/heapq.html
Question: Implement Dijkstra's shortest path algorithm using the
heapmodule from Python. What is the complexity of the algorithm?
num_nodes1 = 5
edges1 = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 0), (1, 4), (1, 3)]
num_nodes1, len(edges1)(5, 7)num_nodes3 = 9
edges3 = [(0, 1), (0, 3), (1, 2), (2, 3), (4, 5), (4, 6), (5, 6), (7, 8)]
num_nodes3, len(edges3)(9, 8)num_nodes5 = 9
edges5 = [(0, 1, 3), (0, 3, 2), (0, 8, 4), (1, 7, 4), (2, 7, 2), (2, 3, 6),
(2, 5, 1), (3, 4, 1), (4, 8, 8), (5, 6, 8)]
num_nodes5, len(edges5)(9, 10)# Directed graph
num_nodes6 = 5
edges6 = [(0, 1), (1, 2), (2, 3), (2, 4), (4, 2), (3, 0)]
num_nodes6, len(edges6)(5, 6)num_nodes7 = 6
edges7 = [(0, 1, 4), (0, 2, 2), (1, 2, 5), (1, 3, 10), (2, 4, 3), (4, 3, 4), (3, 5, 11)]
num_nodes7, len(edges7)(6, 7)class Graph:
def __init__(self, num_nodes, edges):
self.data = [[] for _ in range(num_nodes)]
for v1, v2 in edges:
self.data[v1].append(v2)
self.data[v2].append(v1)
def __repr__(self):
return "\n".join(["{} : {}".format(i, neighbors) for (i, neighbors) in enumerate(self.data)])
def __str__(self):
return repr(self)g1 = Graph(num_nodes1, edges1)g10 : [1, 4]
1 : [0, 2, 4, 3]
2 : [1, 3]
3 : [2, 4, 1]
4 : [3, 0, 1] Breadth First Search
Complexity $O(m + n)$
def bfs(graph, source):
visited = [False] * len(graph.data)
queue = []
visited[source] = True
queue.append(source)
i = 0
while i < len(queue):
for v in graph.data[queue[i]]:
if not visited[v]:
visited[v] = True
queue.append(v)
i += 1
return queuebfs(g1, 3)[3, 2, 4, 1, 0] def dfs(graph, source):
visited = [False] * len(graph.data)
stack = [source]
result = []
while len(stack) > 0:
current = stack.pop()
if not visited[current]:
result.append(current)
visited[current] = True
for v in graph.data[current]:
stack.append(v)
return resultdfs(g1, 0)[0, 4, 1, 3, 2] class Graph:
def __init__(self, num_nodes, edges, directed=False):
self.data = [[] for _ in range(num_nodes)]
self.weight = [[] for _ in range(num_nodes)]
self.directed = directed
self.weighted = len(edges) > 0 and len(edges[0]) == 3
for e in edges:
self.data[e[0]].append(e[1])
if self.weighted:
self.weight[e[0]].append(e[2])
if not directed:
self.data[e[1]].append(e[0])
if self.weighted:
self.data[e[1]].append(e[2])
def __repr__(self):
result = ""
for i in range(len(self.data)):
pairs = list(zip(self.data[i], self.weight[i]))
result += "{}: {}\n".format(i, pairs)
return result
def __str__(self):
return repr(self)g7 = Graph(num_nodes7, edges7, directed=True)g70: [(1, 4), (2, 2)]
1: [(2, 5), (3, 10)]
2: [(4, 3)]
3: [(5, 11)]
4: [(3, 4)]
5: []g7.weight[2, 10, 3, 11, 4, []]def update_distances(graph, current, distance, parent=None):
"""Update the distances of the current node's neighbors"""
neighbors = graph.data[current]
weights = graph.weight[current]
for i, node in enumerate(neighbors):
weight = weights[i]
if distance[current] + weight < distance[node]:
distance[node] = distance[current] + weight
if parent:
parent[node] = current
def pick_next_node(distance, visited):
"""Pick the next univisited node at the smallest distance"""
min_distance = float('inf')
min_node = None
for node in range(len(distance)):
if not visited[node] and distance[node] < min_distance:
min_node = node
min_distance = distance[node]
return min_node
def shortest_path(graph, source, dest):
"""Find the length of the shortest path between source and destination"""
visited = [False] * len(graph.data)
distance = [float('inf')] * len(graph.data)
parent = [None] * len(graph.data)
queue = []
idx = 0
queue.append(source)
distance[source] = 0
visited[source] = True
while idx < len(queue) and not visited[dest]:
current = queue[idx]
update_distances(graph, current, distance, parent)
next_node = pick_next_node(distance, visited)
if next_node is not None:
visited[next_node] = True
queue.append(next_node)
idx += 1
return distance[dest], distance, parentshortest_path(g7, 0, 5)(20, [0, 4, 2, 9, 5, 20], [None, 0, 0, 4, 2, 3])