-
Notifications
You must be signed in to change notification settings - Fork 1
/
Graphs.js
74 lines (68 loc) · 1.65 KB
/
Graphs.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
//Graphs
class Graph {
constructor() {
this.adjacencyList = {};
}
addVertex(vertex) {
if (!this.adjacencyList[vertex]) {
this.adjacencyList[vertex] = [];
}
}
addEdge(v1, v2) {
if (!this.adjacencyList[v1].includes(v2)) {
this.adjacencyList[v1].push(v2);
this.adjacencyList[v2].push(v1);
}
}
removeEdge(vertex1, vertex2) {
this.adjacencyList[vertex1] = this.adjacencyList[vertex1].filter(
(edge) => edge != vertex2
);
this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(
(edge) => edge != vertex1
);
}
removeVertex(vertex) {
while (this.adjacencyList[vertex].length) {
const adjacentVertex = this.adjacencyList[vertex].pop();
this.removeEdge(vertex, adjacentVertex);
}
delete this.adjacencyList[vertex];
}
DFS(start) {
let result = [];
let visited = {};
let adjacencyList = this.adjacencyList;
const Traverse = function (vertex) {
if (!adjacencyList[vertex]) return null;
result.push(vertex);
visited[vertex] = true;
adjacencyList[vertex].forEach((v) => {
if (!visited[v]) {
Traverse(v);
}
});
return result;
};
return Traverse(start);
}
BFS(start) {
let result = [];
let q = [start];
let visited = {};
let removed;
visited[start] = true;
while (q.length) {
if (!this.adjacencyList[start]) return null;
removed = q.shift();
result.push(removed);
this.adjacencyList[removed].forEach((v) => {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
});
}
return result;
}
}