Graph Interview Questions With Answers for 2026

Graphs show up in almost every coding interview loop, and they trip up more candidates than any other data structure. The good news: most graph interview questions are variations on a handful of core patterns. Learn how to represent a graph, run a breadth-first or depth-first traversal, and recognize when a problem is really a shortest-path or cycle-detection question in disguise, and you can solve the large majority of what you'll be asked.

This guide walks through the graph coding interview questions that actually come up, grouped by topic, with short answers and the reasoning an interviewer wants to hear:

• Representations — adjacency list vs. adjacency matrix, and when to use each
• Traversal — BFS and DFS, the two workhorses
• Ordering — topological sort for dependency problems
• Shortest path — Dijkstra and its close cousins
• Cycle detection and union-find — the connectivity toolkit
• Common patterns and prep tips — how to recognize a graph problem fast

Here's a quick map of the algorithms before we dig in.

Graph representation questions

Almost every graph interview starts here, because your representation choice affects the complexity of everything after it.

Q: What are the two main ways to represent a graph?

An adjacency list stores, for each vertex, a list of its neighbors. An adjacency matrix stores a V × V grid where cell [i][j] marks whether an edge exists between vertices i and j.

Q: When do you pick one over the other?

Use an adjacency list for sparse graphs, which is most real-world cases. It uses O(V + E) space and lets you iterate a vertex's neighbors in time proportional to its degree. Use an adjacency matrix when the graph is dense or you need O(1) edge lookups, but be ready to pay O(V²) space. Here's the trade-off interviewers want you to name:

Q: How would you store a weighted graph?

In an adjacency list, store (neighbor, weight) pairs instead of bare neighbors. In a matrix, put the weight in the cell and use a sentinel (like infinity or zero) for "no edge." Mention that most interview problems hand you an edge list as input, and your first move is usually to build an adjacency list from it.

BFS and DFS traversal questions

These two traversals are the foundation. If you can implement both cleanly and explain when each wins, you'll handle most graph coding interview questions.

Q: How does BFS work and when should you use it?

Breadth-first search explores the graph level by level using a queue. It visits all nodes at the current distance before moving one step further. Because of that layer-by-layer order, BFS finds the shortest path measured in number of edges in an unweighted graph. Both time and space are O(V + E). Reach for BFS on grid shortest-path problems, level-order questions, and "minimum number of steps" prompts.

Q: How does DFS differ, and how is it usually implemented?

Depth-first search explores as far as possible down one branch before backtracking. It's typically written recursively (the call stack does the bookkeeping) or iteratively with an explicit stack. Same O(V + E) complexity. DFS is the natural fit for connectivity, cycle detection, topological sort, and any problem where you need to fully explore a path before evaluating it.

Q: What's the one bug interviewers watch for in graph traversal?

Forgetting the visited set. Graphs can have cycles, so without marking nodes as visited you'll loop forever. State out loud that you mark a node visited when you enqueue or first reach it, not after you process it, to avoid adding the same node twice.

Q: How do you count connected components?

Loop over every vertex. Each time you hit an unvisited one, run a full BFS or DFS from it and increment a counter. When the loop ends, the counter is the number of connected components. This same skeleton solves "number of islands" and "friend circles" style problems.

Topological sort questions

Any problem phrased as "you must do A before B" is a topological sort in disguise.

Q: What is a topological sort and what does it require?

A topological sort orders the vertices of a directed graph so that for every edge u → v, u comes before v. It only exists for a directed acyclic graph (DAG) — if there's a cycle, no valid ordering exists, which is exactly how you detect one.

Q: Describe the two standard approaches.

• Kahn's algorithm (BFS-based): compute each node's in-degree, start a queue with all zero-in-degree nodes, and repeatedly pop a node, add it to the output, and decrement its neighbors' in-degrees. If a neighbor drops to zero, enqueue it. If you can't output all V nodes, the graph has a cycle.
• DFS-based: run DFS, and prepend each node to the result after all its descendants finish. Reverse-postorder gives a valid topological order.

Both run in O(V + E). A classic prompt is "course schedule": given prerequisites, can you finish all courses? That's just asking whether the dependency graph is a DAG.

Shortest path and Dijkstra questions

Once edges carry weights, BFS is no longer enough, and this family of questions takes over.

Q: When can't you use BFS for shortest paths?

BFS assumes every edge costs the same (one step). The moment edges have different weights, BFS can return a path with fewer edges but a higher total cost. That's when you switch to Dijkstra's algorithm.

Q: How does Dijkstra's algorithm work?

