Graph Algorithms LeetCode Pattern Guide — DFS, BFS, Dijkstra, and Union-Find

A graph algorithms LeetCode pattern guide should start before the algorithm choice. Most graph mistakes happen because candidates do not identify the graph shape: directed or undirected, weighted or unweighted, cyclic or acyclic, explicit adjacency list or hidden grid, static or changing connectivity. DFS, BFS, Dijkstra, and union-find solve different versions of "relationships between things." The interview signal is not memorizing names. It is mapping the prompt to the right graph model, stating the invariant, and avoiding accidental exponential search.

Graph algorithms LeetCode pattern guide: choose by question type

Use this table as the first decision pass:

| Prompt asks for | Usually use | Reason | |---|---|---| | Can I reach X? Count components? Explore all connected cells? | DFS or BFS | Traversal visits reachable nodes | | Shortest path in unweighted graph | BFS | Each edge has equal cost, levels are distance | | Shortest path with nonnegative weights | Dijkstra | Expands cheapest known frontier | | Connectivity after many unions | Union-find | Maintains components efficiently | | Detect cycle in undirected graph | DFS or union-find | Parent tracking or failed union | | Detect cycle in directed graph | DFS colors | Back edge means cycle | | Course prerequisites / ordering | Topological sort | Directed acyclic dependency order | | Island/grid problems | DFS/BFS/union-find | Grid cells are graph nodes |

If edge weights can be negative, Dijkstra is not valid. LeetCode rarely expects Bellman-Ford unless the prompt clearly includes negative weights or "cheapest with at most k stops" variants. For those, dynamic programming or modified BFS may be intended.

Step 1: build the graph model

Before writing code, say what the nodes and edges are. In "number of islands," nodes are land cells and edges connect four-directional neighbors. In "course schedule," nodes are courses and directed edges represent prerequisites. In "word ladder," nodes are words and edges connect words that differ by one character. In "accounts merge," nodes can be emails, and edges connect emails from the same account.

Then choose a representation:

• Adjacency list for sparse explicit graphs.
• Matrix or grid loops for board problems.
• Hash map of lists when node labels are strings.
• Edge list for union-find or Bellman-Ford style processing.
• Implicit neighbor generation when listing all edges would be too expensive.

The hidden cost is often graph construction. For word ladder, comparing every word to every other word is O(n^2 L). A wildcard pattern map like ht -> hot, hit can reduce neighbor generation. In interviews, mention graph construction complexity, not just traversal complexity.

DFS pattern: exhaustive reachability and structure

DFS goes deep before it goes wide. It is a good fit for connected components, island area, path existence, cycle detection, tree-like recursion, and backtracking with graph constraints.

The core invariant: once a node is marked visited, we will not process it again. That single set prevents infinite loops in cyclic graphs. Recursive DFS is compact, but iterative DFS with a stack avoids recursion depth problems.

Common DFS templates:

• Component count: for every node not visited, increment count and DFS from it.
• Grid flood fill: if cell is in bounds, land/target, and unvisited, mark and explore neighbors.
• Directed cycle detection: use colors: unvisited, visiting, visited. Seeing a visiting neighbor means a cycle.
• Backtracking: mark choice, recurse, unmark choice when paths are independent.

A trap: using one visited set when the problem requires path-specific state. In "all paths from source to target" in a DAG, a global visited set can incorrectly suppress valid paths. Use path stack or rely on DAG structure.

Another trap: mutating the input grid without permission. It is often accepted to turn land into water, but say that this is an in-place visited marker. If the prompt requires preserving input, use a separate visited set.

BFS pattern: shortest path by layers

BFS explores all nodes at distance d before distance d+1. That makes it the default for shortest path in unweighted graphs. The queue is not just an implementation detail; it represents the frontier of the current distance.

Use BFS for:

