Permalink
May 5, 2021
Newer
100644
43 lines (36 sloc)
762 Bytes
1
/**
2
* Adjacency List Graph - Breadth First Search
3
*/
4
5
{
6
function traversalBreadthFirstSearch(graph) {
7
const seen = {};
8
const queue = [0];
9
const values = [];
10
11
while (queue.length) {
12
const vertex = queue.shift();
13
values.push(vertex);
14
seen[vertex] = true;
15
16
const connections = graph[vertex];
17
18
for (let i = 0; i < connections.length; i++) {
19
const connection = connections[i];
20
21
if (!seen[connection]) {
22
queue.push(connection);
23
}
24
}
25
}
26
27
return values;
28
}
29
30
console.log(
31
traversalBreadthFirstSearch([
32
[1, 3],
33
[0],
34
[3, 8],
35
[0, 2, 4, 5],
36
[3, 6],
37
[3],
38
[4, 7],
39
[6],
40
[2],
41
]),
42
); // [0, 1, 3, 2, 4, 5, 8, 6, 7]
43
}