RecapDifficulty: Advanced1 min

Recap: Graph Modelling

Name the vertex, the edge, its direction and its weight, and the question then names the algorithm: search, order or group.

A problem hides a graph when it has things, links between pairs of them, and a question about reaching, ordering or grouping. Modelling decides the vertex, the edge, whether the edge has a direction and whether it has a weight; the question then picks the algorithm.

What the problem says, and the graph and algorithm it leads to
The problem says	Vertex	Edge	Algorithm
Fewest steps from one thing to another	The thing	One step, no direction or weight	Breadth-first search
Fewest moves in a puzzle	A state: everything the next move depends on	One move, built when reached	Breadth-first search over states
Do this before that	A task	From what comes first to what needs it	Topological sort; a short order means a loop
Records that share a detail belong together	A record	A shared detail	Union-find
Fewest changes between routes	A route	Two routes that meet	Breadth-first search from every route at the start

A state must work as a key: a tuple in Python, a record in Java and a string in TypeScript. Depth-first search with a visited set finds a route but not the fewest moves, and the choice of vertex decides what a search counts.

← → move through sections and cards