Data Structures
Lessons · #9 of 11

Graphs

Vertices and edges — the universal abstraction

Graph · algorithms lab

Click any node to set start, then run BFS or DFS. The frontier panel renders as a queue for BFS and a stack for DFS — that single difference is what makes the two visit orders diverge.

frontier
visited (order) 
click a node, then bfs or dfs

Try it: Six modes, one demo. traverse: BFS vs DFS with the frontier visualized as a queue vs a stack — click any node to set start, then race both at once. shortest path: pick start + goal, compare Dijkstra to A* on a weighted graph. grid: paint walls, watch BFS plan around them. dag · topo: order a robot boot sequence; introduce a cycle and watch the algorithm refuse. pose graph: relax a drifted trajectory using a loop-closure constraint (toy SLAM). coverage: drop anchors, get a discrete Voronoi diagram.

Why it matters

Graphs model relationships: social networks, road maps, dependencies, state machines. BFS finds shortest paths, DFS explores all possibilities. Graphs are the universal language of connected data.

The idea

Think of a map of cities connected by roads. Each city is a vertex (node), each road is an edge (connection).

Graphs can be:

Two representations:

  1. Adjacency matrix: 2D array where matrix[i][j] = 1 if edge exists. Fast lookup O(1), but O(V^2) space.
  2. Adjacency list: Each vertex stores a list of its neighbors. Space-efficient O(V+E).

Two traversals:

Key takeaways

Going deeper

Topological sort — Kahn's algorithm and DFS-finish-times

A DAG (directed acyclic graph) represents dependencies. Topological sort linearizes the DAG so every edge u → v has u appearing before v in the output — i.e., every dependency comes before its dependents. Two algorithms, both O(V + E):

Kahn's algorithm (used in the demo's dag · topo mode):

1. Compute in-degree for every node.
2. Enqueue all nodes with in-degree 0 (no dependencies).
3. While the queue is non-empty:
     u = dequeue.  emit(u).
     For each edge u → v:
       in-degree[v] -= 1
       if in-degree[v] == 0: enqueue(v).
4. If emitted fewer than V nodes → the graph contains a cycle.

DFS-finish-time variant: run DFS from every unvisited node; when a node finishes (all its descendants explored), push it on a stack. Reverse-pop the stack to get topological order. This one extends naturally to find strongly connected components (Kosaraju's, Tarjan's) — applications include finding clusters in social graphs and analyzing program control flow.

Robotics use: ROS launch files form a DAG (each node has prerequisite nodes that must start first); the launch system does topological sort under the hood. Behavior trees and Make/Bazel build graphs are the same shape.

Bellman-Ford — Dijkstra's negative-weight cousin

Dijkstra assumes non-negative edge weights. Its correctness proof relies on the fact that once you pop a node from the priority queue with the minimum cost-so-far, no shorter path could possibly arrive later. Negative edges break that assumption — a long but cheap detour could shorten a "settled" path.

Bellman-Ford trades speed for the ability to handle negative weights:

For each of V−1 iterations:
  For each edge (u, v, w):
    if dist[u] + w < dist[v]: dist[v] = dist[u] + w

That's O(V·E) — way slower than Dijkstra's O((V+E) log V) with a heap. The payoff is correctness under negative weights, and the ability to detect negative cycles (a V-th iteration that still relaxes some edge means a cycle exists with total negative weight — your shortest path would loop forever).

When you need it: currency arbitrage detection, route planning with toll refunds / subsidies, anything where edges can be "discounts." Most robotics navigation uses only non-negative costs (distance, energy, time), so Dijkstra and A* dominate.

Minimum spanning tree (MST)

For a connected, undirected, weighted graph, an MST is the subset of V − 1 edges that connects all vertices with minimum total weight. Two classic algorithms, both O(E log V):

When you need it: road / cable / pipeline layout, clustering (single-link clustering = building an MST then cutting the largest edges), network design. For robotics multi-agent coordination, MST gives a minimum-communication tree spanning all robots.

Representation choices

Adjacency-matrix vs adjacency-list isn't just space. They have different sweet spots:

Most production graph libraries default to lists. The Graph struct in the shortest-path demo above uses adjacency lists keyed by node id.

Math details

Space Complexity
Adjacency Matrix: O(V^2)
Adjacency List: O(V + E)
Time Complexity
BFS/DFS: O(V + E)
Check edge (matrix): O(1)
Check edge (list): O(degree)

Implementation

Graph Representations

// Adjacency List
let mut graph: Vec<Vec<usize>> = vec![vec![]; n];
graph[0].push(1);  // Edge 0 -> 1
graph[1].push(0);  // Edge 1 -> 0 (undirected)

// BFS from vertex 0
let mut visited = vec![false; n];
let mut queue = VecDeque::from([0]);
while let Some(v) = queue.pop_front() {
    if visited[v] { continue; }
    visited[v] = true;
    for &neighbor in &graph[v] {
        queue.push_back(neighbor);
    }
}

Classic Algorithms

Practice

Three problems covering the three most-asked graph idioms:

→ Browse all practice problems