topologicalSort.js

topologicalSort.js

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {number[]}
 */
var findOrder = function(numCourses, prerequisites) {
    let adjList = {};
    let indegree = {};
    let topologicalOrder = [];
    
    // graph
    // course => [dependencies]
    
    // indegree is how many things depend on destination 
    
    for(let i = 0; i < prerequisites.length; i++) {
        let dest = prerequisites[i][0]; // depends on 
        let src = prerequisites[i][1]; // source
        
        if(!adjList.hasOwnProperty(src)) { adjList[src] = []; }
        if(!adjList.hasOwnProperty(dest)) { adjList[dest] = []; }
        if(!indegree.hasOwnProperty(dest)) { indegree[dest] = 0; }
        if(!indegree.hasOwnProperty(src)) { indegree[src] = 0; }
        adjList[src].push(dest);
        indegree[dest]++;
    }

    let list = [];
    let zeroes = Object.keys(indegree).filter((key) => indegree[key] == 0);
    list.push(...zeroes);

    while (list.length > 0) {
        let node = list.shift();
        topologicalOrder.push(node);
            
        if (adjList.hasOwnProperty(node)) {
            adjList[node].forEach((neighbor) => {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    list.push(neighbor);
                }
            });
        }
    }
    if (topologicalOrder.length == numCourses) {
        return topologicalOrder;
    }
    return [];
};