Graphs

What is a graph?

A graph is a collection of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles, and nodes can have any number of neighbors in any direction.

Two key properties to establish upfront: directed vs undirected (do edges have direction?), weighted vs unweighted (do edges have costs?). Most interview problems use undirected, unweighted graphs unless explicitly stated otherwise.

The standard adjacency list representation uses a dict of list:

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0],
    3: [1],
}

Adjacency matrix: grid[i][j] = 1 if edge exists. O(1) edge lookup, O(V²) space. Adjacency list: O(degree) edge lookup, O(V + E) space. Use adjacency lists by default - most interview graphs are sparse.

The core trade-off: graphs model arbitrary connectivity but require a visited set to avoid infinite loops. Trees never need this because they are acyclic by definition.

Core operations

Key patterns

BFS (shortest path / level-order)

BFS fans out from the start one ring at a time, visiting every node at distance 1 before any node at distance 2.

When to use - you need the shortest path, or the fewest steps, between two nodes in an unweighted graph, or you want to process nodes in order of distance from a source. The naive alternative is to enumerate every path and keep the shortest, which is exponential; BFS finds it in one O(V + E) sweep.

How it works - keep a queue and pull nodes off it in FIFO order, enqueuing each undiscovered neighbor as you go. The invariant is that nodes leave the queue in non-decreasing distance order, so the first time you reach a node is always by a shortest path - you never find a cheaper route later. Mark a node visited the moment you enqueue it, not when you dequeue it. Each node is enqueued once and each edge is examined once, which is what keeps the whole traversal at O(V + E).

DFS with visited set (connected components)

DFS walks as deep as it can down one path before backing up, and a visited set stops it from looping forever on a cycle.

When to use - you want to know which nodes are reachable from a start, count connected components, or detect a cycle. The brute force of re-checking reachability from every node pair is O(V²) or worse; a DFS from each unvisited node settles the whole question in O(V + E).

How it works - recurse (or use an explicit stack) into each neighbor, marking nodes visited so you never enter the same node twice. One DFS launched from an unvisited node reaches exactly the nodes in its connected component, so iterating over all nodes and starting a fresh DFS at each still-unvisited one counts the components in a single pass. The visited check is what makes graph DFS terminate where tree DFS does not: trees are acyclic, but a graph can loop back, and without the check the recursion never ends. Every node and edge is touched once, so the total cost is O(V + E).

Topological sort

Order the nodes of a directed graph so every edge points forward, peeling off nodes that have no remaining prerequisites.

When to use - you need a valid order for tasks with dependencies (build steps, course prerequisites, package installs), or you need to know whether such an order even exists. Trying every permutation to find a consistent one is factorial; Kahn's algorithm produces an order, or proves none exists, in O(V + E).

How it works - compute each node's in-degree, then queue every node whose in-degree is 0 - those depend on nothing and can go first. Pop one, append it to the order, and decrement its neighbors' in-degrees; any neighbor that drops to 0 is now free and joins the queue. The removal order is a valid topological order because a node is only released once every edge pointing into it has been resolved. If the loop ends having placed fewer than V nodes, the leftovers each still wait on one another - that mutual wait is a cycle, so no ordering exists. Each node is queued once and each edge is decremented once, giving O(V + E).

Canonical examples

Number of islands

Each '1' cell is a node; adjacent '1' cells share an edge. The insight: DFS from any unvisited '1' cell and mark all reachable '1' cells visited by sinking them to '0'. Each DFS launch from an unvisited cell counts as one island. This avoids a separate visited set by mutating the grid in place.

Course schedule (cycle detection)

Given courses with prerequisites, determine if all courses can be finished. A cycle in the prerequisite graph means some course indirectly depends on itself, making it impossible to complete. Kahn's algorithm solves this without explicitly looking for cycles: if topological sort processes all V nodes, no cycle exists. If fewer than V nodes are processed, the remainder form a cycle.

When to reach for a graph

• The problem describes entities with arbitrary connections (cities and roads, people and friendships, courses and prerequisites).
• You need to find connected components or check if two nodes can reach each other - DFS.
• You need the shortest path between nodes in an unweighted graph - BFS.
• The problem involves ordering with dependencies (task scheduling, course prerequisites) - topological sort.
• The problem gives you a grid and asks you to explore regions - treat it as an implicit graph with 4-directional edges.
• You need to detect a cycle in a directed or undirected graph.

Practice problems

• Number of Islands - Grid DFS, the most common graph entry point.
• Clone Graph - DFS/BFS with a hash map to track cloned nodes.
• Course Schedule - Cycle detection via topological sort.
• Number of Connected Components in an Undirected Graph - DFS/BFS component counting.
• Pacific Atlantic Water Flow - Multi-source BFS from two boundaries, intersect reachable sets.
• Word Ladder - BFS on an implicit graph where edges connect words differing by one letter.