-
Notifications
You must be signed in to change notification settings - Fork 10
/
bfs.js
41 lines (38 loc) · 1.08 KB
/
bfs.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
/**
* Visitor function called on each node
* @callback visitor
* @param {{}} node The node being visited, it is augmented with the path (an
* array of nodes, that leads to it)
*/
/**
* Graph visitor based on the the https://en.wikipedia.org/wiki/Breadth-first_search
*
* @param {{}} startNode The node where the search/traverse starts
* @param {Array} graph The graph to be traversed
* @callback {visitor} fn A function called on each node
*/
module.exports = function bfs(startNode, graph, fn) {
visit([{ node: startNode, path: [] }], graph, fn);
};
function visit(frontier, graph, fn) {
var level = 0;
var levels = {};
while (0 < frontier.length) {
var next = [];
for (var i = 0; i < frontier.length; i++) {
var cur = frontier[i];
var node = cur.node;
if (fn(cur) === false) {
return;
}
levels[node] = level;
for (var adj in graph[node]) {
if (typeof levels[adj] === "undefined") {
next.push({ node: adj, path: cur.path.concat(node) });
}
}
}
frontier = next; // eslint-disable-line no-param-reassign
level += 1;
}
}