Graphs — the universal data model

Three ways to represent a graph in code. Each makes different operations cheap.

One — adjacency list. A dict (or list of lists) mapping each node to its neighbours. graph[node] returns the list of neighbours. Memory O(V + E). Iteration over neighbours is fast. Edge existence check is O(degree). Default for sparse graphs (most real graphs).

Two — adjacency matrix. An n×n boolean (or weight) array. matrix[u][v] is true if there's an edge from u to v. Memory O(V²). Edge existence is O(1). Iteration over neighbours is O(V) — you scan the row. Useful when graphs are dense (close to n² edges) or you query edge existence frequently.

Three — edge list. A list of (u, v) pairs. Memory O(E). Iteration over all edges is fast. Iteration over neighbours of a single node is O(E) — slow. Useful for algorithms that process all edges (Kruskal's MST), almost never for traversal.

For the 99% of practical graph work — adjacency list, with defaultdict(list).

from collections import defaultdict

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)   # undirected

Now graph[node] is the neighbour list. Iteration is fast. Memory matches the actual edge count.

Real-world graphs are almost always sparse. Social networks have average degree maybe 200, on networks of millions of users — way fewer than V² edges. Adjacency list is right.

The rare cases for matrix — small dense graphs (V < 1000), all-pairs shortest paths algorithms (Floyd-Warshall), or when edge-existence queries dominate. Otherwise adjacency list.

Learn one rep well. Most algorithms (BFS, DFS, Dijkstra, topological sort) work directly on adjacency lists.

Here's a beautiful property of breadth-first search — on an unweighted graph (or a graph where all edges have the same weight), BFS finds the shortest path from source to every reachable node.

Why? BFS uses a queue. Nodes leave the queue in distance-from-source order, because each node enters the queue when it's first reached, and 'first reached' means 'shortest distance found'. The first time you reach a node is via the shortest path.

Proof sketch — when BFS pops a node u at distance d, every node at distance < d has already been popped. Every neighbour of u is at distance ≤ d+1. They're added to the queue if not seen. The next pop is at distance d or d+1. Distance never decreases as you pop. When you reach the target node, you've reached it via the shortest path.

For weighted graphs (different edge costs), BFS doesn't work. Counterexample — if edge AB has cost 5 and edge AC has cost 1 and edge CB has cost 1, BFS reaches B in 1 hop via the direct edge (cost 5), but the actual shortest path A→C→B has cost 2. Two hops, but cheaper.

For weighted graphs, you need Dijkstra (next post — same shape as BFS, but with a min-heap instead of a queue).

The practical recipe. Got 'find shortest path / fewest steps / minimum hops' on an unweighted graph or grid? Use BFS. Add a 'distance' dict to track distances; add a 'parent' dict to reconstruct the path.

Grid problems are unweighted graphs in disguise. Each cell is a node; cardinal neighbours are edges. Maze solvers, num-islands, knight's tour, word ladder — all BFS on a graph constructed from the input.

The BFS template from Day 20 is the implementation. The shortest-path application is the most important payoff.

Dijkstra finds the shortest path from a source to every reachable node in a graph with non-negative edge weights. Generalisation of BFS — the queue becomes a min-heap, sorted by distance from source.

The algorithm:

1. dist[src] = 0; all others = infinity.
2. Min-heap holds (distance, node) pairs. Start with (0, src).
3. Pop the smallest-distance node u. If you've already found a shorter path, skip.
4. For each neighbour v of u, the candidate distance is dist[u] + weight(u,v). If shorter than dist[v], update dist[v] and push (new_dist, v) onto the heap.
5. Repeat.

Look at the snippet. dist tracks current shortest distances. pq is the min-heap (Python's heapq is a min-heap by default). The 'if d > dist[u]: continue' line skips stale entries — the heap may contain old (longer) distance entries from before we found shorter routes.

Complexity — O((V + E) log V) with a binary heap. For sparse graphs, this is dramatically faster than the matrix-based Dijkstra (O(V²)).

Where it's used:

Map routing. Edges are roads with travel time as weights. Source is your location; destination is the target. Standard implementation in Google Maps, OpenStreetMap routing engines.

Network routing protocols. Edges are network links with latency or hop counts as weights.

Event-driven simulations where 'cheapest event next' drives the schedule.

Dependencies between tasks where some take longer than others.

Dijkstra requires non-negative edge weights. For graphs with negative edges, use Bellman-Ford (slower, O(VE)). For all-pairs shortest paths on dense graphs, Floyd-Warshall (O(V³)).

For 95% of weighted shortest-path problems, Dijkstra is the answer.

When you have tasks with dependencies (A must finish before B; B must finish before C; D depends on A; etc), topological sort gives you a valid execution order.

The Kahn's algorithm version is the cleanest:

1. Compute the in-degree of every node (number of incoming edges).
2. Find all nodes with in-degree 0. These have no dependencies; add them to a queue.
3. While the queue isn't empty: pop a node, add it to the output, decrement the in-degree of all its successors. If any successor's in-degree drops to 0, add it to the queue.
4. If the output contains all n nodes, you have a valid topological order. If not, there's a cycle in the graph — no valid order exists.

O(V + E). Linear in the graph size.

Where it's used:

Build systems. Make, Bazel, Cargo all topologically sort the dependency graph to decide compile order.

Package managers. pip, npm, apt resolve dependency order with topo sort.

Course scheduling. CS101 before CS201, CS201 before CS301 — toposort gives a valid order.

ML training pipelines. Feature pipeline → preprocessing → training → evaluation. Each stage depends on the previous; toposort handles arbitrary DAGs.

Spreadsheet recalculation. Cell A depends on cell B; topo-sort the dependency graph and recompute in order.

The cycle-detection property is also useful. If the algorithm can't finish (some nodes have in-degree > 0 at the end), there's a cycle. Detecting a cycle in a directed graph is exactly what 'fails to topologically sort' tells you.

DFS-based topo sort exists too — depth-first traversal, post-order, reversed. Same result, different style. Kahn's queue-based approach is usually clearer.

DAGs (directed acyclic graphs) are everywhere. Topo sort is the algorithm that orders them.

End of Day 26. Graphs done. The most-used data model in computer science.

What we covered.

Morning, the three graph representations and when to pick each. Adjacency list (default for sparse graphs). Matrix (dense graphs, O(1) edge check). Edge list (rare).

Midday, the beautiful BFS-on-unweighted-graphs property — first reached is shortest path. The BFS template from Day 20 becomes the shortest-path solver. Grid problems are graphs in disguise; they yield to BFS the same way.

Afternoon, Dijkstra in 16 lines. The weighted generalisation of BFS. Min-heap instead of queue; relax edges; non-negative weights required. Used everywhere — map routing, network protocols, event simulators.

Evening, topological sort with Kahn's algorithm. In-degree counting and queue-based processing. Used in build systems, package managers, course schedulers, ML pipelines. Cycle detection comes free.

A broader thought. Graphs are the most general structure on this list. Trees are graphs with restrictions. DAGs are graphs with restrictions. Linked lists are graphs with restrictions. Almost every relational data model is graph-shaped.

Mastering BFS, DFS, Dijkstra, and topo sort gives you the toolkit for most graph problems. Add a few specialised algorithms (MST with Kruskal/Prim for clustering and network design, max flow for assignment problems, Floyd-Warshall for small all-pairs) and you have professional-grade graph fluency.

Tomorrow, Day 27, dynamic programming. The single most-feared topic in DSA, and one of the most powerful tools when applied correctly. We make it less scary.

See you in the morning.