A graph is a set of nodes (vertices) joined by edges. Edges may be directed (a prerequisite, a one-way street) or undirected (a friendship, a road), and weighted (distance, cost) or unweighted. Trees, linked lists and grids are all special cases — a tree is a connected graph with no cycles, a grid is a graph whose edges are implied by coordinates. The drills on this page are the general case, where you must build the edges yourself from an input list.

In Java the standard representation is an adjacency list: List<List<Integer>> graph, where graph.get(u) holds every neighbour of u. It uses O(V + E) memory and lets you iterate a node's neighbours in time proportional to its degree, which is what makes every traversal below O(V + E). An adjacency matrix (boolean[V][V]) answers "is there an edge u–v?" in O(1) but costs O(V²) memory and O(V) per neighbour scan, so it only pays off for small dense graphs.

Graph questions rarely say "graph". They say courses and prerequisites, accounts sharing an email, words differing by one letter, cities and flight costs. Step one is always to name the nodes and the edges; step two is to recognise what is being asked of them.

Four templates, each a few lines long, are the building blocks of all nine drills. They are written in pseudocode here; every drill below has the full Java version.

graph dfs hashmap deep copy

Given a reference to one node of a connected undirected graph, return a deep copy of the whole graph. Each node has an integer val and a list of neighbors. The copy must contain brand-new node objects with the same values and the same neighbour structure — no reference may point back into the original graph.

A naive recursive copy ("new node, then copy each neighbour") never terminates on a cycle, and on a DAG-shaped graph it duplicates shared nodes. Tracking visited originals fixes termination, but you still need to find the copy of an already-visited neighbour to wire the edge — hence a map rather than a set. DFS or BFS both work in O(V + E).

• If the input is null, return null.
• clone(node): if the map has it, return the stored copy.
• Otherwise create the copy, put it in the map, then for each neighbour add clone(neighbour) to the copy's list.
• Return the copy of the start node.

graph union-find connected components

You are given n nodes labelled 0 to n - 1 and a list of undirected edges. Return the number of connected components — maximal groups of nodes where every node can reach every other.

Building an adjacency list and launching a DFS from every unvisited node also works in O(V + E) and is a perfectly good answer. Union-Find avoids building the adjacency list at all, processes edges in a single streaming pass, and is the better fit when edges arrive over time ("how many components after each new edge?"). Without path compression and union by rank, chains can grow to length n and each find costs O(n), giving O(n·E).

• Initialise parent[i] = i, rank[i] = 0, components = n.
• For each edge (a, b), call union(a, b); on success, components--.
• Return components.

graph union-find tree property

Given n nodes labelled 0 to n - 1 and a list of undirected edges, return true if the edges form a valid tree — that is, the graph is connected and has no cycles.

The DFS alternative builds an adjacency list, runs DFS from node 0 while tracking the parent (to ignore the edge you came from), fails on any visited non-parent neighbour, and finally checks that all n nodes were visited. It is O(V + E) but has two separate failure modes to get right. The edge-count + Union-Find version has one loop and no parent bookkeeping.

• If edges.length != n - 1, return false.
• For each edge, if union(a, b) fails (same root), return false.
• Return true.

graph dfs cycle detection directed

There are numCourses courses labelled 0 to numCourses − 1. Each pair [a, b] in prerequisites means you must take course b before course a. Return true if it is possible to finish every course.

Trying every ordering of courses is O(V!) and hopeless. Two O(V + E) answers exist: Kahn's algorithm (count how many nodes can be peeled with in-degree 0 — see the next drill) and DFS colouring, shown here. The BLACK state is the key optimisation: a node proven cycle-free is never re-explored, so each node and edge is processed once. Without it (only an on-path flag) the DFS revisits shared sub-graphs and can become exponential.

• Build the adjacency list with edges b → a for each pair [a, b].
• For every WHITE course, run hasCycle.
• hasCycle(u): colour GRAY; for each neighbour, GRAY means cycle; WHITE means recurse; then colour BLACK.
• Return false if any cycle is found, otherwise true.

graph bfs topological order dag

Given n nodes and a list of directed edges [u, v] meaning "u must come before v", return an ordering of all nodes that respects every edge (a topological order). If the graph contains a cycle, no such order exists — return an empty array.

