Graph Algorithms Cheat Sheet for Interviews (with Code)

Almost every graph problem reduces 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 once edges carry weights. Learn those four with their recognition cues and "graph" stops being scary.

Start with the representation — it decides everything after it

Adjacency list — each node's neighbours. O(V + E) space; listing the neighbours of u costs O(deg(u)), and so does asking "is there an edge u→v?", because you scan.

Adjacency matrix — a V×V grid. O(1) edge lookup, but O(V²) space whether the edges exist or not, and listing u's neighbours costs O(V) even when it has two. At V = 10⁵ that is 10¹⁰ cells — 10 GB at one byte each — against a few megabytes for the same graph as a list.

Edge list — a flat list of (u, v, w). Useless for traversal, ideal for union find and Kruskal, which consume edges instead of exploring from a node.

Interview graphs are sparse, so the list is the default; take the matrix only when E approaches V², or when the problem hands you one and keeps asking "is u adjacent to v?". Most problems give you n and an edge list and expect you to build the list yourself:

from collections import defaultdict

def build_adj(n, edges):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)          # drop this line for a directed graph
    return adj

Two traps: reading a missing key on a defaultdict inserts an empty list, so adj[node] inside a loop over adj mutates the dict as you iterate it; and isolated nodes never appear. With ids 0..n-1, build adj = [[] for _ in range(n)] and index it — the only form worth writing in Java anyway:

List<List<Integer>> buildAdj(int n, int[][] edges) {
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int[] e : edges) {
        adj.get(e[0]).add(e[1]);
        adj.get(e[1]).add(e[0]);   // drop for a directed graph
    }
    return adj;
}

BFS — shortest path in an unweighted graph

from collections import deque

