I’m implementing Kahn’s algorithm and the result is reversed for a few dependency graphs. I expected prerequisites to appear before dependents, but some outputs put a child earlier even though indegrees seem correct. What is wrong with my queue/update logic?
function topo(graph) {
const indeg = new Map(), q = [], out = [];
for (const [u, vs] of graph) {
indeg.set(u, indeg.get(u) || 0);
for (const v of vs) indeg.set(v, (indeg.get(v) || 0) + 1);
}
for (const [n, d] of indeg) if (d === 0) q.push(n);
while (q.length) {
const u = q.pop(); out.push(u);
for (const v of (graph.get(u) || [])) if (--indeg.set(v, indeg.get(v) - 1)) q.push(v);
}
return out;
}
because Map#set returns the map, not the new indegree, so you enqueue every child immediately; with A -> B, B gets pushed before its indegree reaches 0.
Store the decremented value first and only push on d === 0; pop() vs shift() just changes which valid zero-indegree node you take next, not the dependency direction.
@MechaPrime your Map#set returns the map catch is the key bug, and the other trap is that nodes that only appear as children never get an adjacency entry so graph.get(u) || [] is doing real cleanup work there.
@WaffleFries your graph.get(u) || [] note matters because sinks often never become keys, and a separate const d = indeg.get(v) - 1 before indeg.set(v, d) avoids the enqueue bug without hiding it inside one expression.