Generating permutations and checking each is O(n!·E). The DFS alternative pushes each node onto a stack after its descendants finish and reverses the stack at the end — also O(V + E), but it needs separate cycle detection (the gray state from Drill 75). Kahn's algorithm gives the order and the cycle check together, iteratively, with no recursion depth risk.

• Build the adjacency list and indegree[].
• Enqueue every node with in-degree 0 (in index order here: 4, 5).
• Poll u, append to the order, decrement each neighbour's in-degree, enqueue those that reach 0.
• If the order has n nodes return it; otherwise return [].

graph union-find hashmap sorting

Each account is a list whose first element is a name and the rest are email addresses. Two accounts belong to the same person if they share at least one email (directly or through a chain of accounts). Accounts with the same name may belong to different people. Merge the accounts and return each person as [name, emails in sorted order].

Comparing every pair of accounts for shared emails is O(A² · k) and still needs transitive merging. A graph-of-emails DFS (connect all emails within an account, then DFS each component) is the other standard answer, O(N log N). Union-Find over account indices is the most compact: one pass to union, one pass to group, then sort each group. Sorting dominates: O(N log N) for N total emails.

• parent[i] = i for each account.
• For each email of account i: owner.putIfAbsent(email, i); if it already had an owner p, union i with p.
• For each (email, owner), add the email to a TreeSet keyed by find(owner).
• Emit [name of root account] + sorted emails for each root.

graph bfs implicit graph shortest path

Given beginWord, endWord and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, where each step changes exactly one letter and every intermediate word must be in wordList. Return 0 if no sequence exists. beginWord itself need not be in the list.

Building the explicit graph by comparing every pair of words costs O(N²·L) before the search even starts. Generating neighbours by letter substitution costs O(26·L) candidates per word, each needing O(L) to build and hash, so the BFS is O(N·26·L²) — far better when N is large. DFS is wrong here: it finds a ladder, not the shortest. Bidirectional BFS (expanding from both ends, always the smaller frontier) is the standard follow-up optimisation.

• Put the dictionary in a HashSet; if endWord is missing, return 0.
• BFS from beginWord with level = 1.
• For each polled word: if it equals endWord, return level. Otherwise try every position × every letter; if the candidate is removed from the set (i.e. it was unvisited), enqueue it.
• After each level, level++. Queue exhausted ⇒ return 0.

graph greedy union-find mst

Given a connected, undirected graph with n nodes and weighted edges [u, v, w], find the total weight of a minimum spanning tree — a subset of n − 1 edges that connects all nodes with the smallest possible total weight. Return -1 if the graph is not connected.

Enumerating every spanning tree is exponential (a complete graph has nⁿ⁻² of them). Kruskal sorts once — O(E log E) — and then does E near-constant Union-Find operations. Prim's algorithm is the alternative: grow one tree from a start node using a min-heap of crossing edges, O(E log V); it is preferred for dense graphs given as adjacency lists, Kruskal for sparse edge lists.

• Copy and sort the edges by weight (don't mutate the caller's array).
• For each edge, if union(u, v) succeeds, add its weight and count it.
• Stop once n − 1 edges are taken.
• Return the total if n − 1 edges were taken, else -1.

graph dijkstra priority queue greedy

Given an undirected graph with n nodes and edges [u, v, w] with non-negative weights, and a source node src, return the shortest distance from src to every node (Integer.MAX_VALUE for unreachable nodes).

BFS is wrong as soon as weights differ (it minimises edge count). Bellman-Ford relaxes every edge V−1 times — O(V·E) — and handles negative weights. Dijkstra with an array scan for the minimum is O(V²), good for dense graphs; with a binary heap it is O((V + E) log V), the standard interview answer for sparse graphs.

• Build the adjacency list (both directions for undirected edges).
• dist[] = MAX, dist[src] = 0, push (src, 0).
• Poll the smallest; skip it if stale; otherwise relax every edge and push improvements.
• Return dist when the heap is empty.

Nine drills, four templates. The table is the one-page revision sheet: if you can say why each row uses its pattern — and what would go wrong with the neighbouring pattern — you are ready for graph questions in interviews.

← 07 · Grids & Matrices All Coding Drills 09 · Dynamic Programming →