Topological Sort

topological-sort.js

const topologicalSort = (tree) => {
  const answers = [];
  
  const entryTimesMap = new Map();
  // calc entry times
  tree.forEach(node => {
    if (!entryTimesMap.has(node.val)) {
      entryTimesMap.set(node.val, 0);
    }
    node.deps.forEach(dep => {
      entryTimesMap.set(dep, (entryTimesMap.get(dep) || 0) + 1);
    })
  })
  
  // console.log(entryTimesMap);
  
  // search no entry times items
  const queue = [];
  entryTimesMap.forEach((entryTimes, val) => {
    if (entryTimes === 0) {
      queue.push(val);
    }    
  })
  
  while (queue.length > 0) {
    const val = queue.shift();
    answers.push(val);
    
    const node = tree.find(n => n.val === val);
    node.deps.forEach(dep => {
      const entryTimes = entryTimesMap.get(dep) - 1;
      entryTimesMap.set(dep, entryTimes);
      if (entryTimes === 0) {
        queue.push(dep);
      }
    })
    
  }
  
  return answers;
}

const testTree = [
  { val: 0, deps: [1, 3] },
  { val: 1, deps: [3] },
  { val: 2, deps: [3, 4] },
  { val: 3, deps: [] },
  { val: 4, deps: [5] },
  { val: 5, deps: [] },
];
// [0,2,1,4,3,5]
console.log(topologicalSort(testTree));