Keep a distance estimate for every node, starting at zero for the source and infinity elsewhere. Repeatedly pull the unvisited node with the smallest known distance from a min-priority queue, then relax its edges — if going through that node gives a neighbor a shorter distance, update it. With a binary heap this runs in O(E + V log V). The catch interviewers listen for: Dijkstra requires non-negative edge weights. Negative edges break it.

Q: What if the graph has negative weights?

Name the alternative: Bellman-Ford handles negative edges in O(V·E) and can also detect negative cycles. For all-pairs shortest paths on a small dense graph, mention Floyd-Warshall at O(V³). You don't need to implement these live, but knowing when each applies signals depth.

Cycle detection and union-find questions

These questions test whether you understand graph connectivity, and union-find is the tool that surprises candidates who've never seen it.

Q: How do you detect a cycle in an undirected graph?

Run DFS and track the parent you came from. If you reach an already-visited node that isn't your parent, you've found a cycle. Alternatively, use union-find (below), which many interviewers prefer for its clarity.

Q: How does cycle detection differ for directed graphs?

You need to track nodes currently on the recursion stack, not just visited nodes. If DFS reaches a node that's still "in progress" (on the current path), there's a back edge and therefore a cycle. A node that's merely visited but already finished doesn't count.

Q: What is union-find and why is it useful here?

The disjoint-set (union-find) data structure tracks which elements belong to the same group with two operations: find (which group is this in?) and union (merge two groups). With path compression and union by rank, each operation runs in nearly constant amortized time — O(α(n)), where α is the inverse Ackermann function.

Q: How does union-find detect a cycle?

Process edges one at a time. For each edge (u, v), if find(u) already equals find(v), the two are already connected and adding the edge closes a cycle. Otherwise, union them. This is also the engine behind Kruskal's algorithm for minimum spanning trees, so mentioning that connection scores points.

Common patterns and prep tips

Recognizing the pattern fast is what separates candidates who freeze from candidates who ship a solution. Here's how to read a graph problem quickly.

• "Shortest / fewest steps," unweighted → BFS.
• "Explore all paths," "connected," "count regions" → DFS or union-find.
• "Order tasks," "prerequisites," "dependencies" → topological sort (and check for cycles).
• "Shortest path," weighted, non-negative → Dijkstra.
• "Are these connected," "does adding this edge form a cycle" → union-find.
• Grids are graphs. Treat each cell as a node with up-to-four neighbors; the same BFS/DFS templates apply.

A few prep tips that pay off:

1. Build the adjacency list first. Most problems hand you an edge list. Converting it is your reliable opening move, and doing it out loud buys thinking time.
2. Always mention the visited set before you write the loop. It's the single most common source of infinite loops.
3. State complexity in V and E, not "n." Interviewers specifically want O(V + E) for traversals.
4. Practice the templates until they're muscle memory. BFS with a queue, DFS with recursion, Dijkstra with a heap, union-find with path compression. Four templates cover most of the surface area.
5. Talk through the representation trade-off early. It shows you're thinking about complexity before you write code.

Frequently asked questions

What topics do graph data structure interview questions usually cover?

Representations (adjacency list and matrix), BFS and DFS traversal, topological sort, shortest-path algorithms like Dijkstra, cycle detection, and union-find. Most questions combine two or three of these rather than testing one in isolation.

Are graph questions harder than other coding interview questions?

They feel harder because there are more moving parts — you have to choose a representation, a traversal, and often an algorithm on top. But the underlying patterns are finite. Once BFS, DFS, and union-find are automatic, most graph problems become pattern-matching.

Do I need to memorize Dijkstra's algorithm exactly?

You should be able to implement it, but understanding matters more than memorizing. Know that it uses a min-priority queue, relaxes edges greedily, and only works with non-negative weights. If you can explain *why* it fails on negative edges, you understand it well enough.

How much graph practice is enough before an interview?

Aim to solve BFS, DFS, topological sort, cycle detection, and one Dijkstra problem cold, without looking anything up. If you can implement those five templates from scratch and explain their complexity, you're prepared for most graph coding interview questions you'll face.

Prepare for the interviewer, not just the whiteboard

Nailing graph interview questions gets you through the technical screen. What often decides the offer is how well you connect with the specific people interviewing you — the engineer who wrote the systems you'll touch, the manager who owns the roadmap. Knowing what they've built and what they care about lets you ask sharper questions and stand out.

If you're preparing for a loop, Articuler helps you find the actual hiring manager and interviewers behind a posting using semantic search across 980M+ profiles, then builds a Playbook on each person — their background, recent work, and common ground — so you walk in ready for *that* conversation, not a generic one. It's the layer that turns a solid whiteboard performance into a real connection.

For more interview prep, see our guides on coding interview questions, technical interview questions, software engineer interview questions, system design interview questions, and how to prep for the CodeSignal assessment.