Services that call each other, packages that depend on each other, hosts linked by a network: all are graphs, nodes joined by edges. Before searching one, build an adjacency list, a map from each node to its neighbours, so each step looks at neighbours directly instead of scanning every edge.
Breadth-first search starts from one node and visits everything one step away, then everything two steps away, and so on, using a queue. Because it goes level by level, the first time it reaches a node is by the fewest possible steps. Mark nodes as seen when you add them to the queue, not when you take them out, or the same node is queued many times.
In JavaScript, Array.prototype.shift is slow on big arrays, because it moves every remaining item. Keep a read index into the array instead and let it grow.
The same level-by-level idea orders dependencies. Count, for each node, how many of its dependencies are not done yet. Everything at zero can run now: that is the first wave. Running it lowers the counts of what depends on it, and whatever reaches zero forms the next wave. If nodes remain that never reach zero, they depend on each other in a cycle.
Recognise it
- The data is about connections: who links to, calls or depends on whom.
- The question is the fewest steps, or whether something is reachable at all.
- Things must happen in an order that respects dependencies.
The shape of the code
const adj = new Map(); // node -> neighbours
for (const [a, b] of edges) {
if (!adj.has(a)) adj.set(a, []);
adj.get(a).push(b);
}
const dist = new Map([[start, 0]]);
const queue = [start];
for (let head = 0; head < queue.length; head++) {
const node = queue[head];
for (const next of adj.get(node) ?? []) {
if (dist.has(next)) continue;
dist.set(next, dist.get(node) + 1);
queue.push(next);
}
}