Skip to content

Instantly share code, notes, and snippets.

@rmdort
Last active May 30, 2021 16:27
Show Gist options
  • Save rmdort/2e89d9713ec0714a6a87341f96154444 to your computer and use it in GitHub Desktop.
Save rmdort/2e89d9713ec0714a6a87341f96154444 to your computer and use it in GitHub Desktop.
Topologically sort (BFS) a DAG
/**
* Visit a graph node
* Sort it topologically and return
* all the dependents
* @param nodes
* @param previsit
* @returns
*/
const topologicalSort = <T>(nodes: T[], children: (node: T) => Set<T>) => {
const stack = new Set<T>();
const visited = new Set<T>();
const sort = (node: T) => {
visited.add(node);
for (const child of children(node)) {
if (!visited.has(child)) {
sort(child);
}
}
stack.add(node);
};
for (const node of nodes) {
if (!visited.has(node)) {
sort(node);
}
}
return [...stack].reverse();
};
export default topologicalSort;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment