-
Notifications
You must be signed in to change notification settings - Fork 0
/
bfs.js
106 lines (90 loc) · 2.77 KB
/
bfs.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
//Visit neigbours first before going down
/*
Steps:-
- Function should accept a string vertex
- Create a queue and place the starting vertex in it
- Create an array to store the nodes visited
- Create an obeject to store nodes visited
- Mark the starting vertex as visited
- Loop as long as there is anything in the queue
- Remove the first vertex from the queue and push it into the array that stores nodes visited
- Loop over each vertex in the adjacency list for the vertex you are visiting
- If it is not inside the object that stores nodes visited, mark it as visited and enqueue that vertex
- Once you have finished looping, return the array of visted nodes
*/
class Graph {
constructor() {
this.adjacencyList = {}
}
addVertex(vertex) {
if(!this.adjacencyList[vertex]) this.adjacencyList[vertex] = []
}
addEdge(v1, v2) {
this.adjacencyList[v1].push(v2)
this.adjacencyList[v2].push(v1)
}
removeEdge(vertex1, vertex2) {
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
v => v !== vertex2
)
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
v => v !== vertex1
)
}
removeVertex(vertex) {
while(this.adjacencyList[vertex].length) {
const adjacentVertex = this.adjacencyList[vertex].pop()
this.removeEdge(vertex, adjacentVertex)
}
delete this.adjacencyList[vertex]
}
depthFirstRecursive(start) {
const result =[]
const visited = {}
const adjacencyList = this.adjacencyList
(function dfs(vertex) {
if(!vertex) return null
visited[vertex] = true
result.push(vertex)
adjacencyList[vertex].forEach(neighbour => {
if(!visited[neighbour]) {
return dfs(neighbour)
}
})
})(start)
return result
}
breadthFirst(start) {
const queue = [start]
const result = []
const visited = {}
let currentVertex
visited[start] = true
while(queue.length) {
currentVertex = queue.shift()
result.push(currentVertex)
this.adjacencyList[currentVertex].forEach(neighbour => {
if(!visited[neighbour]) {
visited[neighbour] = true
queeue.push(neighbour)
}
})
}
return result
}
}
let g = new Graph()
g.addVertex("A")
g.addVertex("B")
g.addVertex("C")
g.addVertex("D")
g.addVertex("E")
g.addVertex("F")
g.addEdge("A", "B")
g.addEdge("A", "C")
g.addEdge("B", "D")
g.addEdge("C", "E")
g.addEdge("D", "E")
g.addEdge("D", "F")
g.addEdge("E", "F")
console.log(g.depthFirstRecursive("A"))