-
Notifications
You must be signed in to change notification settings - Fork 8
/
toposort.js
65 lines (55 loc) · 1.47 KB
/
toposort.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
const GraphBase = require('./graph-base');
const Stack = require('./ds/stack');
class TopologicalSort extends GraphBase {
constructor(numVertices = 0, numEdges = 0, startingPoint = 0) {
super(numVertices, numEdges);
this.startingPoint = startingPoint;
}
topologicalSortHelper(node, visited, stack, Adj) {
visited[node] = true;
for (let i = 0; i < Adj.get(node).length; i++) {
if (!visited[Adj.get(node)[i]]) {
this.topologicalSortHelper(Adj.get(node)[i], visited, stack, Adj);
}
}
stack.push(node);
}
topologicalSort() {
let stack = new Stack();
let Adj = this.getSimpleAdj();
let visited = [];
let vertex = [];
Adj.forEach((value, key) => {
visited[key] = false;
vertex.push(key);
});
for (let i = 0; i < vertex.length; i++) {
if (!visited[vertex[i]]) {
let node = vertex[i];
this.topologicalSortHelper(node, visited, stack, Adj);
}
}
let topoSort_order = [];
while (!stack.isEmpty()) {
topoSort_order.push(stack.peek());
stack.pop();
}
return topoSort_order;
}
}
// const g = new TopologicalSort(5)
// vertices = [0,1,2,3,4,5,6]
// for(let i=0;i<vertices.length;i++)
// {
// g.addVertex(vertices[i])
// }
// g.addEdge(0, 2);
// g.addEdge(0, 1);
// g.addEdge(0,3);
// g.addEdge(2, 3);
// g.addEdge(3,4);
// g.addEdge(4,5);
// g.addEdge(1,6);
// // console.log(g.adj)
// console.log(g.topologicalSort())
module.exports = TopologicalSort;