Graph Algorithm Patterns — Complete Guide

If you have been grinding LeetCode for a while, you have probably noticed that graph algorithms leetcode problems feel wildly different from one another. A shortest path question looks nothing like a dependency ordering question, and a connected components problem seems unrelated to cycle detection. But here is the secret: every graph problem maps to one of six patterns.

Once you learn to identify which pattern a problem belongs to, the solution strategy becomes almost mechanical. Instead of staring at a new graph problem and wondering where to start, you match it to a pattern and apply a well-practiced template.

Graph problems make up a significant portion of coding interviews at top companies. They test your ability to model real-world relationships — social networks, course prerequisites, maze navigation, network connectivity — as nodes and edges. The good news is that the underlying algorithms are surprisingly few.

In this guide, we will walk through each of the six core graph patterns, show you real LeetCode problems that use them, and give you a decision framework for choosing the right approach every time.

Before solving any graph problem, you need to decide how to represent it. The three main representations are adjacency lists, adjacency matrices, and edge lists. Your choice affects both code simplicity and time complexity, so understanding the trade-offs is essential.

An adjacency list stores each node alongside a list of its neighbors. This is the most common representation in coding interviews because it uses O(V + E) space and makes neighbor traversal efficient. Most LeetCode graph problems either give you an adjacency list directly or expect you to build one from an edge list.

An adjacency matrix uses a 2D array where matrix[i][j] indicates whether an edge exists between nodes i and j. It uses O(V^2) space, which is wasteful for sparse graphs but enables O(1) edge lookups. You will rarely build one in an interview unless the problem specifically calls for it or the graph is dense.

An edge list is simply an array of [source, destination] pairs. It is the rawest representation and often what LeetCode gives you as input. Your first step is almost always converting it into an adjacency list before running any algorithm.

Breadth-first search is the go-to algorithm when you need the shortest path in an unweighted graph or when you need to process nodes level by level. BFS explores all neighbors at distance k before moving to distance k+1, which guarantees that the first time you reach a node, you have found the shortest path to it.

The classic BFS template uses a queue. You start by enqueuing the source node, then repeatedly dequeue a node, process it, and enqueue all unvisited neighbors. The visited set is critical — without it, you will revisit nodes and potentially loop forever in cyclic graphs.

Word Ladder (LeetCode #127) is one of the most famous BFS problems. You need to find the shortest transformation sequence from a begin word to an end word, changing one letter at a time. Each word is a node, and two words are connected if they differ by exactly one character. BFS finds the minimum number of transformations.

Rotting Oranges (LeetCode #994) is a multi-source BFS problem. All rotten oranges start spreading simultaneously, so you enqueue all of them at the start and process level by level. Each level represents one minute of elapsed time. This pattern — multi-source BFS — appears whenever multiple starting points expand in parallel.

Depth-first search dives as deep as possible along each branch before backtracking. It is the right choice when you need to explore all possible paths, detect cycles, or perform exhaustive search. DFS is simpler to implement recursively and uses O(V) space on the call stack.

Number of Islands (LeetCode #200) is the quintessential DFS problem. Given a 2D grid of ones and zeros, you count connected components of ones. For each unvisited one, you run DFS to mark the entire island as visited, then increment your count. This pattern — DFS for connected component counting — recurs across dozens of problems.

Clone Graph (LeetCode #133) requires you to create a deep copy of an undirected graph. DFS with a hash map that maps original nodes to their clones handles this elegantly. As you traverse each node, you clone it, store the mapping, and recursively clone all neighbors. The hash map doubles as your visited set.

DFS also powers cycle detection in directed graphs. By tracking three states — unvisited, in-progress, and completed — you can detect back edges that indicate cycles. If you visit a node that is currently in-progress on your DFS stack, you have found a cycle. This is the foundation for topological sort validation.

Topological sort produces a linear ordering of nodes in a directed acyclic graph (DAG) such that for every edge u to v, u appears before v. It is the definitive pattern for dependency resolution problems — whenever you see "prerequisites," "build order," or "task scheduling," think topological sort.

There are two standard approaches: Kahn's algorithm (BFS-based) and DFS-based. Kahn's algorithm maintains an in-degree count for each node, starts with all zero-in-degree nodes in a queue, and repeatedly removes nodes while decrementing neighbors' in-degrees. It has the advantage of naturally detecting cycles — if you process fewer nodes than exist, a cycle is present.

Course Schedule (LeetCode #207) asks whether you can finish all courses given prerequisite pairs. This is a direct application of topological sort — model courses as nodes and prerequisites as directed edges, then check whether a valid topological ordering exists. Course Schedule II (#210) extends this by asking you to return the actual ordering.

Alien Dictionary (LeetCode #269) is a harder topological sort problem. Given a sorted list of words in an alien language, you must deduce the character ordering. You extract ordering constraints by comparing adjacent words character by character, build a directed graph of character dependencies, and run topological sort. It elegantly combines string processing with graph algorithms.

Union-Find (also called Disjoint Set Union) is a specialized data structure for tracking connected components and answering connectivity queries efficiently. While DFS and BFS can also find connected components, Union-Find shines when you process edges incrementally or need to answer many "are these two nodes connected?" queries.

The data structure supports two operations: find (which component does this node belong to?) and union (merge two components). With path compression and union by rank optimizations, both operations run in nearly O(1) amortized time — specifically O(alpha(n)), where alpha is the inverse Ackermann function.

Number of Connected Components in an Undirected Graph (LeetCode #323) is a straightforward Union-Find application. Start with n components (one per node), iterate through edges calling union on each pair, and return the final component count. Each successful union decrements the count by one.

Redundant Connection (LeetCode #684) asks you to find the edge that, when removed, turns a graph with one extra edge back into a tree. Process edges one by one with Union-Find — the first edge whose endpoints already belong to the same component is redundant. This incremental processing pattern is where Union-Find beats BFS and DFS.

The hardest part of graph problems is not implementing the algorithm — it is recognizing which algorithm to use. Here is a decision framework that covers the vast majority of graph algorithms leetcode problems you will encounter in interviews.

Start by identifying what the problem is actually asking. Need the shortest path or minimum steps? Use BFS. See dependencies, prerequisites, or ordering constraints? Use topological sort. Need to find or count connected components? Union-Find is your fastest option. Need to explore all possible paths or detect cycles? Use DFS.

Some problems combine patterns. For example, you might use BFS for shortest path but need Union-Find to preprocess connectivity. Or you might use DFS to detect cycles before running topological sort. The key is to break the problem into subproblems and match each subproblem to its pattern.

Practice is the final piece. Use YeetCode flashcards to drill pattern recognition until identifying the right graph algorithm becomes automatic. When you see a new graph problem in an interview, you should be able to classify it within seconds — not minutes.