forked from thuva4/Algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathBFS.js
More file actions
131 lines (118 loc) · 3.2 KB
/
BFS.js
File metadata and controls
131 lines (118 loc) · 3.2 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
131
// Fully runnable code, along with test cases at https://codepen.io/sniper6/pen/KXrJqG/
const BFS = (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 Q = [], // The queue 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;
Q.push(source);
visited[source] = true;
while (Q.length !== 0) {
const currentVertex = Q.shift();
order.push(currentVertex);
const neighbors = graph.getNeighbors(currentVertex);
for (const neighbor of neighbors) {
if (!visited[neighbor]) {
Q.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("BFS", () => {
let graph = null;
beforeEach(() => {
graph = GraphFactory.getGraph();
});
it("should throw error on bad graph", () => {
expect(() => {
BFS({});
}).toThrow("Graph should implement a getNeighbors function");
});
it("should throw error on no source vertex", () => {
expect(() => {
BFS(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(BFS(graph, 0, 3)).toEqual({
order: [0, 1, 3, 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(BFS(graph, 0, 3)).toEqual({
order: [0, 1, 2, 3, 4],
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(3, 5, false);
graph.addEdge(4, 2, false);
expect(BFS(graph, 0, 3)).toEqual({
order: [0, 1, 2, 3, 4, 5],
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(BFS(graph, 0, 5)).toEqual({
order: [0, 1, 3, 2],
found: false
});
});
});