Graph Algorithms
The problem
Once data is modeled as a graph, real questions follow — what's reachable, what's the cheapest path, is there a cycle — and answering them by hand doesn't scale past a handful of nodes. Graph algorithms are the general-purpose machinery for answering these questions on graphs of any size.
Why now
Graph theory basics defined what a graph is and stated the key facts; stacks and queues supply the exact machinery (a stack for depth-first, a queue for breadth-first) those facts are computed with. This topic turns graph theory from something you reason about by hand into something a program executes.
Mental model
Depth-first search commits to one path and backtracks only when stuck — a stack, explicit or via recursion. Breadth-first search explores everything one step away before going further — a queue. Shortest-path algorithms (Dijkstra) are breadth-first search generalized to weighted edges: always expand the cheapest known frontier next.
Requires
- Graph Theory BasicsMathematical Thinking
Graph algorithms operate on the graph object (vertices, edges, directed/undirected) that graph theory basics defines; without that vocabulary there's nothing to write an algorithm over.
- Stacks & QueuesComputer Science Fundamentals
Depth-first and breadth-first search are defined by which structure holds the frontier of nodes to visit next — a stack for DFS, a queue for BFS — making this a direct prerequisite, not just useful context.
Helps
- TreesComputer Science Fundamentals
A tree is a special-case graph, and tree traversal is a special case of graph traversal; having built tree traversal first makes generalizing to graphs (which can have cycles) a smaller step.
Unlocks
Used in
- Dependency resolution (npm install, build systems) via topological sort
- Routing and navigation (shortest path algorithms)
- Social network 'people you may know' via graph traversal
- Network flow and capacity problems in infrastructure planning
Projects
- Implement BFS and DFS on an adjacency-list graph and use each to solve a different problem (BFS for shortest unweighted path, DFS for cycle detection)
- Implement topological sort and use it to compute a valid build order for a project with dependencies
Examples
- BFS from a starting page finds the fewest-click path to any other page in a website's link graph
- npm's dependency resolution is a topological sort over the package dependency DAG
Resources
Mastery checklist
- I can implement BFS and DFS on an adjacency list and explain when to use each
- I can implement topological sort and explain why it requires a DAG
- I can explain, at a high level, how Dijkstra's algorithm generalizes BFS to weighted edges
- I can model a real problem (routing, dependencies, reachability) as a graph algorithm