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.