Graph

Traverse, connect, and find the cheapest paths through networks of nodes and edges.

Concepts

Explore as far as possible down one path before backtracking, used to walk trees, graphs, and grids.

Explore level by level from a starting point, the go-to way to find the shortest path in an unweighted graph.

Find the shortest path from a starting node to every other node in a graph where edges have non-negative weights.

Find the shortest path from a starting node even when some edges have negative weights, and detect negative cycles.

Order the nodes of a graph so every task comes after everything it depends on, used for scheduling and build order.

Track which nodes belong to the same group and merge groups quickly, used to detect cycles and build networks.

Build the cheapest network connecting all nodes by adding the smallest edges first, skipping any that form a cycle.

Build the cheapest network connecting all nodes by growing a tree one node at a time, always picking the cheapest edge out.