Permalink
May 5, 2021
Newer
100644
41 lines (35 sloc)
919 Bytes
1
/**
2
* Adjacency Matrix 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 v = 0; v < connections.length; v++) {
19
if (connections[v] > 0 && !seen[v]) {
20
queue.push(v);
21
}
22
}
23
}
24
25
return values;
26
}
27
28
console.log(
29
traversalBreadthFirstSearch([
30
[0, 1, 0, 1, 0, 0, 0, 0, 0],
31
[1, 0, 0, 0, 0, 0, 0, 0, 0],
32
[0, 0, 0, 1, 0, 0, 0, 0, 1],
33
[1, 0, 1, 0, 1, 1, 0, 0, 0],
34
[0, 0, 0, 1, 0, 0, 1, 0, 0],
35
[0, 0, 0, 1, 0, 0, 0, 0, 0],
36
[0, 0, 0, 0, 1, 0, 0, 1, 0],
37
[0, 0, 0, 0, 0, 0, 1, 0, 0],
38
[0, 0, 1, 0, 0, 0, 0, 0, 0],
39
]),
40
); // [0, 1, 3, 2, 4, 5, 8, 6, 7]
41
}