Skip to content

Commit 6099a7d

Browse files
abranheabranhe
authored
Merge pull request AllAlgorithms#34 from jakubkarabula/add-bfs-dfs
Add DFS and BFS algorithms
2 parents cb2d753 + 4a17a23 commit 6099a7d

2 files changed

Lines changed: 90 additions & 0 deletions

File tree

‎graphs/bfs.js‎

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
/*
2+
A non-recursive implementation of bfs with worst-case space complexity O(|E|)
3+
*/
4+
5+
function Vertex (name, neighbours) {
6+
this.name = name;
7+
this.neighbours = neighbours;
8+
}
9+
10+
function bfs (root) {
11+
var visited = {}
12+
var stack = []
13+
14+
stack.push(root)
15+
while(!!stack.length) {
16+
var vertex = stack.shift()
17+
18+
if (!visited[vertex.name]) {
19+
visited[vertex.name] = true
20+
console.log('Visiting vertex ', vertex.name)
21+
22+
var len = vertex.neighbours.length
23+
for (var index = 0; index < len; index++) {
24+
stack.push(vertex.neighbours[index])
25+
}
26+
}
27+
}
28+
}
29+
30+
var root = new Vertex('root', [
31+
new Vertex('child 1', [
32+
new Vertex('grandchild 1', []), new Vertex('grandchild 2', [])
33+
]),
34+
new Vertex('child 2', [
35+
new Vertex('grandchild 3', []),
36+
]),
37+
new Vertex('child 3', [
38+
new Vertex('grandchild 4', [
39+
new Vertex('grandgrandchild 1', [])
40+
]),
41+
]),
42+
])
43+
44+
bfs(root)

‎graphs/dfs.js‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
/*
2+
A non-recursive implementation of DFS with worst-case space complexity O(|E|)
3+
4+
according to wiki pseudocode https://en.wikipedia.org/wiki/Depth-first_search
5+
*/
6+
7+
function Vertex (name, neighbours) {
8+
this.name = name;
9+
this.neighbours = neighbours;
10+
}
11+
12+
function dfs (root) {
13+
var visited = {}
14+
var stack = []
15+
16+
stack.push(root)
17+
while(!!stack.length) {
18+
var vertex = stack.pop()
19+
20+
if (!visited[vertex.name]) {
21+
visited[vertex.name] = true
22+
console.log('Visiting vertex ', vertex.name)
23+
24+
var len = vertex.neighbours.length
25+
for (var index = 0; index < len; index++) {
26+
stack.push(vertex.neighbours[index])
27+
}
28+
}
29+
}
30+
}
31+
32+
var root = new Vertex('root', [
33+
new Vertex('child 1', [
34+
new Vertex('grandchild 1', []), new Vertex('grandchild 2', [])
35+
]),
36+
new Vertex('child 2', [
37+
new Vertex('grandchild 3', []),
38+
]),
39+
new Vertex('child 3', [
40+
new Vertex('grandchild 4', [
41+
new Vertex('grandgrandchild 1', [])
42+
]),
43+
]),
44+
])
45+
46+
dfs(root)

0 commit comments

Comments
 (0)