Graph Algorithm Templates

Another cheat sheet: six self-contained, runnable graph algorithm templates, each demoed on a tiny sample graph so a paste-and-run confirms it works before you adapt it to the real problem in front of you.

What you’ll learn

BFS — shortest path in an unweighted graph, $O(V + E)$ .
DFS — both iterative and recursive, $O(V + E)$ .
Dijkstra — shortest paths with non-negative weights, $O(E \log V)$ .
Prim — minimum spanning tree, growing one tree with a heap.
Kruskal — minimum spanning tree, sorting edges + Union-Find.
Kahn’s algorithm — topological sort via in-degree, with built-in cycle detection.

BFS — shortest path, unweighted graph

Use it whenever every edge costs the same and the question is “fewest steps” or “shortest path.” The first time BFS reaches a node is guaranteed to be the shortest route. $O(V + E)$ .

bfs_template.py

from collections import deque
 
 
def bfs_shortest_path(graph, start, target):
    visited = {start}
    queue = deque([(start, 0)])   # (node, distance so far)
 
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
 
    return -1   # target unreachable
 
 
graph = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
print("shortest 0 -> 4:", bfs_shortest_path(graph, 0, 4))   # expect 3

bfs_template.py

from collections import deque
 
 
def bfs_shortest_path(graph, start, target):
    visited = {start}
    queue = deque([(start, 0)])   # (node, distance so far)
 
    while queue:
        node, dist = queue.popleft()
        if node == target:
            return dist
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, dist + 1))
 
    return -1   # target unreachable
 
 
graph = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
print("shortest 0 -> 4:", bfs_shortest_path(graph, 0, 4))   # expect 3

DFS — iterative and recursive

Use it for “does a path exist,” connected components, or flood fill — anything about whether something is reachable rather than how far. Both versions visit the same $O(V + E)$ nodes/edges; iterative avoids Python’s recursion-depth limit on deep graphs.

dfs_template.py

def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)
    return order
 
 
def dfs_iterative(graph, start):
    visited = {start}
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    return order
 
 
graph = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
print("DFS recursive:", dfs_recursive(graph, 0))
print("DFS iterative:", dfs_iterative(graph, 0))

dfs_template.py

def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None:
        visited, order = set(), []
    visited.add(node)
    order.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)
    return order
 
 
def dfs_iterative(graph, start):
    visited = {start}
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
    return order
 
 
graph = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
print("DFS recursive:", dfs_recursive(graph, 0))
print("DFS iterative:", dfs_iterative(graph, 0))

Dijkstra — shortest paths, non-negative weights

Use it the moment edges carry different (but non-negative) weights — BFS’s “first arrival is shortest” guarantee no longer holds. A min-heap always expands the closest unfinalized node next. $O(E \log V)$ .

dijkstra_template.py

import heapq
from collections import defaultdict
 
 
def dijkstra(n, edges, source):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))   # remove this line for a DIRECTED graph
 
    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]
 
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue   # stale heap entry
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
 
    return dist
 
 
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3)]
print("distances from 0:", dijkstra(5, edges, 0))

dijkstra_template.py

import heapq
from collections import defaultdict
 
 
def dijkstra(n, edges, source):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((v, w))
        graph[v].append((u, w))   # remove this line for a DIRECTED graph
 
    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]
 
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:
            continue   # stale heap entry
        for neighbor, weight in graph[node]:
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                heapq.heappush(heap, (new_dist, neighbor))
 
    return dist
 
 
edges = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1), (2, 3, 5), (3, 4, 3)]
print("distances from 0:", dijkstra(5, edges, 0))

Prim — minimum spanning tree, grow one tree

Use it on dense graphs (or when you already have an adjacency list): start from one node and repeatedly add the cheapest edge that reaches a brand-new node. $O(E \log V)$ .

prim_template.py

import heapq
from collections import defaultdict
 
 
def prim_mst(n, weighted_edges, start=0):
    graph = defaultdict(list)
    for u, v, w in weighted_edges:
        graph[u].append((w, v))
        graph[v].append((w, u))
 
    visited = {start}
    min_heap = graph[start][:]
    heapq.heapify(min_heap)
    total_weight = 0
 
    while min_heap and len(visited) < n:
        weight, node = heapq.heappop(min_heap)
        if node in visited:
            continue
        visited.add(node)
        total_weight += weight
        for next_weight, neighbor in graph[node]:
            if neighbor not in visited:
                heapq.heappush(min_heap, (next_weight, neighbor))
 
    return total_weight
 
 
weighted_edges = [(0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 4, 7), (2, 3, 8), (3, 4, 3)]
print("MST total weight:", prim_mst(5, weighted_edges))   # expect 11

prim_template.py

