Skip to content

Instantly share code, notes, and snippets.

@robbywashere

robbywashere/topo_sort.js

Last active Jan 15, 2019
Embed
What would you like to do?
class Graph {
constructor(){
this.nodes = {};
}
addNode(n){
if (!this.nodes[n]) this.nodes[n] = [];
}
addDirEdge(a,b){
this.nodes[a].push(b);
}
}
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addDirEdge("A", "C");
g.addDirEdge("A", "B");
g.addDirEdge("A", "D");
g.addDirEdge("C", "D");
g.addDirEdge("D", "E");
g.addDirEdge("E", "F");
g.addDirEdge("B", "G");
function topoSort(graph){
let stack = [];
let explored = new Set();
for (let node of Object.keys(graph.nodes)){
if (!explored.has(node)){
function ts(n){
explored.add(n);
graph.nodes[n].forEach(nextNode=>{
if (!explored.has(nextNode)) ts(nextNode);
})
stack.push(n);
}
ts(node)
}
}
while (stack.length) console.log(stack.pop())
}
topoSort(g);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.