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)$.

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.

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)$.

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)$.

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)$.

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) != n for a cycle. $O(V + E)$.

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

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.

Press Run to see what your code prints.

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

Press Run to see what your code prints.

Kahn's algorithm — topological order, or [] if a cycle exists

Press Run to see what your code prints.

Pitfalls

• Marking a node visited on dequeue instead of enqueue in BFS. A node discovered by several neighbours is then pushed several times before being processed — duplicated output and a queue that grows toward $O(E)$. Mark when you push.
• Enqueueing a neighbour in Kahn's on first sight. It must wait until its in-degree reaches 0, otherwise a node with two prerequisites is emitted before one of them.
• Reading Dijkstra's stale heap entries as a bug. heapq has no decrease-key, so an improvement pushes a second entry; if d > dist[node]: continue discards the obsolete one. That guard is required, not optional.
• Running Dijkstra with a negative edge. It finalises a node on pop, so a negative edge found later cannot fix it — a confidently wrong answer. Negative weights are Bellman-Ford.
• Using a visited set in 0-1 BFS. A 0-weight edge can improve a node after it has been popped, so the correct guard is dist[v] + w < dist[u].
• Applying the directed cycle-detection method to an undirected graph. Every edge appears in both adjacency lists, so each one looks like a 2-cycle. Undirected needs the parent passed down; directed needs three colours.
• Prim's without a visited check on pop. The heap holds stale entries just as Dijkstra's does, and re-adding a node already in the tree inflates the MST weight.
• Recursive DFS on a $10^5$-node graph. CPython's ~1000-frame limit. Use the iterative form in these templates, or raise the limit deliberately.

Interview follow-ups

LeetCode problem set

One ladder across all six graph templates. Sorting these by which template they need is a faster exercise than solving them, and it is the skill the interview actually tests.

Recall card

• BFS — deque, popleft, mark visited on enqueue. Shortest path when every edge costs the same. $O(V+E)$.
• DFS — stack or recursion; the same loop with pop() instead of popleft(). Reachability, components, cycles. $O(V+E)$, $O(h)$ stack.
• Dijkstra — heap of (dist, node); skip stale pops with if d > dist[node]: continue. Non-negative weights only. $O(E \log V)$.
• Bellman-Ford — $V-1$ rounds over all edges; one extra round detects a negative cycle. $O(VE)$.
• Prim — grow one tree with a heap, skipping nodes already in it. Kruskal — sort edges, union with DSU, take an edge when union returns True. Both $O(E \log E)$.
• Kahn's — in-degree counts, seed the queue with zeros, enqueue a neighbour only when its degree hits 0. len(order) != n means a cycle.
• Weights decide the tool — equal → BFS; 0/1 → deque; non-negative → Dijkstra; negative → Bellman-Ford; DAG → relax in topological order.
• Iterative by default. Every template here avoids recursion because a $10^5$-node line is a legal input.

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.