Skip to content

Instantly share code, notes, and snippets.

@manzaloros
Last active July 13, 2021 13:26
Show Gist options
  • Save manzaloros/059c4b562f8001d685e811569324abdf to your computer and use it in GitHub Desktop.
Save manzaloros/059c4b562f8001d685e811569324abdf to your computer and use it in GitHub Desktop.
Topological sort using depth first search
// Time: O(number of vertices)
// Space: O(number of vertices)
// Using the params for course scheduler:
const findOrder = (numCourses, prerequisites) => {
/*
// Make graph adjacency list if needed:
const graph = new Map();
prerequisites.forEach(([course, prerequisite]) => {
if (!graph.has(course)) graph.set(course, []);
if (!graph.has(prerequisite)) graph.set(prerequisite, []);
graph.get(prerequisite).push(course);
});
for (let i = 0; i < numCourses; i += 1) {
if (!graph.has(i)) graph.set(i, []);
}
*/
const visited = new Set();
const order = [];
let isCyclic = false;
const depthFirstSearch = (node, branchMemo) => {
visited.add(node);
// Keep track of the current branch so you don't get stuck
// in a cycle
branchMemo.add(node);
graph.get(node).forEach((neighbor) => {
if (!isCyclic) {
if (branchMemo.has(neighbor)) {
isCyclic = true;
}
if (!visited.has(neighbor)) depthFirstSearch(neighbor, branchMemo);
}
});
branchMemo.delete(node);
// add to order in reverse order because DFS hits leaf nodes first
order.unshift(node);
};
// iterate over each graph node only if not cyclic
graph.forEach((value, node) => {
if (!isCyclic) {
if (!visited.has(node)) depthFirstSearch(node, new Set());
}
});
return isCyclic ? [] : order;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment