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:

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

Example: fewest hops from a source. Given edges 0-1, 0-2, 1-3, 2-3, 3-4 starting at 0, the queue holds 0, then 1 and 2, then 3, then 4 - one layer per distance. Node 3 is reachable from both 1 and 2, but whichever neighbor dequeues first enqueues it once and marks it visited, so 3 is processed exactly once at distance 2. Node 4 takes three hops total, the fewest possible - the visualizer below shows the queue filling level by level.

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

Example: count friend groups. Given edges 0-1, 1-2, 3-4, the scan starts at unvisited 0 and a stack-based DFS swallows 1 and 2 for component #1. Nodes 0 through 2 are now visited, so the scan skips them and starts fresh at 3, whose DFS picks up 4 for component #2. Five nodes, two groups: and - the visualizer below colors each group as its DFS completes.

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

Example: order tasks by prerequisites. Given 0>1, 0>2, 1>3, 2>3, only 0 starts with in-degree 0, so it is emitted first. Emitting 0 drops 1 and 2 to in-degree 0 and both join the queue; emitting 1 takes 3 down to in-degree 1, and emitting 2 finally releases it. The result 0, 1, 2, 3 is valid (as is the swap 0, 2, 1, 3) - the visualizer below emits one of them; a cycle would leave nodes stranded.

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.