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

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

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

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

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

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

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.

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

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

They ask	What they’re checking	The answer
“BFS or DFS here?”	Judgement	Shortest path in an unweighted graph or per-level output → BFS. Reachability, components, cycles, or anything about a node’s descendants → DFS. If either works, DFS is usually shorter and uses $O(h)$ rather than $O(w)$ space
“Why does Dijkstra need non-negative weights?”	The precondition	Because it finalises a node the moment it is popped, on the assumption that nothing cheaper can arrive later. A negative edge breaks that and nothing revisits the node
“Kruskal or Prim?”	Structural difference	Kruskal sorts all edges and unions with DSU — better on sparse graphs and trivially parallel to reason about. Prim grows one tree with a heap — better on dense graphs. Both $O(E \log E)$ in practice
“How does Kahn’s detect a cycle?”	Reading its output	If fewer than `n` nodes are emitted, the remainder never reached in-degree 0 — they are on a cycle or downstream of one. `len(order) != n` is the entire test, and the partial order names the healthy prefix
“All weights are 1. Still Dijkstra?”	Not over-reaching	No — BFS is $O(V+E)$ with no heap. Weights of exactly 0 and 1 want a deque. The heap only earns its log factor for arbitrary weights
“Detect a negative cycle”	Bellman-Ford’s extra round	Run $V-1$ relaxation rounds, then one more: if anything still improves, a negative cycle is reachable from the source
“The graph is a DAG and you want the longest path”	Why DAGs are special	Relax along edges in topological order — every predecessor is final before it is used, so longest-path becomes $O(V+E)$ despite being NP-hard in general
” $10^5$ nodes, recursive DFS”	Python awareness	It dies at the frame limit. Convert to the explicit-stack form, and say so before being asked

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.

32 problems

1 easy26 medium5 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

Unsolved onlyImport

112Path SumeasyLeetCode Top Interview 150
200Number of IslandsmediumNeetCode 150Blind 75LeetCode Top Interview 150amazongooglemetamicrosoftbytedance
102Binary Tree Level Order TraversalmediumNeetCode 150Blind 75LeetCode Top Interview 150amazonmetamicrosoftbytedance
207Course SchedulemediumNeetCode 150Blind 75LeetCode Top Interview 150googleamazonmetabytedance
133Clone GraphmediumNeetCode 150Blind 75LeetCode Top Interview 150metagoogleamazon
743Network Delay TimemediumNeetCode 150googleuberamazon
787Cheapest Flights Within K StopsmediumNeetCode 150googleuberamazon
994Rotting OrangesmediumNeetCode 150amazonmicrosoftbytedance
1584Min Cost to Connect All PointsmediumNeetCode 150amazonuber
128Longest Consecutive SequencemediumNeetCode 150Blind 75LeetCode Top Interview 150
210Course Schedule IImediumNeetCode 150LeetCode Top Interview 150
261Graph Valid TreepremiummediumNeetCode 150Blind 75
310Minimum Height Treesmedium
399Evaluate DivisionmediumLeetCode Top Interview 150
433Minimum Genetic MutationmediumLeetCode Top Interview 150
547Number of Provincesmedium
684Redundant ConnectionmediumNeetCode 150
695Max Area of IslandmediumNeetCode 150
721Accounts Mergemedium
909Snakes and LaddersmediumLeetCode Top Interview 150
990Satisfiability of Equality Equationsmedium
1091Shortest Path in Binary Matrixmedium
1135Connecting Cities With Minimum Costpremiummedium
1136Parallel Coursespremiummedium
1319Number of Operations to Make Network Connectedmedium
1334Find the City With the Smallest Number of Neighbors at a Threshold Distancemedium
1631Path With Minimum Effortmedium
127Word LadderhardNeetCode 150LeetCode Top Interview 150amazongooglebytedance
269Alien DictionarypremiumhardNeetCode 150Blind 75googlemetaamazon
778Swim in Rising WaterhardNeetCode 150
1168Optimize Water Distribution in a Villagepremiumhard
1293Shortest Path in a Grid with Obstacles Eliminationhard

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.

pch.coffeeTagline

pch.coffeeCta

pch.feedbackHeading

pch.feedbackSubheading