What can I do first?
Prepare dough before steaming momos; learn JavaScript before React. Dependencies form a directed acyclic graph, and a topological sort lists tasks so every task comes after everything it depends on. Build tools, package managers and course prerequisites all do this.
Kahn's algorithm
function topoSort(tasks, deps) {
const indegree = new Map(tasks.map((t) => [t, 0]));
const next = new Map(tasks.map((t) => [t, []]));
for (const [before, after] of deps) {
next.get(before).push(after);
indegree.set(after, indegree.get(after) + 1);
}
const ready = tasks.filter((t) => indegree.get(t) === 0);
const order = [];
for (let i = 0; i < ready.length; i++) {
const t = ready[i];
order.push(t);
for (const n of next.get(t)) {
indegree.set(n, indegree.get(n) - 1);
if (indegree.get(n) === 0) ready.push(n);
}
}
return order.length === tasks.length ? order : null;
}
const tasks = ["buy flour", "make dough", "make filling", "fold momos", "steam", "serve"];
const deps = [["buy flour", "make dough"], ["make dough", "fold momos"], ["make filling", "fold momos"], ["fold momos", "steam"], ["steam", "serve"]];
console.log(topoSort(tasks, deps));
console.log(topoSort(["a", "b"], [["a", "b"], ["b", "a"]]));