Graph problems appear in 20% of coding interviews at top tech companies. The key challenge is recognizing that a problem IS a graph problem and choosing the right algorithm. This comprehensive guide organizes graph problems by algorithm, providing a decision framework for the most common interview questions.
Graph Problem Decision Framework
Match the problem type to the algorithm: (1) Shortest path, unweighted -> BFS. (2) Shortest path, weighted, non-negative -> Dijkstra. (3) Shortest path, negative weights -> Bellman-Ford. (4) All-pairs shortest path, small V -> Floyd-Warshall. (5) Connected components -> BFS/DFS or Union-Find. (6) Cycle detection, directed -> DFS with 3 states. (7) Cycle detection, undirected -> Union-Find or DFS with parent. (8) Dependency ordering -> Topological sort. (9) Minimum spanning tree -> Kruskal (Union-Find) or Prim. (10) Bipartite check -> BFS/DFS 2-coloring. Before coding: identify nodes and edges. Is the graph directed or undirected? Weighted or unweighted? Can there be cycles? Is the graph given explicitly (adjacency list) or implicitly (grid, state space)? These answers determine the algorithm.
BFS Problems: Shortest Path and Level-Order
BFS finds the shortest path in unweighted graphs (minimum edges). It explores level by level using a queue. Core 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. BFS from source to target. Build the graph on the fly: for each word, try all 26 substitutions per character. O(N * M * 26) where N=words, M=word length. Open the Lock: 4-digit combination lock, BFS from “0000” to target avoiding deadends. Each state has 8 neighbors (each digit +/- 1). Multi-source BFS: Rotting Oranges (all rotten oranges are sources), Walls and Gates (all gates are sources), 01 Matrix (all 0s are sources). Start BFS from ALL sources simultaneously. Each BFS level = one time step. Shortest Path in Binary Matrix: BFS with 8-directional movement. The first time target is reached = shortest path. State-space BFS: Sliding Puzzle (states are board configurations, edges are valid moves). BFS over the state space finds minimum moves.
DFS Problems: Traversal, Backtracking, and Components
DFS explores as deep as possible before backtracking. Use for: path finding, cycle detection, component counting, and exhaustive search. Number of Islands: DFS from each unvisited land cell, marking the entire island as visited. Count DFS starts = island count. Clone Graph: DFS with a hash map (original -> clone). For each node: create a clone, recurse on neighbors, set clone neighbors from the map. Course Schedule: cycle detection in a directed graph. DFS with 3 states (WHITE/GRAY/BLACK). GRAY -> GRAY = cycle. All Paths From Source to Target (DAG): DFS with path tracking. Since it is a DAG (no cycles), no visited check needed. Backtracking for paths: find all paths between two nodes. DFS with visited tracking. Add node to path, recurse, remove node (backtrack). Critical Connections in a Network: find bridges using Tarjan DFS (disc/low arrays). An edge (u,v) is a bridge if low[v] > disc[u]. Key insight: BFS = shortest path (level order). DFS = existence, components, cycles, exhaustive search.
Dijkstra Problems: Weighted Shortest Path
Dijkstra finds the shortest path in graphs with non-negative edge weights. Uses a min-heap (priority queue). Network Delay Time: find the time for a signal to reach all nodes from a source. Dijkstra from source. Answer: max distance to any node. If any node unreachable: -1. Path With Minimum Effort: grid problem. Edge weight = absolute height difference between cells. Dijkstra where “distance” = max effort along the path. Relax: new_effort = max(current, |height_diff|). Cheapest Flights Within K Stops: modified Dijkstra with state (cost, node, stops). Only explore if stops > 0. Track min cost per (node, stops) to prune. Swim in Rising Water: binary search + BFS, or Dijkstra where edge weight = max(grid[u], grid[v]). Implementation: heap of (distance, node). Pop minimum, relax neighbors. Skip already-finalized nodes. Time: O((V+E) log V). Common mistake: using Dijkstra with negative weights (breaks the greedy assumption — use Bellman-Ford instead).
Union-Find and Topological Sort Problems
Union-Find: for incremental connectivity and cycle detection. Number of Connected Components: process edges with union. Final count = initial nodes – successful unions. Redundant Connection: the first edge where find(u)==find(v) is the extra edge creating a cycle. Accounts Merge: union emails within each account. Group by root to merge accounts sharing emails. Kruskal MST: sort edges by weight, add if no cycle (Union-Find check). Topological Sort: order dependencies in a DAG. Course Schedule II: return a valid course ordering. Kahn BFS: process in-degree-0 nodes first. Alien Dictionary: extract character precedence from sorted word pairs, topological sort on the character graph. Parallel Courses: minimum semesters = number of BFS levels in Kahn algorithm (the critical path). When to use which: Union-Find when edges arrive incrementally and you only need connectivity (not paths). Topological sort when you need a valid ordering respecting dependencies. BFS/DFS when you need actual traversal or path information.
Hidden Graph Problems
Many problems are graphs in disguise: (1) Grid problems — each cell is a node, adjacent cells are edges. Number of Islands, Shortest Path in Grid, Rotting Oranges. (2) Transformation problems — each state is a node, valid moves are edges. Word Ladder, Open the Lock, Sliding Puzzle. BFS finds minimum transformations. (3) Dependency problems — items with prerequisites. Course Schedule, Build Order, Alien Dictionary. Topological sort. (4) Connectivity problems — grouping related items. Accounts Merge, Friend Circles, Redundant Connection. Union-Find. (5) Optimization on states — minimum cost to reach a goal state. Cheapest Flights, Swim in Rising Water. Dijkstra on the state graph. Recognition signals: “minimum steps/moves” = BFS. “order respecting dependencies” = topological sort. “are X and Y connected/grouped” = Union-Find. “minimum cost path” = Dijkstra. “find all connected groups” = DFS/BFS flood fill. When you identify the graph structure, the algorithm choice becomes clear.
{“@context”:”https://schema.org”,”@type”:”FAQPage”,”mainEntity”:[{“@type”:”Question”,”name”:”How do you decide which graph algorithm to use in a coding interview?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Match problem type to algorithm: Shortest path (unweighted) -> BFS. Shortest path (weighted, non-negative) -> Dijkstra. Shortest path (negative weights) -> Bellman-Ford. All-pairs shortest path (small V) -> Floyd-Warshall. Connected components -> BFS/DFS or Union-Find. Cycle detection (directed) -> DFS 3 states. Cycle detection (undirected) -> Union-Find. Dependency ordering -> Topological sort. Minimum spanning tree -> Kruskal or Prim. Bipartite check -> BFS/DFS 2-coloring. Before coding: identify nodes and edges, determine directed vs undirected, weighted vs unweighted, and whether cycles are possible. These properties determine the algorithm.”}},{“@type”:”Question”,”name”:”How do you recognize hidden graph problems in coding interviews?”,”acceptedAnswer”:{“@type”:”Answer”,”text”:”Many problems are graphs in disguise: (1) Grid problems — cells are nodes, adjacent cells are edges. Number of Islands, Shortest Path in Grid, Rotting Oranges. (2) Transformation problems — states are nodes, valid moves are edges. Word Ladder, Open the Lock, Sliding Puzzle. BFS finds minimum transformations. (3) Dependency problems — items with prerequisites. Course Schedule, Alien Dictionary. Topological sort. (4) Connectivity problems — grouping related items. Accounts Merge, Friend Circles. Union-Find. (5) Optimization on states — minimum cost to reach a goal. Cheapest Flights, Swim in Rising Water. Dijkstra. Recognition signals: minimum steps/moves = BFS. Order respecting dependencies = topological sort. Are X and Y connected? = Union-Find. Minimum cost path = Dijkstra. Find all groups = DFS/BFS flood fill.”}}]}