1 |
|
2 |
|
3 |
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
10 |
|
11 |
|
12 |
|
13 |
|
14 |
|
15 | module.exports = function bfs(startNode, graph, fn) {
|
16 | visit([{ node: startNode, path: [] }], graph, fn);
|
17 | };
|
18 |
|
19 | function visit(frontier, graph, fn) {
|
20 | var level = 0;
|
21 | var levels = {};
|
22 |
|
23 | while (0 < frontier.length) {
|
24 | var next = [];
|
25 | for (var i = 0; i < frontier.length; i++) {
|
26 | var cur = frontier[i];
|
27 | var node = cur.node;
|
28 | if (fn(cur) === false) {
|
29 | return;
|
30 | }
|
31 | levels[node] = level;
|
32 | for (var adj in graph[node]) {
|
33 | if (typeof levels[adj] === "undefined") {
|
34 | next.push({ node: adj, path: cur.path.concat(node) });
|
35 | }
|
36 | }
|
37 | }
|
38 | frontier = next;
|
39 | level += 1;
|
40 | }
|
41 | }
|