The question this module answers: what is connected to what, and how far apart? A graph is a set of nodes (vertices) and edges between pairs of them. Edges can be directed (a → b only) or undirected, and can carry weights (a distance, a cost, a latency). Trees (module 10) are graphs with no cycles; grids are graphs where each cell connects to its neighbours.
ML context.
- Computation graphs: autograd records operations as a directed acyclic graph and runs backward in reverse topological order (lessons 11.6 and 11.14).
- Pipelines and schedulers: Airflow DAGs, build systems and data dependencies are graphs to order and check for cycles.
- Data as graphs: user-item interactions, knowledge graphs, citation networks, near-duplicate records (lessons 11.15 and 11.16); graph neural networks aggregate over neighbourhoods.
- Search: shortest routes, fewest edits between words (lesson 11.12), state spaces of planners.
1. The problem: which nodes can I reach?
Task: given V nodes and a list of E directed edges, return every node reachable from a start node.
The most direct approach keeps a reached set and rescans the whole edge list each round, adding the endpoints of any edge that leaves the set, until a round adds nothing.