What graph algorithms do I need to know for coding interviews?

The algorithms you need for the vast majority of graph interview questions: (1) BFS for shortest path in unweighted graphs and level-by-level exploration, (2) DFS for connected components, cycle detection, and topological sort, (3) Dijkstra's algorithm for shortest path in weighted graphs with non-negative weights, (4) Union-Find (Disjoint Set Union) for connectivity and cycle detection in undirected graphs, (5) Topological sort (Kahn's algorithm using BFS or DFS-based) for dependency ordering. Bellman-Ford and Floyd-Warshall appear rarely but are worth knowing for senior-level roles.

What are the most common graph question categories in interviews?

Based on real interview reports in LeakCode's database: (1) number of connected components or islands (BFS/DFS flood fill), (2) shortest path in a grid or graph (BFS), (3) cycle detection in directed or undirected graphs, (4) topological sort and course scheduling problems, (5) bipartite graph checking, (6) minimum spanning tree problems, and (7) Dijkstra-based shortest path with weighted edges. The first four categories cover over 70% of reported graph questions.

When should I use BFS vs DFS on a graph?

Use BFS when you need shortest path (fewest edges) in an unweighted graph, when you need level-by-level processing, or when you need to find the nearest node matching some criterion. Use DFS when you need to explore all possible paths (backtracking), detect cycles, compute connected components, or perform topological sort. For weighted shortest paths, use Dijkstra (priority queue + BFS) instead of plain BFS.

How do I represent a graph in code during an interview?

Adjacency list is almost always the right choice for interview problems. In Python, use a defaultdict(list) or dict of lists. In Java, use a HashMap with ArrayList values. Adjacency matrix (2D array) is only appropriate when the graph is dense (many edges relative to nodes) or when you need O(1) edge lookup. For grid-based problems, the grid itself is the implicit adjacency list: each cell connects to its 4 (or 8) neighbors.

How does LeakCode help with graph interview prep?

LeakCode aggregates 51,000+ real interview questions including graph problems from companies like Google, Amazon, Meta, and Microsoft. You can filter by topic and company to see which graph categories your target company has asked most in recent interview reports. This tells you whether to prioritize BFS/DFS basics or more advanced algorithms like Dijkstra and Union-Find for your specific target.

Graph Interview Questions: Complete Guide (2026)

Which graph algorithms and problem categories appear most at top companies, how to approach graph problems systematically, and how to use real data from LeakCode to prepare.

Why graph problems are critical for top-company interviews

Graphs are the most versatile data structure in computer science. They model networks, dependencies, geographic data, social connections, and state machines. Because of this breadth, graph problems appear at every level of the software engineering interview process at FAANG companies.

According to real interview reports in the LeakCode database, graph questions appear in approximately 20% of coding rounds at top tech companies. Amazon, Google, and Microsoft all ask graph problems at a high rate. At Amazon, graph problems often appear in disguise as dependency resolution, path finding in a warehouse context, or network connectivity problems.

The breadth of graph problems can feel overwhelming, but the same core algorithms handle the vast majority. LeakCode's data from 51,000+ real interview reports shows which categories are most common at each company, so you can prioritize effectively.

Core graph problem categories

Connected components and flood fill

Count or identify distinct connected regions in a grid or graph. The "number of islands" pattern. Solve with either BFS or DFS. Mark visited nodes to avoid cycles. The most commonly reported graph category in LeakCode's database, appearing across all levels and companies.

Shortest path in unweighted graphs

BFS gives the shortest path in terms of edge count in unweighted graphs. Common in grid problems where you want the minimum number of steps to reach a target, word ladder transformations, or social network distance. The key insight: BFS explores nodes level by level, so the first time you reach a node is via the shortest path.

Cycle detection

Detecting whether a directed or undirected graph contains a cycle. For undirected graphs, use Union-Find or DFS with a visited set. For directed graphs, use DFS with a "currently in recursion stack" set (three-color marking). Cycle detection underpins many dependency validation problems.

Topological sort

Ordering nodes in a directed acyclic graph such that every directed edge goes from earlier to later in the ordering. Solves course scheduling, build dependency ordering, and compilation sequencing problems. Know both Kahn's algorithm (BFS with in-degree tracking) and the DFS post-order approach.

Weighted shortest path (Dijkstra)

Dijkstra's algorithm finds the shortest path in a weighted graph with non-negative edge weights. Implemented with a min-heap (priority queue). Appears at Google and in senior-level rounds at other companies. Know the time complexity: O((V + E) log V) with a binary heap.

Union-Find (Disjoint Set Union)

Data structure for tracking connected components with near-O(1) union and find operations. Useful for Kruskal's minimum spanning tree, detecting cycles in undirected graphs, and grouping problems. Know path compression and union by rank optimizations.

Bipartite graph checking

Determine whether a graph can be 2-colored such that no two adjacent nodes have the same color. Equivalent to checking whether the graph contains no odd-length cycles. Solved with BFS or DFS, alternating colors. Appears in scheduling and matching problems.

How to represent a graph in interview code

Use an adjacency list for almost all interview problems. An adjacency list stores the graph as a map from each node to a list of its neighbors. This is O(V + E) space and gives O(degree) neighbor lookup, which is what BFS and DFS need.

For grid problems, you do not need to build an explicit graph. Treat each cell as a node and use the four directional neighbors as its edges. Keep a visited set or modify the grid in-place to mark visited cells.

Always track visited nodes in a set to avoid infinite loops in cyclic graphs. In BFS, add nodes to the visited set when they are enqueued, not when they are dequeued, to avoid redundant processing.

Search Graph Questions on LeakCode

LeakCode has 51,000+ real interview questions from 2,000+ companies. Filter by topic and company to see which graph algorithms your target company asks most.

Browse Graph Questions

How LeakCode helps with graph interview prep

LeakCode indexes real graph interview questions from 1Point3Acres, Blind, LeetCode Discuss, Glassdoor, and Reddit. Filter by company and topic to see which graph categories appear most in recent interview reports at your target company.

Graph algorithm patterns by interview frequency

BFS and DFS together cover roughly 60% of graph interview questions. BFS is the right reach for shortest-path-in-unweighted-graph, level-by-level processing, and finding the connected component containing a starting node. DFS is the right reach for cycle detection, topological sort, and counting connected components. Both run in O(V+E) on adjacency lists; the choice between them is usually stylistic except for shortest-path problems.

Topological sort (Kahn's algorithm or DFS post-order) is heavily probed in problems framed as "course schedule" or "task dependencies." Union-Find appears in dynamic connectivity problems, redundant connection detection, and minimum-spanning-tree variants. Dijkstra's algorithm with a min-heap handles weighted shortest paths. At L5+ levels, you may also see Bellman-Ford (negative weights) or A* (heuristic search) in specific domains like routing.

Common graph problem traps

The most frequent bug under pressure: not tracking visited nodes in BFS or DFS, causing infinite loops or exponential time blowup on cyclic graphs. Always initialize a visited set or array; mark nodes when you push (BFS) or when you enter (DFS). For trees specifically, you can skip the visited check, but for arbitrary graphs you cannot.

The second frequent bug: not handling disconnected components. If the problem asks about "all nodes" but you only start from a single node, you miss the disconnected components. The fix: wrap your BFS/DFS in an outer loop that starts from every unvisited node. Reports on LeakCode tag this as the most common edge-case failure at Google and Meta L4 graph rounds.