• Shortest path in a binary matrix.
• Minimum genetic mutation.
• Word ladder length.
• Rotting oranges.
• Nearest exit from maze.
• Level-order graph expansion.

The clean BFS distance pattern stores (node, distance) in the queue or loops by level size and increments distance after each level. Both are fine. The key is marking nodes visited when enqueued, not when dequeued, to avoid duplicate queue entries.

Multi-source BFS is a frequent upgrade. Put all starting sources into the queue at distance zero, then expand. This solves rotting oranges, walls and gates, distance to nearest zero, and shortest distance from any source. Candidates often run BFS from every empty cell, which is too slow. Flip the perspective: start from all sources at once.

Dijkstra pattern: weighted shortest path

Dijkstra solves shortest path when edge weights are nonnegative. It uses a min-heap ordered by current known distance. Each pop gives the cheapest frontier candidate. If the popped distance is stale because a better one was already recorded, skip it.

The invariant: when a node is finalized with the smallest distance from the heap, no future nonnegative path can improve it. That is why negative weights break the algorithm.

Typical Dijkstra prompts:

• Network delay time.
• Path with minimum effort.
• Cheapest route in weighted grid.
• Minimum time to reach all nodes.
• Swim in rising water style min-max path.

Not every Dijkstra-like problem sums weights. "Path with minimum effort" minimizes the maximum edge on the path. The heap key becomes current path effort, and relaxing an edge uses max(current_effort, edge_effort). The same frontier principle applies.

Complexity is O((V + E) log V) with a heap. In dense graphs, this can be large, but most interview graphs are sparse or grid-based.

Union-find pattern: dynamic connectivity

Union-find, also called disjoint set union, maintains components under merge operations. It supports find(x) to get a representative and union(a, b) to merge components. With path compression and union by rank/size, operations are almost constant time.

Use union-find when the prompt says:

• Count connected components from edges.
• Determine if adding an edge creates a cycle in an undirected graph.
• Merge accounts or synonyms.
• Number of islands II as land is added over time.
• Kruskal minimum spanning tree.
• Satisfiability of equality equations.

The mental model: DFS/BFS answers connectivity by exploring the graph now. Union-find answers connectivity by maintaining components as edges arrive. If the graph changes through many union operations and many connectivity queries, union-find is usually cleaner.

The traps are initialization and counting. Every node must have a parent before union. If nodes appear as strings, create entries lazily. When union merges two different roots, decrement component count. If roots are already equal, do not decrement.

Union-find is not good for directed reachability or shortest paths. It knows whether nodes are in the same undirected component, not how to travel between them.

Topological sort: dependencies and order

Topological sort belongs in a graph pattern guide because many "graph" questions are actually dependency questions. If the graph is directed and the prompt asks whether all tasks can be completed, or asks for an ordering, think topological sort.

Kahn's algorithm:

1. Build adjacency list and indegree count.
2. Queue all nodes with indegree zero.
3. Pop a node, append to order.
4. Decrement indegree of neighbors.
5. Add neighbors whose indegree becomes zero.
6. If processed count is less than node count, there is a cycle.

DFS can also produce topological order by postorder, but Kahn's algorithm is easier to explain for course scheduling because indegree maps directly to "remaining prerequisites."

Common mistake: reversing the prerequisite edge. If pair [a, b] means take b before a, then edge is b -> a. Get this wrong and your order may still contain all courses but violate dependencies.

Grid graphs: the hidden graph category

Many graph questions never say graph. A grid is a graph where each cell is a node and neighboring cells are edges. Before coding, define the neighbor directions: four-way, eight-way, knight moves, or problem-specific transitions.

Grid checklist:

• Bounds check before reading cell.
• Decide if diagonal movement is allowed.
• Decide if obstacles block traversal.
• Mark visited at the right time.
• For shortest path, use BFS, not DFS.
• For weighted movement, use Dijkstra or 0-1 BFS if weights are only 0 and 1.
• For island count, DFS/BFS or union-find both work.

