In this article
Representation and basics
For the method behind these answers, and how to practise them, see the coding interview guide. The illustrative numbers quoted in the answers were computed by a short script.1
What is a graph, and how do you store one?
A graph is a set of vertices and a collection of edges that each connect a pair of vertices (Sedgewick and Wayne, Algorithms, 4th edition). Write V for the number of vertices and E for the number of edges. An adjacency list is a vertex-indexed array of lists, each holding the neighbours of one vertex, and it is the usual way to store a graph. In Python a dictionary from vertex to list does the job, and defaultdict saves the key-exists check.
Why it is asked: it checks that you can turn cities and roads, or courses and prerequisites, into vertices and edges. Read the full explanation: Algorithms, 4th edition, undirected graphs.
What is the difference between an adjacency list and an adjacency matrix?
An adjacency matrix is a table with one row and one column per vertex, where each cell says whether an edge joins the pair. It answers an edge query in constant time but needs V squared space. Adjacency lists use space proportional to V plus E (Princeton Graph documentation), and asking whether an edge exists costs the outdegree of the vertex (Sedgewick and Wayne lecture slides, 2011).
Text description of the diagram
- An adjacency matrix answers an edge query in constant time but needs V squared space.
- Adjacency lists use space proportional to V plus E.
Why it is asked: the choice shows whether you reason about cost, not only correctness. Read the full explanation: Princeton Graph documentation.
When should you use a matrix instead of lists?
Sedgewick and Wayne advise adjacency lists in practice, because real graphs have a huge number of vertices and a small average degree (lecture slides, 2011). With 1,000 vertices and 2,000 directed edges, lists hold 3,000 entries while a matrix has 1,000,000 cells.1 Choose a matrix for a small or dense graph, or when you need constant-time edge lookups.
Why it is asked: it tests whether you size a structure before choosing it. Read the full explanation: lecture slides, representations.
How is a tree related to a graph?
A tree is a connected graph with no cycles, so every tree problem is a graph problem with extra structure. Because a tree has exactly one path between two vertices, you can walk parent links instead of keeping a visited set. Questions such as finding the lowest common ancestor use that structure directly.
Why it is asked: it shows you can move between the two models. Read the full explanation: lowest common ancestor of a binary tree.
How do you treat a grid or matrix problem as a graph?
A grid is an implicit graph: each cell is a vertex, and its edges go to the neighbouring cells above, below, left and right that lie inside the grid. You never build a list. Run breadth-first or depth-first search from a cell and keep a visited set, so counting connected regions becomes repeated traversal from each unvisited cell.
Why it is asked: it checks that you spot a graph that the statement never calls one. Read the full explanation: Algorithms, 4th edition, undirected graphs.
Traversal: breadth-first and depth-first search
How does breadth-first search work?
Breadth-first search (BFS) is a traversal that visits vertices in order of their edge distance from a start vertex. It keeps a first in, first out (FIFO) queue of vertices that are marked but whose adjacency lists have not been checked (Sedgewick and Wayne). Remove a vertex, mark and enqueue each unmarked neighbour, and repeat until the queue is empty. On an illustrative graph with edges A-B, A-C, B-D, C-D and D-E, starting at A visits A, B, C, D, E.1
Why it is asked: the queue discipline is the whole idea. Read the full explanation: Algorithms, 4th edition, undirected graphs.
How does depth-first search work?
Depth-first search (DFS) is a traversal that follows one path as far as it can before backing up. It finds some path from a source to a target, not necessarily the shortest (Sedgewick and Wayne). Recursion keeps the path on the call stack, so an explicit stack is optional, though an explicit one avoids deep-recursion limits on long chains. It marks every vertex connected to the source in time proportional to the sum of their degrees (Sedgewick and Wayne, section 4.1).
Why it is asked: depth-first search underlies cycle detection and ordering. Read the full explanation: Algorithms, 4th edition, undirected graphs.
What is the time complexity of BFS and DFS?
With adjacency lists both visit each vertex once and scan each list once, so they take O(V + E) time; the lists themselves use Θ(E + V) space (Princeton Graph documentation). With a matrix, finding the neighbours of a vertex scans a row of V cells, so a full traversal costs V squared. For 1,000 vertices that is 1,000,000 cell checks, against 3,000 list entries for 2,000 directed edges.1
Why it is asked: it checks whether you can derive a bound, not recite it. Read the full explanation: Princeton Graph documentation.
When do you use BFS and when DFS?
Use BFS when you need the fewest edges in an unweighted graph, because it explores level by level. Use DFS when you need to explore everything or follow a path to its end. Path existence and connected components work equally well with either search; DFS is the natural fit for detecting cycles and producing a topological order. Both cost the same on lists, so choose by the property you need.
Why it is asked: it shows you choose a tool by property, not habit. Read the full explanation: what is topological sort.
How do you find the shortest path in an unweighted graph?
Run BFS from the source and record each vertex's parent when you first mark it. The first time BFS reaches a vertex is by the fewest edges, which is the shortest path when every edge counts the same (Sedgewick and Wayne). In the illustrative graph above, E is reached from A in three edges.1 Follow parents back from the target to rebuild the path.
Why it is asked: it is the standard use of BFS. Read the full explanation: Algorithms, 4th edition, undirected graphs.
Why does BFS not give shortest paths in a weighted graph?
BFS counts edges, not total cost, so it ignores weights. In Stanford's Programming Abstractions lecture (CS106B) example, going from A to H directly is one edge but costs more, while A to I to G to H costs 6 (Stanford CS106B, August 2025). BFS would prefer the direct edge because it is one step. Use Dijkstra's algorithm when weights are non-negative.
Why it is asked: it separates "shortest" meaning edges from "shortest" meaning cost. Read the full explanation: Stanford CS106B, Dijkstra and A*.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Shortest paths with weights
How does Dijkstra's algorithm work, and what does it cost?
Dijkstra's algorithm finds shortest paths in weighted graphs (Stanford CS106B, August 2025). It repeatedly takes the unsettled vertex with the smallest known distance, settles it, and updates its neighbours. With a binary heap it takes time proportional to E log V in the worst case (Sedgewick and Wayne, section 4.4), and it is correct only for non-negative weights. A heap is the usual priority queue; see heap-based selection.
Why it is asked: it tests the greedy argument and the data structure behind it. Read the full explanation: Stanford CS106B, Dijkstra and A*.
Why does Dijkstra fail with negative edge weights?
Dijkstra settles a vertex when it is the closest unsettled one, assuming no later path can be cheaper, and a negative edge breaks that assumption: it does not work on graphs with negative edge weights (Stanford CS106B). In an illustrative graph with A to B costing 2, A to C costing 5 and C to B costing −4, Dijkstra settles B at 2 and never revisits it, but A to C to B costs 1.1
Why it is asked: it checks whether you know the precondition of the algorithm you name. Read the full explanation: Stanford CS106B, Dijkstra and A*.
Can you fix Dijkstra by adding a constant to every edge?
No. Adding a constant penalises paths with more edges more heavily, so the ranking of paths changes; Stanford's lecture shows this fix fails (Stanford CS106B). In the illustrative graph above, adding 4 to every edge makes the direct edge cost 6 and the route through C cost 9, though the route through C was cheaper before.1
Why it is asked: it catches the tempting shortcut. Read the full explanation: Stanford CS106B, Dijkstra and A*.
What does Bellman-Ford do, and what is a negative cycle?
Bellman-Ford handles negative edges as long as no negative-weight cycle is reachable from the source; it returns the distances or reports such a cycle, in time proportional to E times V in the worst case (Sedgewick and Wayne, section 4.4). A negative cycle is a loop of edges whose weights sum below zero, so going round it again lowers the cost without limit. A 2022 paper (version 6, May 2025) gives negative-weight shortest paths in near-linear time (Bernstein et al.). On the illustrative graph above, Bellman-Ford gives 1 for B.1
Why it is asked: it asks for the trade between speed and generality. Read the full explanation: Bernstein, Nanongkai and Wulff-Nilsen, arXiv 2203.03456.
What happens with a negative edge in an undirected graph?
One negative undirected edge acts as a negative cycle, because you can cross it back and forth and lower the cost each time (Stanford CS106B). So the shortest walk is unbounded, Dijkstra and Bellman-Ford cannot return distances through it, and Bellman-Ford reports the cycle instead of an answer.
Why it is asked: it tests whether you notice that undirected edges work in both directions. Read the full explanation: Stanford CS106B, Dijkstra and A*.
Ordering and cycles
What is topological sort, and when does it exist?
A topological sort lists the vertices of a directed graph so that every edge points from an earlier vertex to a later one. It exists only for a directed acyclic graph (DAG), meaning a directed graph with no cycle. The queue-based method (Kahn's algorithm) repeatedly removes vertices that have no incoming edges, and the depth-first method lists vertices in reverse order of finishing time (reverse postorder), which is a topological order for a DAG (Sedgewick and Wayne, section 4.2). Course prerequisites and build order are the usual examples.
Why it is asked: it tests dependency thinking. Read the full explanation: what is topological sort.
How do you detect a cycle in a directed graph?
Run depth-first search and track the vertices on the current path: an edge to a vertex that is still on the path closes a cycle. Alternatively, run Kahn's algorithm (see Sedgewick and Wayne, section 4.2); if it outputs fewer vertices than the graph has, the remainder lies on or behind a cycle. In an undirected graph, ignore the edge back to the parent.
Why it is asked: cycle detection is the check behind scheduling and dependency questions. Read the full explanation: how to detect a cycle in a directed graph.
Components, spanning trees and colouring
What is union-find, and when do you use it?
Union-find (also called disjoint-set) is a data structure that tracks which elements belong to the same set: union merges two sets and find reports which set an element is in (Sedgewick and Wayne, section 1.5). Use it for dynamic connectivity, where edges arrive one at a time and you ask whether two vertices are already connected. In an undirected graph, an edge whose endpoints are already connected closes a cycle.
Why it is asked: it is the standard tool for connectivity and for Kruskal's algorithm. Read the full explanation: Algorithms, 4th edition, union-find.
What is a minimum spanning tree, and how do Prim and Kruskal find one?
A minimum spanning tree of a connected, weighted, undirected graph is a set of edges that connects every vertex, has no cycle, and has the least total weight (Sedgewick and Wayne, section 4.3). Prim's algorithm grows one tree by repeatedly adding the cheapest edge that leaves it. Kruskal's algorithm considers edges from lightest to heaviest and keeps each one that does not close a cycle, which is where union-find is used.
Why it is asked: it tests greedy reasoning on graphs. Read the full explanation: Algorithms, 4th edition, minimum spanning trees.
How do you check whether a graph is bipartite?
A graph is bipartite if its vertices can be split into two groups so that every edge joins one group to the other. Test it with BFS or DFS two-colouring: give the start vertex one colour, give each neighbour the opposite colour, and stop with "not bipartite" if an edge joins two vertices of the same colour. Run the search from every unvisited vertex so that disconnected parts are checked too (Sedgewick and Wayne, section 4.1).
Why it is asked: it is a small traversal with one extra idea, carried state. Read the full explanation: Algorithms, 4th edition, undirected graphs.
Graphs and language models
What is graph RAG, and how does it differ from plain RAG?
Retrieval-augmented generation (RAG) gives a large language model (LLM) retrieved text when it answers. Most RAG uses vector similarity, which Microsoft calls baseline RAG. GraphRAG instead extracts a knowledge graph from raw text, builds a community hierarchy, writes summaries of the communities, and uses those structures to answer (Microsoft GraphRAG documentation).
Why it is asked: it checks whether you can say what the graph adds. Read the full explanation: Microsoft GraphRAG documentation.
Is GraphRAG just RAG on a graph database?
Not necessarily. "Graph RAG" is also used for retrieval over an existing knowledge graph. Microsoft's GraphRAG instead has an LLM build a graph-based text index from the source documents: first an entity knowledge graph, then pregenerated community summaries (Edge et al., 2024). Its documentation describes it as a structured, hierarchical approach to RAG, as opposed to plain text snippets.
Why it is asked: it separates storing a graph from constructing one. Read the full explanation: Edge et al., arXiv 2404.16130.
Follow-up questions
What are the common graph interview questions?
The twenty-three above cover the recurring ground: representation, breadth-first and depth-first search, shortest paths with and without weights, topological order and cycles, union-find, spanning trees and two-colouring. For the surrounding routine, see the coding interview guide.
What are graph RAG interview questions?
Expect to explain what a knowledge graph is, how it is extracted from text, why community summaries help, and how it differs from vector-similarity retrieval. A strong answer states one case where plain RAG is enough and one where the graph helps. The two graph RAG entries above give the base definitions.
How do I practise graph problems?
Write each traversal once from scratch, then solve problems that need it: a grid region count, a shortest path, a course order. Say the complexity aloud each time. Language tools matter too, so skim the Python interview questions for dictionaries, queues and sets.
Should depth-first search use recursion or an explicit stack?
Recursion is shorter and clear in an interview. In CPython the recursion limit is 1,000 by default, as read with undefined,1 so a recursive search on a chain of about that many vertices fails with RecursionError; switch to an explicit stack or raise the limit with sys.setrecursionlimit. State which you chose and why.
- A graph is vertices plus edges; adjacency lists use space proportional to V plus E, and a matrix needs V squared.
- BFS finds fewest-edge paths; DFS finds some path and powers cycle detection and ordering.
- Dijkstra needs non-negative weights; Bellman-Ford allows negatives but not a reachable negative cycle.
- Adding a constant to every edge does not repair Dijkstra.
- Microsoft's GraphRAG has an LLM build its graph from text, unlike vector-similarity RAG; the term is also used for retrieval over an existing knowledge graph.
- Union-find, spanning trees and two-colouring round out the recurring graph questions.
Sources
- Algorithms, 4th Edition, section 4.1 Undirected Graphs (Sedgewick and Wayne) — Princeton University booksite, 19 Mar 2011
- Graph class documentation, Algorithms 4th Edition (Javadoc) — Princeton University (Sedgewick and Wayne), 19 Mar 2011
- Algorithms, 4th Edition, section 4.2 Directed Graphs (Sedgewick and Wayne) — Princeton University booksite, 19 Mar 2011
- Algorithms, 4th Edition, section 4.4 Shortest Paths (Sedgewick and Wayne) — Princeton University booksite, 19 Mar 2011
- Algorithms, 4th Edition, section 1.5 Union-Find (Sedgewick and Wayne) — Princeton University booksite, 19 Mar 2011
- Algorithms, 4th Edition, section 4.3 Minimum Spanning Trees (Sedgewick and Wayne) — Princeton University booksite, 19 Mar 2011
- Directed graphs lecture slides, Algorithms 4th Edition — Sedgewick and Wayne (Boston University copy), 9 Nov 2011
- CS106B lecture 26: Dijkstra and A* shortest path algorithms — Stanford University, 7 Aug 2025
- Negative-Weight Single-Source Shortest Paths in Near-linear Time (arXiv 2203.03456v6) — arXiv (Bernstein, Nanongkai, Wulff-Nilsen), 20 May 2025
- From Local to Global: A Graph RAG Approach to Query-Focused Summarization (arXiv 2404.16130) — arXiv (Edge et al.), 24 Apr 2024
- GraphRAG documentation (live documentation, undated) — Microsoft, 26 Oct 2026
- sys.getrecursionlimit, Python standard library documentation (live documentation, undated) — Python Software Foundation, 26 Oct 2026