def bfs_distances(adj, start):
    dist = {start: 0}                        # doubles as the visited set
    q = deque([start])
    while q:
        node = q.popleft()
        for nxt in adj[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1   # mark on ENQUEUE
                q.append(nxt)
    return dist

int[] bfsDistances(List<List<Integer>> adj, int start) {
    int[] dist = new int[adj.size()];
    Arrays.fill(dist, -1);
    Deque<Integer> q = new ArrayDeque<>();
    dist[start] = 0;
    q.add(start);
    while (!q.isEmpty()) {
        int node = q.poll();
        for (int nxt : adj.get(node)) {
            if (dist[nxt] == -1) {
                dist[nxt] = dist[node] + 1;  // mark on ENQUEUE
                q.add(nxt);
            }
        }
    }
    return dist;
}

Mark visited on enqueue, never on dequeue — the most common silent bug in graph code. A node with many in-edges is discovered by several neighbours before it is ever dequeued; mark it only on the way out and each discovery pushes another copy, so the queue grows toward O(E) instead of O(V) and every duplicate redoes work. On grids, where you mark by mutating the cell, marking late is wrong rather than merely slow: two neighbours both claim the same cell.

DFS — recursive and iterative

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

void dfs(List<List<Integer>> adj, int node, boolean[] seen) {
    seen[node] = true;
    for (int nxt : adj.get(node)) {
        if (!seen[nxt]) dfs(adj, nxt, seen);
    }
}

The iterative form, which you want the moment the input is large:

def dfs_iterative(adj, start):
    seen = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in seen:            # guard on POP, not on push
            continue
        seen.add(node)
        for nxt in adj[node]:
            if nxt not in seen:
                stack.append(nxt)
    return seen

The inconsistency with BFS is deliberate. Marking on push keeps the stack small but no longer produces a true depth-first order, which breaks anything relying on DFS structure — post-order for topological sort, back edges for cycle detection. Mark on push when you only need reachability; guard on pop when you need real DFS order.

When BFS, when DFS

If the problem mentions a distance, a minimum number of steps, or a shortest anything on an unweighted graph, it is BFS — however tree-shaped it looks. It is the misclassification I see most in mock interviews: an elegant DFS written for a problem asking for the fewest moves, when DFS gives no guarantee that the first path it finds is short. BFS reaches every node along a fewest-edges path by construction.

If the problem is about reaching everything, or about the route taken rather than its length, it is DFS — components, flood fill, "does a path exist", all paths, cycles, topological order. The rule bends once: "minimum steps" with unequal edge costs is Dijkstra, not BFS.

Complexity, stated honestly

Both traversals are O(V + E) time: each node leaves the frontier once, each edge is examined once from each endpoint.

Space is where candidates get sloppy. BFS is O(V) — the visited structure holds up to V entries and, because you mark on enqueue, so does the queue. DFS is O(V) for the visited set plus O(H) for the recursion stack, H being the longest path explored; quote both, because O(H) alone is the tree answer.

That O(H) term is a real hazard. A line of 10⁵ nodes has H = 10⁵ and Python's default recursion limit is 1000, so you hit a RecursionError before you hit a wrong answer; Java overflows the thread stack in the low tens of thousands of frames. Raising the limit is a patch, the explicit-stack version above is the answer, and saying so unprompted is a senior signal.

For the weighted case: Dijkstra with a binary heap is O((V + E) log V), and union find is effectively O(α(n)) amortised.

A grid is an implicit graph

Most cheat sheets never say this out loud: a grid is already a graph. Each cell is a node; its neighbours are the four (or eight, with diagonals) in-bounds adjacent cells, computed from a direction array instead of stored in an adjacency list. With R×C cells and at most four edges each, O(V + E) is just O(R·C). The "number of islands" family then collapses into flood fill:

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            islands += 1
            stack = [(r, c)]
            grid[r][c] = '0'                  # sink it as you push
            while stack:
                i, j = stack.pop()
                for di, dj in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                    ni, nj = i + di, j + dj
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1':
                        grid[ni][nj] = '0'
                        stack.append((ni, nj))
    return islands

Count an island when you find unvisited land, then sink everything connected to it. Mutating the grid is O(1) extra space; if the input is read-only, use a seen set and say why.

The other grid idea to have ready is multi-source BFS: seed the queue with all sources at distance 0 instead of running one BFS per source, and a single pass gives every cell its distance to the nearest one.

from collections import deque

def oranges_rotting(grid):
    rows, cols = len(grid), len(grid[0])
    q, fresh = deque(), 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                q.append((r, c))          # every rotten orange is a source
            elif grid[r][c] == 1:
                fresh += 1

    minutes = 0
    while q and fresh:
        for _ in range(len(q)):           # one full level = one minute
            r, c = q.popleft()
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1:
                    grid[nr][nc] = 2
                    fresh -= 1
                    q.append((nr, nc))
        minutes += 1
    return -1 if fresh else minutes

Two details carry it: snapshotting len(q) so each iteration drains exactly one level, which is what makes minutes meaningful, and tracking fresh to tell "finished" from "unreachable".

Topological sort, where the cycle is the real question

Kahn's algorithm: count in-degrees, start from every node with in-degree zero, decrement successors as you remove nodes.

from collections import deque

def topo_order(n, prerequisites):
    adj = [[] for _ in range(n)]
    indegree = [0] * n
    for course, prereq in prerequisites:      # edge prereq -> course
        adj[prereq].append(course)
        indegree[course] += 1

    q = deque(i for i in range(n) if indegree[i] == 0)
    order = []
    while q:
        node = q.popleft()
        order.append(node)
        for nxt in adj[node]:
            indegree[nxt] -= 1
            if indegree[nxt] == 0:
                q.append(nxt)

    return order if len(order) == n else []   # short order == cycle

O(V + E), and the last line is the one that matters: nodes left unemitted sit on or behind a cycle, so no valid ordering exists. A schedule that cannot be satisfied is a cycle-detection problem in costume — which is exactly why Course Schedule is asked. Watch the direction too: [course, prereq] means prereq → course, and reversing it yields a plausible answer that is backwards.

Cycle detection depends on the graph type

Both versions look like "DFS and check whether you have seen this node", which is why getting it wrong is common.

Undirected: track the parent. A visited neighbour is a cycle only if it is not the node you came from — otherwise you have detected the edge you walked in on. Union find is often cleaner: find(u) == find(v) before a union means that edge closes a cycle.

Directed: parent tracking is simply wrong, because an edge into an already-visited node may be a cross edge into a finished branch. You need to know whether the target is on the current path, which is what three-colour DFS encodes:

WHITE, GREY, BLACK = 0, 1, 2

def has_cycle_directed(n, adj):
    colour = [WHITE] * n

    def visit(node):
        colour[node] = GREY                    # on the current recursion stack
        for nxt in adj[node]:
            if colour[nxt] == GREY:            # back edge into the current path
                return True
            if colour[nxt] == WHITE and visit(nxt):
                return True
        colour[node] = BLACK                   # fully explored, safe
        return False

    return any(visit(i) for i in range(n) if colour[i] == WHITE)

Grey is "on the stack right now", black is "finished, and nothing under it looped back". If you already ran Kahn's algorithm you have the answer for free: a short order means a cycle.

Union find, with both optimisations

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                    # already connected: this edge is redundant
        if self.rank[ra] < self.rank[rb]:   # union by rank: shallow under deep
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

With both optimisations the amortised cost per operation is O(α(n)), α being the inverse Ackermann function — under 5 for any input that fits in a computer, which is why people round it to constant. Be precise on two points: it is amortised over a sequence of operations, not a worst-case per-operation bound, and either optimisation alone only gets you to logarithmic.

Union find beats re-running a traversal when connectivity is built up incrementally: a traversal answers one snapshot in O(V + E), so m queries interleaved with m edge insertions cost O(m·(V + E)) by re-traversal against O(m·α(n)) with a DSU. It gives you no path, no distance and no un-merge, so edge deletion sends you back to traversal.

Dijkstra — the moment BFS stops working

Dijkstra is the boundary of BFS, not a separate idea. BFS is correct because every edge costs the same, so the queue is already ordered by distance. Weights break that — a two-edge path can be cheaper than a one-edge path — so the queue becomes a min-heap keyed by distance and you pop the closest unsettled node.

import heapq

def dijkstra(adj, start, n):               # adj[u] = [(v, weight), ...]
    dist = [float('inf')] * n
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, node = heapq.heappop(heap)
        if d > dist[node]:                 # lazy deletion: a stale entry
            continue
        for nxt, w in adj[node]:
            nd = d + w
            if nd < dist[nxt]:
                dist[nxt] = nd
                heapq.heappush(heap, (nd, nxt))
    return dist

The if d > dist[node]: continue line is lazy deletion: binary heaps have no decrease-key, so you push a better entry and skip stale copies as they surface. The heap can hold O(E) entries as a result; the bound is still O((V + E) log V).

Two boundaries to name before you are asked. Negative weights break Dijkstra, because a settled node can still be improved later — that is Bellman-Ford, O(V·E). And with 0/1 weights you need no heap: a deque, pushing 0-weight edges to the front and 1-weight to the back, gives 0-1 BFS in O(V + E).

Recognition cues

Common mistakes

• Marking visited on dequeue — duplicates in the queue, wrong answers on grids.
• Recursing on a 10⁵-node path graph — convert to an explicit stack first.
• Parent tracking on a directed graph — cycles there need the recursion stack.
• Returning a topological order without checking its length — that is the half being tested.
• Claiming O(α(n)) without path compression — O(log n) at best.

Practice problems

• Number of Islands — whether you see a grid as a graph, and sink cells as you push them.
• Rotting Oranges — multi-source BFS and level-by-level counting.
• Course Schedule II — Kahn's algorithm, and the cycle case that returns an empty order.
• Word Ladder — BFS on an implicit graph of one-character mutations; the test is generating neighbours cheaply rather than comparing every pair of words.
• Redundant Connection — union find, and whether union reports endpoints that already share a root.
• Network Delay Time — Dijkstra with lazy deletion, including the unreachable-node case.

Work through them by algorithm family rather than in list order — build the schedule with our free study-plan generator, or get live feedback on your traversals in our DSA course.

Traversals, topological sort and union find are four of the seventeen shapes in the complete DSA patterns guide, which covers telling all seventeen apart under time pressure.

If you keep one line from this page, keep the decision rule: the word "distance" means BFS, the words "all paths" mean DFS. Nearly everything else bolts onto one of those two loops.

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

The remaining patterns publish on the same cadence — have them sent to you.

Amit Singh teaches the DSA cohort at AlgoEngineer. He is a Senior SDE at Amazon and a Claude Certified Architect.