Graphs

Vocabulary, adjacency list vs matrix (sparse vs dense), and BFS vs DFS — when to use each.

A graph is just nodes connected by edges — the model for anything relational: social networks, road maps, dependency trees, web links, even the package manager resolving your node_modules. Almost everything you do with a graph reduces to two decisions: how to store it, and how to traverse it. Get those two right and the named algorithms (BFS, DFS, Dijkstra, topological sort) are just variations on a theme.

Vocabulary

Graphs come in flavors, and the flavor changes which algorithms apply. Edges can be directed (a one-way “follows” relationship) or undirected (a mutual “friends” link). Edges can be weighted (a road with a distance/cost) or unweighted (a plain connection). Get these right up front: BFS finds shortest paths only on unweighted graphs, and cycle detection means different things on directed vs undirected graphs. A directed graph with no cycles — a DAG — is the structure behind build systems, task schedulers, and spreadsheet recalculation, and is exactly what topological sort orders.

Storing a graph: list vs matrix

There are two standard representations, and the choice is almost entirely about density.

Representation	Use when	Avoid when	Costs
Adjacency list	sparse graph (most real graphs)	you need constant-time edge existence checks	space `O(V+E)`, edge lookup `O(degree)`
Adjacency matrix	dense graph; frequent “is there an edge?” checks	the graph is large and sparse	space `O(V²)`, edge lookup `O(1)`

Real-world graphs are usually sparse → default to an adjacency list.

An adjacency list stores, for each node, the list of its neighbors. It uses O(V + E) space — proportional to what actually exists — which is why it’s the default for the sparse graphs you meet in practice. An adjacency matrix is a V × V grid giving O(1) “is there an edge between i and j?” lookups, but it always costs O(V²) space even when almost empty. Use a matrix only when the graph is dense or you hammer edge-existence checks. For perspective: a social graph of a million users averaging 200 friends each is ~200M edges in a list, but a matrix would need 10¹² cells — a trillion — almost all of them zero.

FIG 1 · same graph, two representations Four nodes, four edges. The list stores only what exists (O(V+E)); the matrix reserves a cell for every possible pair (O(V²)).

BFS vs DFS

The two fundamental traversals differ in one thing: the order they visit nodes, set by their backing structure.

BFS (breadth-first) uses a queue and explores level by level — all neighbors, then their neighbors. Because it expands outward in rings, the first time it reaches a node is via the fewest edges, so BFS finds the shortest path in an unweighted graph. Use it for level-order traversal and “fewest hops” questions.

DFS (depth-first) uses a stack (or recursion) and plunges down one path before backtracking. It’s the natural fit for connectivity, cycle detection, and topological sort (ordering tasks by dependency).

FIG 2 · order of visitation From node 1: BFS fans out in rings (1 → 2,3 → 4,5,6); DFS dives down one branch first (1 → 2 → 4 → … then backtracks).

BFS for shortest hops

Find the minimum number of edges from start to every reachable node in an unweighted graph:

function bfs(graph, start) {
  const dist = new Map([[start, 0]]);
  const queue = [start];           // FIFO — the engine of "level by level"
  while (queue.length) {
    const node = queue.shift();    // (real code: use a deque/head index for O(1))
    for (const next of graph.get(node) ?? []) {
      if (!dist.has(next)) {       // first visit = shortest hop count
        dist.set(next, dist.get(node) + 1);
        queue.push(next);
      }
    }
  }
  return dist;
}

Swap the queue for a stack (or recurse) and the very same skeleton becomes DFS — the only change is which end you pull from. Both visit every node and edge once, so both are O(V + E) time.

DFS for cycle detection / topological sort

DFS shines when the order of completion matters. To detect a cycle in a directed graph (and, as a byproduct, produce a topological order), color each node white/grey/black: grey = on the current path. Hitting a grey node means an edge back into the path you’re still exploring — a cycle.

function hasCycle(graph) {
  const WHITE = 0, GREY = 1, BLACK = 2;
  const color = new Map();
  for (const v of graph.keys()) color.set(v, WHITE);

  function dfs(u) {
    color.set(u, GREY);                  // u is on the current path
    for (const v of graph.get(u) ?? []) {
      if (color.get(v) === GREY) return true;            // back-edge → cycle
      if (color.get(v) === WHITE && dfs(v)) return true;
    }
    color.set(u, BLACK);                 // u fully explored
    return false;
  }
  for (const v of graph.keys())
    if (color.get(v) === WHITE && dfs(v)) return true;
  return false;                          // O(V + E)
}

