Course Schedule (Topological Sort)
Given a set of N courses and the prerequisites between them, works out an order in which every course can be taken — the topological sort behind build systems, package installers and task pipelines. Receives the prerequisites as a square adjacency matrix, where a nonzero value at row i, column j means course i must be taken before course j (0 means no dependency). Applies Kahn's algorithm: it counts how many prerequisites each course is still waiting on (its indegree), queues every course that has none, and then repeatedly takes a course out of the queue, appends it to the order and decrements the indegree of every course that depended on it, queueing any that drop to zero. Returns a valid order of all N courses, or an empty list when a cycle of mutual prerequisites makes the schedule impossible.
Visualization
- Input
- Result
Algorithm code
// Course Schedule — a single pure function. Receives the course prerequisite
// graph as an N×N adjacency matrix and returns a valid order in which every
// course can be taken, or an empty list when a cycle makes that impossible.
/**
* @param {number[][]} prerequisiteMatrix - N×N matrix where a nonzero value at
* row i, column j means course i must be taken before course j
* @returns {number[]} a topological order of all N courses, or [] when a cycle exists
*/
export function courseSchedule(prerequisiteMatrix) {
const courseCount = prerequisiteMatrix.length;
const indegree = new Array(courseCount).fill(0);
for (let from = 0; from < courseCount; from += 1) {
for (let to = 0; to < courseCount; to += 1) {
if (prerequisiteMatrix[from][to] !== 0) {
indegree[to] += 1;
}
}
}
const queue = [];
for (let course = 0; course < courseCount; course += 1) {
if (indegree[course] === 0) {
queue.push(course);
}
}
const order = [];
while (queue.length > 0) {
const course = queue.shift();
order.push(course);
for (let next = 0; next < courseCount; next += 1) {
if (prerequisiteMatrix[course][next] !== 0) {
indegree[next] -= 1;
if (indegree[next] === 0) {
queue.push(next);
}
}
}
}
return order.length === courseCount ? order : [];
}FUNCTION courseSchedule(prerequisiteMatrix):
courseCount ← length(prerequisiteMatrix)
indegree ← array of courseCount zeros
FOR from FROM 0 TO courseCount - 1:
FOR to FROM 0 TO courseCount - 1:
IF prerequisiteMatrix[from][to] ≠ 0:
indegree[to] ← indegree[to] + 1
queue ← empty list
FOR course FROM 0 TO courseCount - 1:
IF indegree[course] = 0:
enqueue course to queue
order ← empty list
WHILE queue is not empty:
course ← dequeue from queue
append course to order
FOR next FROM 0 TO courseCount - 1:
IF prerequisiteMatrix[course][next] ≠ 0:
indegree[next] ← indegree[next] - 1
IF indegree[next] = 0:
enqueue next to queue
IF length(order) = courseCount:
RETURN order
RETURN empty list