Introduction
From finding the shortest route on maps to detecting social network connections, graphs are incredibly versatile. Understanding graph algorithms is essential for solving many real-world problems efficiently.
This article covers fundamental graph algorithms, their implementations, and practical applications.
Graph Representations
How you represent a graph affects algorithm performance:
Adjacency List:
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
- Memory efficient for sparse graphs: O(V + E)
- Good for traversals
- Better cache for large graphs
Adjacency Matrix:
matrix = [
[0, 1, 1, 0], # A connects to B, C
[1, 0, 0, 1], # B connects to A, D
[1, 0, 0, 1], # C connects to A, D
[0, 1, 1, 0] # D connects to B, C
]
- O(1) edge lookup
- O(V²) space
- Good for dense graphs
Breadth-First Search (BFS)
Explores level by level—visit all neighbors before going deeper.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
Properties:
- Time: O(V + E)
- Space: O(V)
- Finds shortest path in unweighted graphs
- Uses queue data structure
Applications:
- Shortest path in unweighted graphs
- Level-order tree traversal
- Finding connected components
- Social network “degrees of separation”
Depth-First Search (DFS)
Explores as deep as possible before backtracking.
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in graph[start]:
if neighbor not in visited:
result.extend(dfs(graph, neighbor, visited))
return result
# Iterative version
def dfs_iterative(graph, start):
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
result.append(node)
stack.extend(reversed(graph[node]))
return result
Properties:
- Time: O(V + E)
- Space: O(V) for recursion stack
- Uses stack (or recursion)
Applications:
- Detecting cycles
- Topological sorting
- Finding strongly connected components
- Maze solving
- Path finding
Topological Sort
Linear ordering of vertices where all edges point from earlier to later.
Kahn’s Algorithm (BFS-based):
from collections import deque, defaultdict
def topological_sort(num_courses, prerequisites):
graph = defaultdict(list)
in_degree = [0] * num_courses
for dest, src in prerequisites:
graph[src].append(dest)
in_degree[dest] += 1
queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return result if len(result) == num_courses else []
Applications:
- Course scheduling
- Build systems (dependency resolution)
- Task scheduling
- Instruction ordering
Shortest Path Algorithms
Dijkstra’s Algorithm
Finds shortest path from single source to all other vertices in weighted graphs with non-negative weights.
import heapq
def dijkstra(graph, start):
dist = {vertex: float('inf') for vertex in graph}
dist[start] = 0
pq = [(0, start)]
visited = set()
while pq:
current_dist, current = heapq.heappop(pq)
if current in visited:
continue
visited.add(current)
for neighbor, weight in graph[current]:
if current_dist + weight < dist[neighbor]:
dist[neighbor] = current_dist + weight
heapq.heappush(pq, (dist[neighbor], neighbor))
return dist
Properties:
- Time: O((V + E) log V) with binary heap
- Space: O(V)
- Does NOT work with negative weights
Bellman-Ford
Handles negative weights, detects negative cycles.
def bellman_ford(num_vertices, edges, source):
dist = [float('inf')] * num_vertices
dist[source] = 0
# Relax edges V-1 times
for _ in range(num_vertices - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Check for negative cycles
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # Negative cycle detected
return dist
Minimum Spanning Tree (MST)
Connects all vertices with minimum total edge weight, no cycles.
Prim’s Algorithm
Like Dijkstra but for MST.
def prim(graph, start):
visited = {start}
edges = [(weight, start, neighbor)
for neighbor, weight in graph[start]]
heapq.heapify(edges)
total_weight = 0
while edges:
weight, u, v = heapq.heappop(edges)
if v in visited:
continue
visited.add(v)
total_weight += weight
for neighbor, w in graph[v]:
if neighbor not in visited:
heapq.heappush(edges, (w, v, neighbor))
return total_weight
Kruskal’s Algorithm
Uses Union-Find (Disjoint Set) for efficiency.
def kruskal(num_vertices, edges):
# Sort edges by weight
edges = sorted(edges, key=lambda x: x[2])
parent = list(range(num_vertices))
rank = [0] * num_vertices
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False
if rank[px] < rank[py]:
px, py = py, px
parent[py] = px
if rank[px] == rank[py]:
rank[px] += 1
return True
mst_weight = 0
edges_used = 0
for u, v, w in edges:
if union(u, v):
mst_weight += w
edges_used += 1
if edges_used == num_vertices - 1:
break
return mst_weight
Real-World Applications
- Navigation: Shortest path in road networks
- Social networks: Friend recommendations, degrees of separation
- Web page ranking: PageRank algorithm
- Package delivery: Vehicle routing problems
- Network design: Minimum cost to connect cities
External Resources
Conclusion
Graph algorithms are fundamental tools in a programmer’s toolkit. BFS and DFS provide basic traversal, while Dijkstra and MST algorithms solve optimization problems. Understanding when and how to apply these algorithms opens solutions to countless practical problems.
Comments