The same grey/black machinery, pushing nodes onto a list as they turn black and reversing it, gives a topological sort — the order your build system compiles modules or a scheduler runs dependent tasks.

Topological sort: two ways

A topological sort linearizes a DAG so every edge points forward — exactly what a build system, task scheduler, or course-prerequisite checker needs. There are two standard ways to produce one, and interviewers like that you know both:

DFS post-order (above): run DFS, and as each node turns black (fully explored) push it to a list; reverse the list at the end.
Kahn’s algorithm (queue-based): repeatedly take a node with in-degree 0 (nothing depends on it yet), emit it, and decrement its neighbors’ in-degrees. If you run out of zero-in-degree nodes before emitting everything, the leftover nodes form a cycle — so Kahn’s detects “this isn’t a DAG” for free.

function topoSort(graph) {              // graph: node -> [dependents]
  const indeg = new Map([...graph.keys()].map((v) => [v, 0]));
  for (const nbrs of graph.values()) for (const v of nbrs) indeg.set(v, indeg.get(v) + 1);
  const queue = [...indeg].filter(([, d]) => d === 0).map(([v]) => v);
  const order = [];
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (const v of graph.get(u) ?? []) if (--indeg.set(v, indeg.get(v) - 1).get(v) === 0) queue.push(v);
  }
  return order.length === indeg.size ? order : null;   // null = cycle (not a DAG)
}

Both are O(V + E). Reach for Kahn’s when you also want clean cycle detection or a “process as dependencies free up” model; reach for DFS when you’re already traversing.

Weighted shortest paths

BFS finds the fewest edges, but the moment edges have weights (distance, cost, latency) that’s the wrong answer — a 5-hop path can be cheaper than a 2-hop one. You need a shortest-path algorithm, and which one depends on the weights.

Algorithm	Handles	Cost	Reach for it when
Dijkstra	non-negative weights	`O((V+E) log V)` with a heap	the default weighted shortest path (maps, routing)
Bellman-Ford	negative weights; detects negative cycles	`O(V·E)`	weights can be negative (e.g. currency arbitrage)
A*	non-negative + a goal estimate	Dijkstra-ish, often far fewer nodes	point-to-point with a good heuristic (game/maps pathfinding)

BFS only works when every edge costs 1. With weights, pick by whether negatives are possible and whether you have one target.

Dijkstra is BFS with a priority queue instead of a plain queue (building directly on the heap from chapter 1.4): always expand the closest-so-far unvisited node, and relax each neighbor (update its best-known distance). Because it greedily locks in the nearest node each step, it breaks if a negative edge could later undercut a “finished” distance — hence non-negative only. Bellman-Ford trades speed for power: it relaxes every edge V−1 times, tolerates negative weights, and a final pass that still finds an improvement proves a negative cycle. A* is Dijkstra plus a heuristic h(n) estimating the remaining distance to the goal — with an admissible heuristic it finds the same shortest path while exploring far fewer nodes, which is why it powers game and map pathfinding.

Dependency resolution is graph traversal npm / package managers

Every time you run npm install, a graph algorithm runs under the hood: the dependency tree is a directed graph, and the installer must traverse it, detect cycles, and resolve a consistent set of versions. Early npm did this naively and produced deeply nested, duplicated trees that ballooned node_modules into millions of files — the famous “heaviest objects in the universe” meme — and traversals that were painfully slow on large projects.

The class of bugs here is pure graph theory: circular dependencies (A needs B needs A) are cycles that a traversal without a visited-set loops on forever; the fix is the same visited set this chapter insists on. The npm v5+ rewrite (and pnpm’s content-addressed store) reframed install as a smarter graph walk with deduplication and cycle handling — a reminder that “BFS/DFS with a visited set” isn’t academic, it’s what installs your code.

read the writeup ↗ blog.npmjs.org

01 Learning objectives

0 / 5 done

02 Knowledge check

knowledge check4 questions · pass ≥ 70%

01medium
For a SPARSE graph, which representation is more memory-efficient?
02medium
Shortest path in an UNWEIGHTED graph is found by:
03medium
Your weighted graph may have negative edge weights. Which shortest-path algorithm?
04medium
Kahn's algorithm for topological sort repeatedly removes nodes with…

03 Interview questions

browse all ↗

What gets asked on this topic — tap a card for how to approach it, the follow-ups, and the trap. Company tags are best-effort & sourced.

