Lessons · TypeScript · graphs (things joined to things)
Things joined to things
A graph is usually a Map, or a plain object, from each node to the list it joins. Unlike a tree it can hold cycles, so every walk needs a Set of what it has already seen.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
Followers, routes, dependencies, imports, deadlocks. A surprising share of hard-looking problems turn out to be a graph once you name the nodes and the edges.
How to think about it
Name the nodes and the edges before writing anything. Fewest steps means breadth-first with a queue; 'is there any route' means depth-first. Add the seen set before anything else.
Worked example
const graph = { a: ['b', 'c'], b: ['d'], c: ['d'], d: ['a'] };d joins back to a: a cycle.function hops(start, goal) {const queue = [[start, 0]], seen = new Set([start]);The Set is what stops the cycle.
let head = 0;
while (head < queue.length) {const [n, dist] = queue[head++];Front of the queue: nothing nearer is waiting.
if (n === goal) return dist;First arrival is by a shortest route.
for (const next of graph[n]) { if (!seen.has(next)) { seen.add(next); queue.push([next, dist + 1]); }Without this, a to b to d to a forever.}
}
return null;No route at all.
}
console.log(hops('a', 'd'), hops('a', 'a'));2 0Your turn
Stop the walk revisiting a node and looping forever.
for (const next of graph[n]) {
if (!seen.(next)) { seen.add(next); queue.push(next); }
}Solve one with the tests running
The trap
Depth-first finds A route, not the shortest. Using it where the question says 'fewest' gives an answer that is plausible, too large, and passes small tests.