Categories
Algorithms Javascript

Topological Sort in JS

Imagine you have a list of dependencies and prerequisites that form a graph. You can use topological sort graph algorithm in order to validate meeting all the requirements. Here is a BFS implementation of this algorithm in Javascript:

const canFinish = function (numCourses, prerequisites) {
	const rank = new Array(numCourses).fill(0),
		// rank["C" => 0, "OOP" = 1, "DS" = 1] -> how many dependencies
		dependent = new Array(numCourses).fill().map((v) => []);
		// dependent["C"] = ["OOP", "DS"];
	for (const [a, b] of prerequisites) {
		rank[a]++;
		dependent[b].push(a);
	}
	const queue = [];
	for (const i in rank) if (rank[i] == 0) queue.push(i);
	while (queue.length) {
		const node = queue.shift();
		for (const neighbour of dependent[node]) {
			rank[neighbour]--;
			if (rank[neighbour] == 0) queue.push(neighbour);
		}
	}
	return rank.every((v) => !Boolean(v));
};

Time Complexity: O(∣E∣+∣V∣)

  • ∣V∣ is the number of nodes
  • ∣E∣ is the number of dependencies.

Space Complexity: O(∣E∣+∣V∣)

Leave a Reply

Your email address will not be published. Required fields are marked *