Permalink
May 5, 2021
Newer
100644
38 lines (33 sloc)
917 Bytes
1
/**
2
* Adjacency Matrix Graph - Depth First Search
3
*/
4
5
{
6
function traversalDepthFirstSearch(graph) {
7
const values = [];
8
depthFirstSearch(0, graph, values, {});
9
return values;
10
}
11
12
function depthFirstSearch(vertex, graph, values, seen) {
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
depthFirstSearch(v, graph, values, seen);
21
}
22
}
23
}
24
25
console.log(
26
traversalDepthFirstSearch([
27
[0, 1, 0, 1, 0, 0, 0, 0, 0],
28
[1, 0, 0, 0, 0, 0, 0, 0, 0],
29
[0, 0, 0, 1, 0, 0, 0, 0, 1],
30
[1, 0, 1, 0, 1, 1, 0, 0, 0],
31
[0, 0, 0, 1, 0, 0, 1, 0, 0],
32
[0, 0, 0, 1, 0, 0, 0, 0, 0],
33
[0, 0, 0, 0, 1, 0, 0, 1, 0],
34
[0, 0, 0, 0, 0, 0, 1, 0, 0],
35
[0, 0, 1, 0, 0, 0, 0, 0, 0],
36
]),
37
); // [0, 1, 3, 2, 8, 4, 6, 7, 5]
38
}