Graph Interview Questions 2026

Why Graph Problems Are Frequent

Graph problems appear in 25% of coding interview questions based on LeakCode's data, making them the second most common topic after arrays. They appear frequently because graphs model real-world problems (social networks, maps, dependency systems) and require genuine algorithmic depth. Many problems that look like arrays or trees are actually graphs in disguise.

Google and Meta in particular are known for graph-heavy interviews. Meta candidates report graph problems in over 40% of their coding rounds.

Graph Representations

Know how to work with both adjacency lists and adjacency matrices. In interviews, adjacency lists (dict of lists) are almost always the right representation unless the problem gives you a dense matrix explicitly. Know how to build an adjacency list from an edge list in O(E) time, and how to check edge existence in O(1) with an adjacency matrix.

Grid graphs: a 2D grid is a graph where each cell is a node and edges connect to 4 (or 8) neighbors. BFS/DFS on grids uses the same logic as on explicit graphs. This is the most common form of graph problem in interviews because grids are visually intuitive.

Core Graph Patterns

BFS vs DFS: When to Use Which

Use BFS when: you need shortest path, you need to process nodes level by level, or the solution is near the source. Use DFS when: you are exploring all possibilities (permutations, combinations), you are doing topological sort, or you are detecting cycles. For connected components, both work and the choice is stylistic.

BFS uses a queue (deque in Python). DFS uses recursion or an explicit stack. Both have O(V+E) time complexity on adjacency lists. BFS uses O(V) space in the worst case for the queue. DFS uses O(V) space for the recursion stack (O(H) for balanced structures). On interview problems, state this complexity explicitly.

Topological Sort and Cycle Detection

Topological sort orders nodes of a DAG such that for every directed edge u -> v, u appears before v. Two standard algorithms: Kahn's (BFS with in-degree counting) and DFS-based (post-order with reverse). Both are O(V+E).

Course Schedule problems are the most common topological sort interview prompt. Variants: course schedule II (return the order), course schedule III (with deadlines, requires heap-based scheduling), parallel course schedule (BFS by levels for minimum semesters). Cycle detection on a directed graph: during DFS, maintain a "gray" set of nodes in the current path; finding a gray node again means a cycle. White-gray-black coloring is the classic formulation.

Shortest Path Algorithms

Unweighted graphs: BFS gives shortest path. Weighted graphs with non-negative weights: Dijkstra's algorithm with a min-heap, O((V+E) log V). Weighted graphs with negative edges (no negative cycles): Bellman-Ford O(VE). All-pairs shortest paths: Floyd-Warshall O(V^3).

Dijkstra implementation traps in interviews: forgetting to skip stale heap entries (the same node may appear multiple times with different priorities), not initializing distances to infinity correctly, and not handling the source-as-target edge case. Strong candidates write the boilerplate without thinking; weak candidates re-derive it under pressure. Practice the template enough to internalize it.

Union-Find for Connectivity Problems

Union-Find (Disjoint Set Union) supports two operations: find (which component is x in) and union (merge two components). With path compression and union by rank, both operations are amortized O(alpha(n)) where alpha is the inverse Ackermann function, effectively constant time.

Use cases: detect cycle in undirected graph, find connected components, minimum spanning tree (Kruskal's), redundant connection, accounts merge. Common interview probes: implement union-find from scratch in 5 minutes, optimize a naive O(n) find to O(alpha(n)) with path compression, solve "Number of Islands II" (dynamic connectivity).