Graph Algorithms Cheat Sheet for Interviews (with Code)

The unlock for graph problems is that almost all of them reduce to BFS or DFS over an adjacency list — the interview skill is recognizing which traversal (and which add-on) the problem wants. BFS for shortest paths in unweighted graphs and level order; DFS for connectivity, cycles, and topological sort; Union-Find for dynamic connectivity; Dijkstra for weighted shortest paths. Learn the four and the recognition cues, and "graph" stops being scary.

Representations

• Adjacency list — dict[node] -> list[neighbors]. The default for interviews (sparse, O(V+E) space).
• Adjacency matrix — V×V grid; good for dense graphs or O(1) edge lookups.
• Edge list — list of (u, v, w); handy for Union-Find / Kruskal.

Many problems hand you an implicit graph (a grid, where cells are nodes and neighbors are the 4 directions) — recognizing that is half the battle.

Core algorithms

BFS — shortest path (unweighted) & level order

from collections import deque

def bfs(adj, start):
    seen = {start}
    q = deque([(start, 0)])           # (node, distance)
    while q:
        node, dist = q.popleft()
        for nxt in adj[node]:
            if nxt not in seen:
                seen.add(nxt)         # mark on enqueue to avoid re-visits
                q.append((nxt, dist + 1))

Use for: shortest path in unweighted graphs, level-order traversal, "minimum steps" problems.

DFS — connectivity, cycles, topological sort

def dfs(adj, node, seen):
    seen.add(node)
    for nxt in adj[node]:
        if nxt not in seen:
            dfs(adj, nxt, seen)

Use for: connected components, cycle detection, topological sort (post-order on a DAG), flood fill. Watch recursion depth — convert to an explicit stack if the graph is deep.

Union-Find (Disjoint Set Union)

def find(parent, x):
    while parent[x] != x:
        parent[x] = parent[parent[x]]   # path compression
        x = parent[x]
    return x

def union(parent, a, b):
    parent[find(parent, a)] = find(parent, b)

Use for: dynamic connectivity, counting components, cycle detection in undirected graphs, Kruskal's MST.

Dijkstra — shortest path (weighted, non-negative)

A BFS variant using a min-heap keyed by distance; pop the closest unsettled node, relax its edges. Use for: weighted shortest path with non-negative weights (for negative weights, use Bellman-Ford).

When to use which (recognition cues)

Time complexities

• BFS / DFS: O(V + E)
• Dijkstra (binary heap): O((V + E) log V)
• Union-Find: ~O(α(n)) ≈ O(1) amortized per op

Common mistakes

• Marking visited too late in BFS (mark on enqueue, not dequeue) → duplicates and TLE.
• Infinite loops from revisiting nodes — always track seen.
• Recursion depth in DFS on large graphs → use an explicit stack.
• Using BFS for weighted shortest path — plain BFS only works when every edge costs the same.

Practice problems

Number of Islands, Clone Graph, Course Schedule I/II, Word Ladder, Rotting Oranges, Pacific Atlantic Water Flow, Number of Connected Components, Network Delay Time (Dijkstra), Redundant Connection (Union-Find).

Work through these by algorithm family — build a schedule with our free study-plan generator, or get live feedback in our DSA course.

More interview patterns: Dynamic Programming · Binary Search · Two Pointers · Sliding Window

Written by Amit Singh — Senior SDE at Amazon, Claude Certified Architect, and founder of AlgoEngineer.