Commonly asked junior concept common Adjacency list vs adjacency matrix: compare space and edge-lookup cost, and say when to use each.
An adjacency list stores each node's neighbours, using O(V + E) space — efficient for sparse graphs, which is most real-world graphs. An adjacency matrix is a V x V grid giving O(1) edge-existence checks but O(V^2) space regardless of edge count, so it only pays off for dense graphs or when you constantly test specific edges. Default to the list unless the graph is dense.
Follow-ups they push on
- Which representation makes 'is there an edge u-v?' fastest?
Red flag Using a matrix for a large sparse graph and wasting O(V^2) memory on mostly-empty cells.
source: Tech Interview Handbook — Graph cheatsheet ↗
Commonly asked junior concept very common BFS vs DFS: how do they differ, and when do you pick each?
BFS explores level by level using a queue and finds the shortest path in an unweighted graph (fewest edges); DFS dives deep along one branch using recursion or an explicit stack and suits connectivity, cycle detection, and topological sort. BFS uses O(width) memory, DFS uses O(depth). Choose BFS when you need shortest hops or level order; choose DFS when you need to fully explore structure or order dependencies.
Follow-ups they push on
- Why does BFS, not DFS, give the shortest path in an unweighted graph?
- When does DFS risk a stack overflow?
Red flag Using DFS to find a shortest unweighted path, or forgetting a visited set and looping forever on cycles.
source: Tech Interview Handbook — Graph cheatsheet ↗
AmazonMetaGoogleMicrosoftBloomberg mid coding very common Count the number of islands in a grid of land ('1') and water ('0').
Scan every cell; when you hit unvisited land, increment the island count and flood-fill (BFS or DFS) all connected land, marking it visited so you don't recount it. The grid is an implicit graph where each cell connects to its 4 neighbours. O(rows * cols) time and space. The core insight is recognizing a 2D matrix as a graph traversal.
Follow-ups they push on
- How would you handle a grid too large to fit in memory?
- Count islands with diagonal connectivity.
Red flag Not marking visited cells (recounting the same island) or only checking diagonal instead of 4-directional neighbours.
source: LeetCode 200 — Number of Islands (company tags) ↗
AmazonMetaGoogleApple mid coding common Given course prerequisites, determine whether you can finish all courses.
Model courses as a directed graph and ask whether it has a cycle: if it does, the prerequisites are circular and you can't finish. Use Kahn's algorithm (BFS topological sort — repeatedly remove in-degree-0 nodes; if you can't remove them all, a cycle remains) or DFS cycle detection with a recursion-stack marker. O(V + E) time and space.
Follow-ups they push on
- Return a valid course ordering (Course Schedule II).
- BFS vs DFS for detecting the cycle?
Red flag Detecting a cycle with a simple visited set but no 'currently on the recursion stack' distinction, giving false positives.
source: LeetCode 207 — Course Schedule (company tags) ↗
Commonly asked mid concept common What is a topological sort, what graphs admit one, and how do you compute it?
A topological sort is a linear ordering of a directed graph's vertices where every edge u->v has u before v — it exists if and only if the graph is a DAG (no cycles). Compute it with Kahn's algorithm (repeatedly emit in-degree-0 nodes) or via DFS finish times reversed. It models dependency resolution: build systems, task scheduling, course prerequisites.
Follow-ups they push on
- How does the same algorithm also tell you the graph has a cycle?
Red flag Claiming any directed graph can be topologically sorted — cycles make it impossible.
source: AlgoMonster — Course Schedule (topological sort) ↗
Commonly asked mid concept common You need the shortest path in an unweighted graph. Which algorithm, and what changes if edges have weights?
Unweighted shortest path is plain BFS — the first time you reach a node is via the fewest edges, so it's optimal at O(V + E). With non-negative weights, BFS no longer works because fewer edges can cost more; switch to Dijkstra's algorithm, which uses a min-heap/priority queue to always expand the cheapest frontier node. The shift from a queue to a priority queue is the key recognition.
Follow-ups they push on
- Why does Dijkstra break with negative edge weights?
Red flag Reaching for Dijkstra on an unweighted graph (overkill) or using BFS when edges carry weights (wrong answer).
source: Tech Interview Handbook — Graph cheatsheet ↗
Commonly asked junior trick occasional Why must graph traversals track visited nodes, and what's the cost of forgetting?
Graphs can contain cycles and multiple paths to the same node, so without a visited set a traversal revisits nodes and, on a cycle, loops forever or explodes in work. A visited set makes both BFS and DFS O(V + E) by guaranteeing each node and edge is processed once. (Trees are the special case where you can skip it — they have no cycles.)
Follow-ups they push on
- Why is a visited set unnecessary when traversing a tree?
Red flag Copy-pasting tree-traversal code onto a graph and infinite-looping on the first cycle.
source: Tech Interview Handbook — Graph cheatsheet ↗
Commonly asked junior concept occasional Define directed vs undirected and weighted vs unweighted graphs, with an example of each.
In a directed graph edges have a direction (Twitter 'follows'); in an undirected graph they go both ways (Facebook 'friends'). Weighted edges carry a cost or distance (road network with mileage); unweighted edges just record a connection (a maze of equal steps). These two axes determine your algorithm choice — e.g. unweighted shortest path uses BFS, weighted uses Dijkstra.
Follow-ups they push on
- How does each property change which traversal/shortest-path algorithm you pick?
Red flag Modelling a one-way relationship (like 'follows') as an undirected edge and corrupting the graph's meaning.
source: Tech Interview Handbook — Graph cheatsheet ↗
AmazonMetaGoogleBloomberg mid coding common Make a deep copy (clone) of a connected undirected graph.
Traverse with BFS or DFS while keeping a hash map from original node to its clone. When you first see a node, create its clone and record it; then for each neighbor, create-or-look-up its clone and wire up the edge. The map serves double duty as both the visited set and the original→copy lookup, which is what prevents infinite loops on cycles. O(V + E) time and space.
What a strong answer covers
- Map original → clone doubles as the visited set.
- Create a clone on first sight; reuse the mapped clone afterward.
- Wire each neighbor edge using looked-up clones.
- O(V + E) time and space; works via BFS or DFS.
Follow-ups they push on
- Why does the original→clone map prevent infinite recursion on cycles?
- How does this change for a directed graph?
Red flag Cloning a neighbor again instead of reusing the mapped clone, producing duplicate nodes and looping on cycles.
source: LeetCode 133 — Clone Graph (company tags) ↗
★ must-know Commonly asked mid concept common What is union-find (disjoint set union), and what do union by rank and path compression buy you?
Union-find tracks elements partitioned into disjoint sets via a parent-pointer forest, supporting find (which set/root an element belongs to) and union (merge two sets). Path compression flattens the tree by pointing visited nodes straight at the root during find, and union by rank/size always attaches the smaller tree under the larger; together they make each operation nearly O(1) — amortized O(α(n)), the inverse-Ackermann function, effectively constant. It's the tool for dynamic connectivity, counting connected components, cycle detection in undirected graphs, and Kruskal's MST.
What a strong answer covers
- Forest of parent pointers; find returns the set root, union merges.
- Path compression: repoint nodes to the root during find.
- Union by rank/size: attach smaller tree under larger.
- Together ⇒ amortized O(α(n)) ≈ constant per operation.
Quick self-check
With both path compression and union by rank, the amortized cost per operation is:
Follow-ups they push on
- Why is union-find better than BFS/DFS for *dynamic* connectivity queries?
- How does Kruskal's algorithm use union-find?
Red flag Implementing find/union without either optimization, degrading to O(n) per op on adversarial unions.
source: GeeksforGeeks — Disjoint Set (Union-Find) with Rank & Path Compression ↗
AmazonGoogleMeta mid coding common Count the number of connected components in an undirected graph. Two ways?
Way 1 — traversal: loop over all nodes; each time you hit an unvisited node, increment the count and BFS/DFS to mark its whole component visited. O(V + E). Way 2 — union-find: start with V components and union the endpoints of every edge; each successful merge of two distinct sets drops the count by one. O(E·α(V)). Union-find shines when edges arrive incrementally or you also need connectivity queries; traversal is simplest for a static graph.
What a strong answer covers
- Traversal: count = number of BFS/DFS launches from unvisited nodes.
- Union-find: start at V, decrement on each cross-set union.
- Both are near-linear: O(V + E) vs O(E·α(V)).
- Prefer union-find for streaming edges / repeated connectivity queries.
Follow-ups they push on
- Which approach fits a stream of edges arriving over time, and why?
- How would you also report the size of the largest component?
Red flag Forgetting isolated (degree-0) vertices, which are components of their own and easy to miss.
source: LeetCode 323 — Number of Connected Components in an Undirected Graph (company tags) ↗
Commonly asked mid concept common How does Dijkstra's algorithm work, and why does it break with negative edge weights?
Dijkstra greedily grows a set of finalized shortest distances: a min-heap repeatedly pops the closest unfinalized node, finalizes its distance, and relaxes its outgoing edges. With a binary heap it's O((V + E) log V). It relies on the assumption that once you finalize a node, no later path can be shorter — true only with non-negative weights. A negative edge can make a 'longer-looking' path actually cheaper after the node is already finalized, breaking correctness; for negative edges use Bellman-Ford (O(V·E)), which also detects negative cycles.
What a strong answer covers
- Min-heap pops the nearest unfinalized node, then relaxes its edges.
- O((V + E) log V) with a binary heap.
- Correct only because finalized nodes can't be improved — needs non-negative weights.
- Negative edges ⇒ use Bellman-Ford (O(V·E)), which finds negative cycles.
Quick self-check
Why does Dijkstra fail on graphs with negative edge weights?
Follow-ups they push on
- What does Bellman-Ford do that Dijkstra can't?
- How does A* differ from Dijkstra?
Red flag Running Dijkstra on a graph with negative edges and trusting the (silently wrong) result.
source: Tech Interview Handbook — Graph cheatsheet ↗
AmazonGoogleMetaLinkedIn senior coding occasional Find the length of the shortest word transformation from beginWord to endWord changing one letter at a time (Word Ladder).
Model each word as a graph node with edges to words differing by one letter, then run BFS from beginWord — the first time you reach endWord, the BFS depth is the shortest transformation length (unweighted shortest path). To find neighbors efficiently, use wildcard patterns like h*t as buckets so you don't compare every pair of words. BFS guarantees the shortest sequence; bidirectional BFS from both ends prunes the frontier and is a strong optimization to mention.
What a strong answer covers
- Words are nodes; one-letter-apart words are edges ⇒ unweighted graph.
- BFS gives the shortest transformation (fewest steps).
- Wildcard buckets (h*t) generate neighbors without all-pairs comparison.
- Bidirectional BFS searches from both ends to cut the explored frontier.
Follow-ups they push on
- Why BFS rather than DFS for the *shortest* sequence?
- How does bidirectional BFS reduce the work?
Red flag Using DFS (finds *a* path, not the shortest) or comparing all word pairs (O(N^2·L)) to build edges.
source: LeetCode 127 — Word Ladder (company tags) ↗
Commonly asked mid concept common How do you detect a cycle in a graph, and why does the method differ between directed and undirected graphs?
In an undirected graph, DFS finds a cycle if it reaches an already-visited node that isn't the immediate parent (or union-find: an edge joining two nodes already in the same set). In a directed graph a plain visited set is insufficient — you must track nodes currently on the recursion stack (often three colors: white/unvisited, gray/in-progress, black/done); a back edge to a gray node means a cycle. The difference is that in directed graphs revisiting a finished node is fine (it's just a shared descendant), whereas an edge back to an *in-progress* ancestor is the cycle.
What a strong answer covers
- Undirected: visited neighbor that isn't the parent ⇒ cycle (or union-find).
- Directed: need a recursion-stack / gray marker, not just visited.
- Back edge to a gray (in-progress) node ⇒ directed cycle.
- Revisiting a finished (black) node in a digraph is not a cycle.
Quick self-check
Detecting a cycle in a DIRECTED graph requires tracking which of these beyond a visited set?
Follow-ups they push on
- Why isn't a simple visited set enough for directed cycle detection?
- How does topological sort also reveal a directed cycle?
Red flag Reusing the undirected approach (plain visited set) on a directed graph and reporting false cycles.
source: GeeksforGeeks — Detect Cycle in a Directed Graph ↗
AmazonMetaGoogleApple mid coding common Given a directed acyclic dependency graph, produce a valid build/task order (topological ordering via Kahn's algorithm).
Compute every node's in-degree, seed a queue with all in-degree-0 nodes (no dependencies), then repeatedly dequeue a node, append it to the order, and decrement its neighbors' in-degrees — enqueuing any that hit zero. O(V + E). If the emitted order contains fewer than V nodes, a cycle exists and no valid ordering is possible, so the same algorithm doubles as cycle detection. This is exactly Course Schedule II / dependency resolution.
What a strong answer covers
- Kahn's: start from in-degree-0 nodes, peel them off layer by layer.
- Decrement neighbors' in-degrees; enqueue when they reach 0.
- O(V + E) time and space.
- Output size < V ⇒ a cycle ⇒ no valid ordering.
Follow-ups they push on
- How does the same run tell you the graph has a cycle?
- How would you produce *all* valid topological orders?
Red flag Assuming an ordering always exists and not checking for the cycle case (output shorter than V).
source: LeetCode 210 — Course Schedule II (company tags) ↗