For 0-1 BFS, use a deque: push front for cost 0 edges and push back for cost 1 edges. It is a specialty pattern, but useful when a prompt has binary edge costs.

Complexity language interviewers like

Do not say "DFS is O(n)" unless you define n. For graphs, say O(V + E) time and O(V) space for visited plus recursion/queue. For grids, V = rows cols and E is bounded by about 4V, so traversal is O(rows cols).

For Dijkstra, say O((V + E) log V) with a binary heap. For union-find, say O(E alpha(V)), effectively near constant per operation, where alpha is inverse Ackermann. You do not need to dwell on the math; the point is that path compression makes it extremely fast.

For topological sort, O(V + E).

The best explanations include both graph construction and algorithm cost. If you build an adjacency list from an edge list, that is O(E). If you generate neighbors on the fly, mention that too.

Common graph traps

No visited set. Cycles create infinite loops or exponential repeated work.

Visited too late. In BFS, mark when enqueuing to avoid duplicates.

Wrong algorithm for shortest path. DFS does not guarantee shortest path in unweighted graphs; BFS does.

Using Dijkstra with negative weights. Nonnegative weights are required.

Confusing directed and undirected cycles. Parent tracking works for undirected; color states are needed for directed.

Forgetting disconnected nodes. Loop over all nodes if components matter.

Incorrect edge direction. Prerequisite and dependency prompts are notorious for this.

Path state vs global visited. Some problems require revisiting a node with different state, such as key sets in a maze. Then visited must include (node, state).

Prep checklist for graph problems

Before coding, answer:

• What are the nodes?
• What are the edges?
• Is the graph directed?
• Are edges weighted?
• Is the graph explicit or implicit?
• Do I need reachability, shortest path, ordering, or connectivity under merges?
• Can nodes repeat with different state?
• What marks a node visited?
• Do I need to process all components?

This checklist prevents most wrong turns.

How to talk about graph algorithms in interviews and resumes

In interviews, lead with the model: "I will treat each course as a node and each prerequisite as a directed edge." Then choose the algorithm: "Because we need an order and cycles make completion impossible, I will use topological sort." That is stronger than jumping straight into code.

On a resume, avoid writing "Solved graph problems." Translate it into systems language:

• "Modeled account relationships as a graph and merged connected identities with union-find."
• "Built BFS-based nearest-resource lookup for location cells, reducing repeated searches."
• "Implemented priority-queue shortest-path routing over weighted service edges."

Graph skill is really modeling skill. Once you identify the right nodes, edges, weights, and state, DFS, BFS, Dijkstra, union-find, and topological sort become straightforward tools instead of guesses.

Related guides

• DFS LeetCode Pattern Guide — Recursion Templates and Grid/Graph Problems — A DFS LeetCode pattern guide with recursion templates, visited-set rules, grid and graph examples, backtracking structure, complexity notes, and interview pitfalls.
• Union-Find LeetCode Pattern Guide — Disjoint Sets, Connectivity, and Kruskal's — A practical Union-Find LeetCode pattern guide for disjoint sets, connectivity checks, cycle detection, component counting, and Kruskal's minimum spanning tree problems.
• BFS LeetCode Pattern Guide — Shortest-Path, Level-Order, and Multi-Source — A BFS LeetCode pattern guide for recognizing queue-based problems, implementing level-order traversal, solving unweighted shortest paths, using multi-source BFS, and avoiding common visited-state bugs.
• Greedy Algorithms LeetCode Pattern Guide — Interval Scheduling and Exchange Arguments — A practical greedy algorithms LeetCode pattern guide for recognizing interval scheduling, proving choices with exchange arguments, and avoiding the traps that make greedy solutions fail.
• Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets — A practical backtracking LeetCode pattern guide with templates, decision rules, duplicate-handling tricks, pruning advice, and interview talk tracks for permutations, combinations, subsets, and constraint problems.