JavaScript/Data-Structures/Graph/Graph.js at master · sibalonecoding-code/JavaScript · GitHub

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
101
102
103
classGraph{
constructor(){
this.adjacencyMap={}
}

addVertex(vertex){
this.adjacencyMap[vertex]=[]
}

containsVertex(vertex){
returntypeofthis.adjacencyMap[vertex]!=='undefined'
}

addEdge(vertex1,vertex2){
if(this.containsVertex(vertex1)&&this.containsVertex(vertex2)){
this.adjacencyMap[vertex1].push(vertex2)
this.adjacencyMap[vertex2].push(vertex1)
}
}

printGraph(output=(value)=>console.log(value)){
constkeys=Object.keys(this.adjacencyMap)
for(constiofkeys){
constvalues=this.adjacencyMap[i]
letvertex=''
for(constjofvalues){
vertex+=j+' '
}
output(i+' -> '+vertex)
}
}

/**
 * Prints the Breadth first traversal of the graph from source.
 * @param {number} source The source vertex to start BFS.
 */
bfs(source,output=(value)=>console.log(value)){
constqueue=[[source,0]]// level of source is 0
constvisited=newSet()

while(queue.length){
const[node,level]=queue.shift()// remove the front of the queue
if(visited.has(node)){
// visited
continue
}

visited.add(node)
output(`Visited node ${node} at level ${level}.`)
for(constnextofthis.adjacencyMap[node]){
queue.push([next,level+1])// level 1 more than current
}
}
}

/**
 * Prints the Depth first traversal of the graph from source.
 * @param {number} source The source vertex to start DFS.
 */
dfs(source,visited=newSet(),output=(value)=>console.log(value)){
if(visited.has(source)){
// visited
return
}

output(`Visited node ${source}`)
visited.add(source)
for(constneighbourofthis.adjacencyMap[source]){
this.dfs(neighbour,visited,output)
}
}
}

constexample=()=>{
constg=newGraph()
g.addVertex(1)
g.addVertex(2)
g.addVertex(3)
g.addVertex(4)
g.addVertex(5)
g.addEdge(1,2)
g.addEdge(1,3)
g.addEdge(2,4)
g.addEdge(2,5)

// Graph
// 1 -> 2 3
// 2 -> 1 4 5
// 3 -> 1
// 4 -> 2
// 5 -> 2

// Printing the adjacency list
// g.printGraph()

// Breadth first search at node 1
g.bfs(1)

// Depth first search at node 1
g.dfs(1)
}

export{Graph,example}