import heapq
from collections import defaultdict
 
 
def prim_mst(n, weighted_edges, start=0):
    graph = defaultdict(list)
    for u, v, w in weighted_edges:
        graph[u].append((w, v))
        graph[v].append((w, u))
 
    visited = {start}
    min_heap = graph[start][:]
    heapq.heapify(min_heap)
    total_weight = 0
 
    while min_heap and len(visited) < n:
        weight, node = heapq.heappop(min_heap)
        if node in visited:
            continue
        visited.add(node)
        total_weight += weight
        for next_weight, neighbor in graph[node]:
            if neighbor not in visited:
                heapq.heappush(min_heap, (next_weight, neighbor))
 
    return total_weight
 
 
weighted_edges = [(0, 1, 4), (0, 2, 1), (1, 2, 2), (1, 3, 5), (2, 4, 7), (2, 3, 8), (3, 4, 3)]
print("MST total weight:", prim_mst(5, weighted_edges))   # expect 11

Kruskal — minimum spanning tree, sort + Union-Find

Use it on sparse graphs given as a flat edge list: sort edges cheapest-first, then add each one only if its endpoints are in different Union-Find components. $O(E \log E)$ .

kruskal_template.py

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        self.parent[ra] = rb
        return True
 
 
def kruskal_mst(n, edges):
    """edges: list of (weight, u, v)."""
    dsu = DSU(n)
    total_weight = 0
    for weight, u, v in sorted(edges):
        if dsu.union(u, v):
            total_weight += weight
    return total_weight
 
 
edges = [(4, 0, 1), (1, 0, 2), (2, 1, 2), (5, 1, 3), (7, 2, 4), (8, 2, 3), (3, 3, 4)]
print("MST total weight:", kruskal_mst(5, edges))   # expect 11

kruskal_template.py

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        self.parent[ra] = rb
        return True
 
 
def kruskal_mst(n, edges):
    """edges: list of (weight, u, v)."""
    dsu = DSU(n)
    total_weight = 0
    for weight, u, v in sorted(edges):
        if dsu.union(u, v):
            total_weight += weight
    return total_weight
 
 
edges = [(4, 0, 1), (1, 0, 2), (2, 1, 2), (5, 1, 3), (7, 2, 4), (8, 2, 3), (3, 3, 4)]
print("MST total weight:", kruskal_mst(5, edges))   # expect 11

Kahn’s algorithm — topological sort

Use it to order tasks/courses/builds by dependency, on a directed acyclic graph. A BFS driven by in-degree: process every node with no remaining prerequisites, and check len(order) != nlen(order) != n for a cycle. $O(V + E)$ .

kahns_template.py

from collections import deque, defaultdict
 
 
def topological_sort(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:            # u must come before v
        graph[u].append(v)
        in_degree[v] += 1
 
    queue = deque(node for node in range(n) if in_degree[node] == 0)
    order = []
 
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    return order if len(order) == n else None   # None means a cycle exists
 
 
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
print("topological order:", topological_sort(5, edges))
 
cyclic_edges = [(0, 1), (1, 2), (2, 0)]
print("cyclic graph result:", topological_sort(3, cyclic_edges))

kahns_template.py

from collections import deque, defaultdict
 
 
def topological_sort(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:            # u must come before v
        graph[u].append(v)
        in_degree[v] += 1
 
    queue = deque(node for node in range(n) if in_degree[node] == 0)
    order = []
 
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
 
    return order if len(order) == n else None   # None means a cycle exists
 
 
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
print("topological order:", topological_sort(5, edges))
 
cyclic_edges = [(0, 1), (1, 2), (2, 0)]
print("cyclic graph result:", topological_sort(3, cyclic_edges))

Complexity at a glance

Algorithm	Time	Use case
BFS	$O(V + E)$	Shortest path, unweighted
DFS	$O(V + E)$	Reachability, components, flood fill
Dijkstra	$O(E \log V)$	Shortest path, non-negative weights
Prim	$O(E \log V)$	MST, dense graph / adjacency list
Kruskal	$O(E \log E)$	MST, sparse graph / edge list
Kahn’s	$O(V + E)$	Topological order + cycle detection

Practice

Drill 1 — BFS visited-on-enqueue. Complete the line that marks a neighbor visited the moment it’s discovered, not when it’s processed.

Drill 2 — Dijkstra’s stale-entry skip. Complete the check that skips a heap entry whose distance is already beaten.

Recap

BFS/DFS cover unweighted reachability and shortest paths in $O(V + E)$ ; pick BFS for “how far,” DFS for “does it exist.”
Dijkstra extends shortest paths to non-negative weights in $O(E \log V)$ via a min-heap.
Prim and Kruskal both build a minimum spanning tree — Prim grows one tree with a heap (dense graphs), Kruskal sorts edges and uses Union-Find (sparse graphs).
Kahn’s algorithm topologically orders a DAG and detects cycles for free, via in-degree counts.

Back to Data Structure Templates for the DSU, segment tree, Fenwick tree, and trie cheat sheet these algorithms build on.

If this helped you, consider buying me a coffee ☕

Buy me a coffee