Topological sort

topological-sort.js

function toposortDFS(edges, begin){
    const inEdges = new Map()
    const outEdges = new Map()
    const vertices = new Set()
    const result = new Set()
    for (const [edge, dep] of edges) {
      vertices.add(edge)
      vertices.add(dep)
    }
    for (const vertex of vertices) {
      outEdges.set(vertex, new Set())
      inEdges.set(vertex, new Set())
    }
    for (const [edge, dep] of edges) {
      outEdges.get(edge).add(dep)
      inEdges.get(dep).add(edge)
    }
    
    function visit(vertex){
        if (inEdges.get(vertex).size > 0) return
        result.add(vertex)
        for (const outVertex of outEdges.get(vertex)) {
          inEdges.get(outVertex).delete(vertex)
          visit(outVertex)
        }
    }
    visit(begin);
    return [...result]
}