Graph problems appear in roughly 20% of coding interviews at top tech companies. The key is recognizing which graph algorithm applies to each problem type. This guide covers the essential graph algorithms, their time complexities, and the problem patterns that signal which algorithm to use — giving you a systematic approach to graph questions in interviews.
Graph Representation
Two representations: (1) Adjacency list — a dictionary mapping each node to its list of neighbors. graph[node] = [neighbor1, neighbor2, …]. For weighted graphs: graph[node] = [(neighbor1, weight1), (neighbor2, weight2)]. Space: O(V + E). Preferred for sparse graphs (most interview problems). (2) Adjacency matrix — a V x V matrix where matrix[i][j] = 1 (or weight) if there is an edge from i to j. Space: O(V^2). Preferred when you need O(1) edge existence checks or for dense graphs. Most interview problems use adjacency lists. Build the graph from the input edge list before running the algorithm: for each edge (u, v), add v to graph[u] (and u to graph[v] for undirected graphs).
BFS: Level-Order and Shortest Path in Unweighted Graphs
Breadth-First Search explores nodes level by level using a queue. Use BFS when: (1) Finding the shortest path in an unweighted graph (minimum number of edges). (2) Level-order traversal (binary tree level order, word ladder). (3) Finding all nodes within K distance. Algorithm: initialize a queue with the start node, mark it visited. While the queue is not empty: dequeue a node, process it, enqueue all unvisited neighbors. Track distance by processing one level at a time (loop through queue size at each level). Time: O(V + E). Space: O(V) for the visited set and queue. Classic BFS problems: word ladder (transform one word to another, changing one letter at a time — each word is a node, edges connect words differing by one letter), shortest path in a grid (each cell is a node, edges connect adjacent cells), rotting oranges (multi-source BFS from all rotten oranges simultaneously).
DFS: Connected Components, Cycles, and Backtracking
Depth-First Search explores as deep as possible before backtracking. Use DFS when: (1) Detecting cycles in a graph. (2) Finding connected components. (3) Topological ordering. (4) Path existence (is there any path from A to B?). (5) Exhaustive search with backtracking. Algorithm: use recursion or an explicit stack. Mark nodes as visited to avoid revisiting. For cycle detection in directed graphs, track three states: unvisited, in-progress (currently in the DFS stack), and completed. A back edge (edge to an in-progress node) indicates a cycle. Time: O(V + E). Space: O(V) for the recursion stack and visited set. Classic DFS problems: number of islands (iterate through the grid, DFS from each unvisited land cell to mark the entire island), clone graph (DFS with a hash map mapping original to cloned nodes), course schedule (detect cycle in a directed graph of prerequisites).
Topological Sort: Ordering Dependencies
Topological sort produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every edge (u, v), u comes before v. Use cases: task scheduling, build systems (compile dependencies), course prerequisites. Two algorithms: (1) Kahn algorithm (BFS-based) — compute in-degree for each node. Add all nodes with in-degree 0 to a queue. Process: dequeue a node, add it to the result, decrement in-degree of all its neighbors. If a neighbor in-degree reaches 0, enqueue it. If the result contains fewer than V nodes, the graph has a cycle (no valid topological order). (2) DFS-based — perform DFS. When a node has no more unvisited neighbors (post-order), push it onto a stack. The stack (reversed) is the topological order. Time: O(V + E) for both. Classic problems: course schedule II (return a valid course order), alien dictionary (determine letter ordering from a sorted word list — build a graph of letter precedence, topologically sort).
Dijkstra: Shortest Path in Weighted Graphs
Dijkstra algorithm finds the shortest path from a source to all other nodes in a graph with non-negative edge weights. Algorithm: use a min-heap (priority queue). Initialize distance[source] = 0, all others = infinity. Push (0, source) to the heap. While the heap is not empty: pop the node with smallest distance. For each neighbor, if distance[current] + edge_weight < distance[neighbor], update distance[neighbor] and push (new_distance, neighbor) to the heap. Skip nodes already processed (visited). Time: O((V + E) log V) with a binary heap. Space: O(V) for distances and the heap. Important: Dijkstra does not work with negative edge weights. Use Bellman-Ford for graphs with negative weights. Classic problems: network delay time (minimum time for a signal to reach all nodes — Dijkstra from the source, answer is the maximum distance), cheapest flights within K stops (modified Dijkstra with a stops constraint), path with minimum effort (Dijkstra where edge weight is the absolute height difference between cells).
Union-Find (Disjoint Set Union)
Union-Find tracks connected components and efficiently answers: “are these two nodes in the same group?” Two operations: find(x) returns the root representative of x group. union(x, y) merges the groups containing x and y. Optimizations: (1) Path compression — during find, make every node on the path point directly to the root. (2) Union by rank — attach the shorter tree under the root of the taller tree. With both optimizations, find and union are nearly O(1) — amortized O(alpha(N)) where alpha is the inverse Ackermann function, effectively constant. Use Union-Find when: grouping elements into sets, checking connectivity, counting connected components, and detecting cycles in undirected graphs (if union(u, v) is called and find(u) == find(v), there is a cycle). Classic problems: number of connected components, redundant connection (find the edge that creates a cycle), accounts merge (group accounts by shared emails), minimum spanning tree (Kruskal algorithm uses Union-Find).
Pattern Recognition for Graph Problems
Algorithm selection guide: (1) Shortest path, unweighted graph -> BFS. (2) Shortest path, weighted graph (non-negative) -> Dijkstra. (3) Shortest path, negative weights -> Bellman-Ford. (4) Detect cycle in directed graph -> DFS with three states. (5) Detect cycle in undirected graph -> Union-Find or DFS. (6) Order dependencies -> Topological sort. (7) Connected components -> DFS/BFS or Union-Find. (8) Minimum spanning tree -> Kruskal (Union-Find + sorted edges) or Prim (similar to Dijkstra). (9) All-pairs shortest path -> Floyd-Warshall O(V^3). (10) Bipartite check -> BFS/DFS with 2-coloring. Before writing code: draw the graph. Identify nodes and edges from the problem description. Determine if the graph is directed or undirected, weighted or unweighted, and whether cycles are possible. This determines the algorithm. Grid problems are implicit graphs: each cell is a node, adjacent cells are connected by edges. Convert the grid to a graph mentally and apply the appropriate algorithm.
{ “@context”: “https://schema.org”, “@type”: “FAQPage”, “mainEntity”: [ { “@type”: “Question”, “name”: “When should you use BFS versus DFS for graph problems in coding interviews?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Use BFS when: (1) Finding the shortest path in an unweighted graph — BFS explores level by level, so the first time it reaches a node is via the shortest path (minimum edges). DFS may find a longer path first. (2) Level-order problems — word ladder (minimum transformations), shortest path in a grid, minimum moves in a puzzle. (3) Multi-source problems — rotting oranges (BFS from all rotten oranges simultaneously), walls and gates (BFS from all gates). Use DFS when: (1) Detecting cycles — DFS with three node states (unvisited, in-progress, completed) naturally detects back edges that indicate cycles. (2) Topological sort — DFS post-order gives a reverse topological ordering. (3) Connected components — DFS from each unvisited node finds all nodes in the component. (4) Exhaustive path enumeration — finding all paths between two nodes requires DFS with backtracking. (5) Tree traversals (pre-order, in-order, post-order). Either works for: reachability (can I reach node B from node A?), connected components (both work, DFS is typically simpler), and graph traversal (visiting all nodes). When either works, DFS is often simpler to implement recursively and uses less memory for deep, narrow graphs. BFS uses less memory for wide, shallow graphs.” } }, { “@type”: “Question”, “name”: “How does Union-Find work and when is it better than BFS/DFS?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Union-Find (Disjoint Set Union) maintains a collection of disjoint sets with two operations: find(x) returns the representative element (root) of the set containing x, and union(x, y) merges the sets containing x and y. Implementation: an array parent[] where parent[i] is the parent of node i. Initially, parent[i] = i (each node is its own set). find(x): follow parent pointers to the root. With path compression, every node on the path points directly to the root after the first find. union(x, y): find the roots of x and y. If different, make one root point to the other. With union by rank, attach the shorter tree to the taller tree. With both optimizations, operations are nearly O(1) amortized. Union-Find is better than BFS/DFS when: (1) Edges arrive incrementally (online connectivity) — you process edges one at a time and need to answer is connected queries after each edge. Rebuilding a graph and running BFS for each query is O(E*(V+E)). Union-Find handles all queries in O(E*alpha(V)). (2) Cycle detection in undirected graphs — if union(u,v) finds that u and v already share the same root, adding edge (u,v) creates a cycle. (3) Kruskal minimum spanning tree — sort edges by weight, add each edge if it does not create a cycle (checked via Union-Find).” } }, { “@type”: “Question”, “name”: “How does Dijkstra algorithm work and what are its limitations?”, “acceptedAnswer”: { “@type”: “Answer”, “text”: “Dijkstra finds the shortest path from a source node to all other nodes in a weighted graph. Algorithm: (1) Initialize distance[source] = 0, all other distances = infinity. (2) Use a min-heap (priority queue). Push (distance=0, node=source). (3) Pop the node with the smallest distance. If already visited, skip it. (4) For each unvisited neighbor: new_dist = distance[current] + edge_weight. If new_dist < distance[neighbor], update distance[neighbor] = new_dist and push (new_dist, neighbor) to the heap. (5) Repeat until the heap is empty. Time: O((V + E) log V) with a binary heap. The algorithm is greedy — once a node is popped from the heap (visited), its shortest distance is finalized. This greedy property only holds with non-negative edge weights. Limitation: negative edge weights break Dijkstra. If an edge has weight -5, a path through it might be shorter than a previously finalized path. The greedy assumption fails. For graphs with negative weights (but no negative cycles), use Bellman-Ford: O(V * E). For negative cycles (where shortest path is undefined, as you can loop forever), Bellman-Ford detects them. Common interview variant: Dijkstra with constraints (cheapest flights within K stops) — modify the algorithm to track additional state (stops remaining)." } }, { "@type": "Question", "name": "How do you recognize that a problem is a graph problem when it does not mention graphs?", "acceptedAnswer": { "@type": "Answer", "text": "Many interview problems are graph problems in disguise. Recognition patterns: (1) Grid problems — a 2D grid where you move between adjacent cells is an implicit graph. Each cell is a node, edges connect adjacent cells (up, down, left, right). Number of islands, shortest path in a maze, and rotting oranges are all graph problems on grids. (2) Transformation problems — word ladder asks for the minimum transformations from one word to another. Each word is a node, edges connect words differing by one letter. This is BFS shortest path. (3) Dependency problems — course prerequisites, build dependencies, task scheduling. Each item is a node, dependencies are directed edges. This is topological sort. (4) Connectivity problems — are two accounts the same person? Group friends-of-friends. These are connected components, solvable with Union-Find or DFS. (5) State space problems — minimum moves to solve a puzzle (sliding puzzle, water jug). Each state is a node, valid moves are edges. BFS finds the minimum moves. The key insight: if the problem involves entities with relationships, and you need shortest path, connectivity, ordering, or reachability — it is a graph problem. Draw the graph (nodes and edges) on paper before writing code." } } ] }