Graph Algorithms
A traversal to build on, then the orders, trees, flows, and ranks a graph yields: nodes peeled off in dependency order, the cheapest tree that touches every node, the most that fits through a network and the cut that limits it, and the fixed point of rank flowing along links.
Algorithms & Data Structures
Before you start
Some lessons here build on lessons from other arcs: Union-Find: Disjoint Sets, Heaps & Priority Queues.
- 1
Graph Traversal: BFS & DFSin progress
Algorithms · Graphs · ~20 minVisit every reachable node once with one loop and a frontier. Take from the front and it ripples out in layers; take from the back, marking nodes as they come off, and it plunges down a branch.
- 2
Topological Sortin review
Algorithms · Graphs · ~25 minOrder the nodes of a directed graph so every edge points forward: peel off nodes with nothing left pointing at them, or finish a depth-first walk and read it backwards.
- 3
Minimum Spanning Trees: Kruskal and Primin review
Algorithms · Graphs · ~25 minConnect every waypoint with the least total length: Kruskal takes edges cheapest first and skips any that close a cycle; Prim grows one tree from a start by its cheapest frontier edge.
- 4
Max Flowin review
Algorithms · Graphs · ~25 minPush as much as the pipes allow from source to sink: find a path with room, send its bottleneck, record how to undo it, repeat; the final blocked set is the minimum cut.
- 5
PageRankin review
Algorithms · Graphs · ~25 minA page is important if important pages link to it: rank flows along links each round, a damping share teleports anywhere, and the ranks settle to a fixed point no matter where they start.