Graph Algorithms: BFS, DFS, Shortest Paths

Part 16, Chapter 16: Algorithms and Complexity

Learning objectives

Represent graphs using adjacency lists and adjacency matrices, and compare trade-offs
Perform breadth-first search (BFS) and depth-first search (DFS) on a graph
Use BFS to find shortest paths in unweighted graphs
Use Dijkstra's algorithm for shortest paths in graphs with non-negative weights
Recognise structural results: connected components, topological sort, cycle detection

Graphs are the data structure of relationships, cities and roads, web pages and hyperlinks, atoms and bonds, neurons and synapses, friends and follows. The two foundational graph traversals (BFS and DFS) are the swiss-army knives of network analysis: they answer reachability, build trees, find shortest paths, detect cycles, sort dependencies, and identify components. Adding edge weights and a priority queue gives Dijkstra's shortest-path algorithm, the engine behind every GPS, every routing protocol, and every "social distance" computation on a network.

Representations

A graph $G = (V, E)$ has vertex set $V$ and edge set $E \subseteq V \times V$ . Edges are directed (the pair is ordered) or undirected. Two standard representations trade off space vs. lookup time:

Adjacency matrix: a $|V| \times |V|$ matrix $A$ with $A_{ij} = 1$ ij=1 iff $(i, j) \in E$ . Edge-lookup is $O(1)$ ; total space is $\Theta(|V|^{2})$ even for sparse graphs.
Adjacency list: each vertex stores a list of its neighbours. Total space is $\Theta(|V| + |E|)$ ; edge-lookup is $O(\deg(v))$ but iteration over neighbours is optimal.

For typical real-world graphs (sparse, $|E| = O(|V|)$ ) the adjacency list is the right default; for dense graphs ( $|E| = \Theta(|V|^{2})$ ) the matrix wins.

Breadth-first search (BFS)

BFS explores a graph level by level from a source vertex $s$ . Maintain a FIFO queue; initialise with $s$ ; repeatedly dequeue a vertex $v$ , mark it visited, and enqueue its unvisited neighbours. Running time is $O(|V| + |E|)$ with an adjacency list.

BFS produces the BFS tree, a spanning tree of the connected component of $s$ . Its key property: for every reachable vertex $v$ , the path from $s$ in the BFS tree is a SHORTEST path in the unweighted graph. So BFS solves the unweighted single-source-shortest-path problem in $O(|V| + |E|)$ , optimal, since you must at least read the graph.

Depth-first search (DFS)

DFS replaces the queue with a stack (or uses recursion). It explores AS DEEP as possible along each branch before backtracking. Running time is again $O(|V| + |E|)$ .

DFS shines on STRUCTURAL queries:

Connected components: repeated DFS from unvisited start vertices labels every component.
Cycle detection: in a directed graph, DFS finds a cycle iff it encounters a back-edge (an edge to an ancestor in the DFS tree).
Topological sort: in a DAG, ordering vertices by decreasing DFS finishing time gives a topological order, an ordering compatible with all dependencies. This is how build systems (make, Bazel) decide compile order.
Strongly connected components: Tarjan's and Kosaraju's algorithms use two DFS passes to find SCCs in $O(|V| + |E|)$ .

Dijkstra's algorithm

When edges carry non-negative weights $w(u, v) \geq 0$ , BFS no longer gives shortest paths. Dijkstra's algorithm generalises BFS using a PRIORITY QUEUE keyed by tentative distance. Start with $d(s) = 0$ and $d(v) = \infty$ for $v \neq s$ . Repeatedly extract the unvisited vertex $u$ of smallest $d(u)$ ; for each neighbour $v$ , relax: if $d(u) + w(u, v) < d(v)$ , update $d(v)$ .

With a binary-heap priority queue, total time is $O((|V| + |E|) \log |V|)$ . Why does it work? Because non-negative weights mean the first time we finalise $d(u)$ , no shorter path can later be discovered through any other unvisited vertex (their distances are all $\geq d(u)$ ).

For graphs with NEGATIVE edge weights, Dijkstra is incorrect. Use the slower Bellman-Ford algorithm ( $O(|V| \cdot |E|)$ ), which also detects negative-weight cycles. For all-pairs shortest paths on dense graphs, the Floyd-Warshall dynamic program runs in $O(|V|^{3})$ .

Where this shows up

GPS navigation and Google Maps: Every routing query is a shortest-path computation on a road graph. Production systems use highly optimised Dijkstra variants (A*, Contraction Hierarchies) that answer queries in microseconds across continental road networks.
Six degrees of Kevin Bacon: The "Bacon number" of an actor is the BFS distance from Kevin Bacon in the co-appearance graph of IMDb. Erdős numbers in the mathematics collaboration graph are the same construction. BFS computes these in linear time.
Compilers and build systems: Make, Bazel, and modern incremental compilers depend on topological sort of the file-dependency DAG to decide compile order. Detecting cyclic dependencies is structural cycle detection via DFS.
Social network analysis: Connected components identify "friend groups"; betweenness centrality (built on shortest paths) identifies bridge-people. PageRank itself is a fixed-point computation on the link graph.
Network routing protocols: OSPF (Open Shortest Path First) is Dijkstra running inside every router on the internet; each router maintains a shortest-path tree of the network to forward packets.

Pause and think: Why does BFS specifically (and not DFS) find shortest paths in unweighted graphs? Trace the queue ordering: when does a vertex get its FINAL $d$ value vs. its first $d$ value? (Hint: a vertex is dequeued exactly once, at distance equal to its BFS level.)

Try it

Draw the graph $V = \{A, B, C, D, E\}$ with edges $AB, BC, CD, DE, AC$ . Perform BFS from $A$ . What is the BFS tree? What are the shortest-path distances?
Same graph, perform DFS from $A$ visiting neighbours alphabetically. List the discovery and finish times for each vertex.
For the weighted graph $A \to B (3), A \to C (1), B \to D (2), C \to D (5), C \to B (1)$ , run Dijkstra from $A$ . Final distances?
Construct a small directed graph where DFS topological sort gives a valid order, and explain why BFS would not naturally produce a topological order.
What goes wrong if you run Dijkstra on a graph containing a single edge of weight $-1$ ? Construct a minimal counterexample.

A trap to watch for

It is tempting to apply Dijkstra to graphs with negative edge weights "to handle penalties." Dijkstra is incorrect on negative weights, the greedy choice "extract the closest unvisited vertex" assumes no future negative edge could undercut it, an assumption that fails the moment any edge is negative. Use Bellman-Ford for that case (or rewrite your problem so all weights are non-negative). Negative-weight CYCLES make shortest paths undefined (you can loop indefinitely to decrease total cost); Bellman-Ford detects them.

What you now know

You can pick the right graph representation, traverse with BFS/DFS in linear time, solve unweighted shortest paths with BFS and non-negative-weighted shortest paths with Dijkstra, and recognise the structural problems (topological sort, cycle detection, connected components) that DFS solves naturally. The next section turns to SORTING, another problem where the algorithmic toolkit and its complexity lower bound are foundational.

Mark section complete →

References

Garrity, T. (2002). All the Mathematics You Missed. Cambridge University Press, ch. 16.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press, ch. 22–25.
Sedgewick, R., Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley, ch. 4.
Tarjan, R. E. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing, 1(2): 146–160.
Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs." Numerische Mathematik, 1: 269–271.