Graphs and Traversals

A graph $G = (V, E)$ consists of vertices and edges. Directed graphs (digraphs) have ordered edges. A DAG (directed acyclic graph) has no cycles.

Representations:

• Adjacency matrix $A$ — $A_{ij} = 1$ if edge $(i,j)$ exists. $O(|V|^2)$ space, $O(1)$ edge lookup
• Adjacency list — each node stores its neighbors. $O(|V| + |E|)$ space, better for sparse graphs

Core traversals:

• BFS (Breadth-First Search) — explore level by level using a queue. $O(|V| + |E|)$. Gives shortest paths in unweighted graphs
• DFS (Depth-First Search) — explore as deep as possible using a stack/recursion. $O(|V| + |E|)$. Used for cycle detection, topological sort

Topological sort — linear ordering of a DAG such that every edge points forward. Found via DFS (reverse post-order). $O(|V| + |E|)$.

Where this appears in ML:

• Computation Graphs are DAGs — backpropagation does a reverse topological sort to compute gradients in the right order
• Graph Neural Networks (GNNs) — message passing on graph structure: each node aggregates features from neighbors
• Knowledge graphs — structured representations for reasoning and retrieval
• Pipeline DAGs — Airflow, Kubeflow, and training pipelines are DAGs of dependent stages
• Tree search — Monte Carlo Tree Search (MCTS) for AlphaGo, reasoning in LLMs (Test-Time Compute)
• Attention as a graph — self-attention is a weighted complete graph over tokens; sparse attention prunes edges

See also: Computation Graphs, Dynamic Programming, Big-O and Complexity Analysis