Graphs: BFS, DFS, and Shortest Paths

Anything with entities and relationships is a graph: currencies and exchange rates, tasks and dependencies, positions and settlement chains. Graph questions decompose into a tiny toolkit — two traversals, one ordering, one shortest-path algorithm — plus the judgment of which to reach for.

Representation first

Adjacency list (dict[node] -> list[neighbors]): $O(V + E)$ space, the default. Adjacency matrix: $O(V^2)$, only for dense graphs or when you need $O(1)$ edge lookups. Saying which and why is the expected first sentence of any graph answer.

BFS: shortest paths in hops

Breadth-first search explores in rings using a queue, and therefore finds shortest paths in unweighted graphs — its defining superpower. $O(V + E)$.

Uses: fewest hops between nodes, word-ladder puzzles, "degrees of separation," and — the pattern worth internalizing — state-space search: the water-jug puzzle from classic brainteasers is BFS over states (jug contents) with moves as edges. Many puzzles that look clever are "BFS over the right state graph" once you name the states — the same state-definition skill as dynamic programming.

DFS: structure discovery

Depth-first search dives with a stack (or recursion). Same $O(V+E)$, different questions: connectivity and component counting ("number of islands"), cycle detection, and topological sort — ordering a DAG so every edge points forward.

Topological sort is the quietly practical one: build systems, dependency resolution, and settlement/obligation chains order by it; a cycle means "no valid order exists" — circular dependency, or in finance, a daisy chain of obligations with no clean unwind. Implementation either via DFS finish times or Kahn's algorithm (repeatedly remove zero-in-degree nodes); the latter is easier to narrate.

Weighted shortest paths: Dijkstra

When edges have costs, BFS breaks; Dijkstra fixes it by always expanding the cheapest known frontier node — a heap (the data-structures lesson again) gives $O((V+E)\log V)$. One hard constraint: no negative edges (greedy finality fails); Bellman-Ford ($O(VE)$) handles negatives and detects negative cycles — remember that fact, it's about to matter.

The quant question: currency arbitrage

"Given a table of FX rates, detect an arbitrage." Multiplying rates around a cycle > 1 means free money. Take $-\ln$ of each rate: multiplication becomes addition, and "product > 1" becomes a negative cycle — which Bellman-Ford detects in $O(VE)$. This is the single most-asked graph question at trading firms, because it composes three ideas (modeling, log transform, the right algorithm) and each is checkable. Rehearse saying it in three sentences.

Choosing fast

Question smells like…	Reach for
fewest steps, unweighted	BFS
connected? cycle? ordering?	DFS / topological sort
cheapest path, non-negative weights	Dijkstra + heap
negative weights or arbitrage cycles	Bellman-Ford
puzzle with configurations and moves	BFS over the state graph

The interview version

"Course prerequisites: can you finish all courses, and in what order?" — Model as a DAG, Kahn's algorithm, cycle ⇒ impossible: four sentences and an $O(V+E)$. "Cheapest way to route an order through venues with fees?" — Dijkstra, fees as weights, and state the no-negative-fee assumption out loud. Modeling — what are the nodes, what are the edges, what's the weight — is scored more heavily than the traversal itself; spend your first thirty seconds there.