forked from thuva4/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDFS.js
More file actions
130 lines (117 loc) · 3.17 KB
/
DFS.js
File metadata and controls
130 lines (117 loc) · 3.17 KB
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
// Fully runnable code with tests at https://codepen.io/sniper6/pen/QqzYEa
const DFS = (graph, source, target = -1) => {
// Some error handling
if (typeof graph.getNeighbors !== "function") {
throw "Graph should implement a getNeighbors function";
}
if (typeof source !== "number") {
throw "source should be a number";
}
const stack = [], // The stack that will be used
order = [], // Array to hold the order of visit. Mainly for unit testing
visited = {}; // Keep track of visited vertices
let found = false;
stack.push(source);
visited[source] = true;
while (stack.length !== 0) {
const currentVertex = stack.pop();
order.push(currentVertex);
const neighbors = graph.getNeighbors(currentVertex);
for (const neighbor of neighbors) {
if (!visited[neighbor]) {
stack.push(neighbor);
visited[neighbor] = true;
if (neighbor === target) {
found = true;
}
}
}
}
return { order, found };
};
const GraphFactory = (() => {
const GraphTemplate = {
init() {
this._graph = [];
},
getNeighbors(vertex) {
return this._graph[vertex] || [];
},
addEdge(source, target, biDirectional = true) {
this._addEdge(source, target);
if (biDirectional) {
this._addEdge(target, source);
}
},
_addEdge(source, target) {
this._graph[source] = this._graph[source] || [];
this._graph[source].push(target);
},
printGraph() {
console.log(JSON.stringify(this._graph, null, 2));
}
};
return {
getGraph() {
const Graph = Object.assign({}, GraphTemplate);
Graph.init();
return Graph;
}
};
})();
describe("DFS", () => {
let graph = null;
beforeEach(() => {
graph = GraphFactory.getGraph();
});
it("should throw error on bad graph", () => {
expect(() => {
DFS({});
}).toThrow("Graph should implement a getNeighbors function");
});
it("should throw error on no source vertex", () => {
expect(() => {
DFS(graph);
}).toThrow("source should be a number");
});
it("simple bi-directional graph where target is reachable", () => {
graph.addEdge(0, 1);
graph.addEdge(0, 3);
graph.addEdge(1, 2);
expect(DFS(graph, 0, 3)).toEqual({
order: [0, 3, 1, 2],
found: true
});
});
it("complex bi-directional graph where target is reachable", () => {
graph.addEdge(0, 1);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 2);
expect(DFS(graph, 0, 3)).toEqual({
order: [0, 2, 4, 3, 1],
found: true
});
});
it("complex uni-directional graph where target is reachable", () => {
graph.addEdge(0, 1, false);
graph.addEdge(0, 2, false);
graph.addEdge(1, 3, false);
graph.addEdge(3, 4, false);
graph.addEdge(4, 2, false);
expect(DFS(graph, 0, 3)).toEqual({
order: [0, 2, 1, 3, 4],
found: true
});
});
it("simple bi-directional graph where target is not present", () => {
graph.addEdge(0, 1);
graph.addEdge(0, 3);
graph.addEdge(1, 2);
expect(DFS(graph, 0, 5)).toEqual({
order: [0, 3, 1, 2],
found: false
});
});
});