Graphs: BFS, DFS and Shortest Paths

A graph is a set of $V$ nodes joined by $E$ edges. Edges can be directed (job A must run before job B) or undirected (stock A is correlated with stock B), and they can carry weights (latency, cost, a log exchange rate).

There are two standard ways to hold one in memory. An adjacency matrix is a $V \times V$ table where entry $(i, j)$ says whether an edge exists. It answers "are $i$ and $j$ connected?" in $O(1)$ but costs $O(V^2)$ memory, and listing a node's neighbors takes $O(V)$. An adjacency list stores, for each node, only the nodes it touches. Memory is $O(V + E)$ and looping over neighbors costs only as much as there are neighbors.

Take 3,000 stocks where each name has a correlation above 0.7 with about 20 others. That is roughly $3000 \cdot 20 / 2 = 30{,}000$ undirected edges. The list stores each edge twice, so 60,000 entries. The matrix stores $3000^2 = 9{,}000{,}000$ cells, almost all of them zero.

In Python the list is a dict mapping each node to a list of neighbors, or of (neighbor, weight) pairs. Use it by default. Reach for the matrix when the graph is dense or arrives as one, such as a correlation matrix.

BFS and DFS below visit each node once and look at each edge once in a directed graph or twice in an undirected one, which is where their $O(V + E)$ bound comes from.