GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — JavaScript/Data-Structures/Graph/Graph.js at master · TheAlgorithms/JavaScript

Expand file tree

/

Graph.js

Copy path
More file actions
More file actions

Latest commit

 

History

History
History
103 lines (88 loc) · 2.27 KB
/

Graph.js

Copy path

File metadata and controls

103 lines (88 loc) · 2.27 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
class Graph {
constructor() {
this.adjacencyMap = {}
}
addVertex(vertex) {
this.adjacencyMap[vertex] = []
}
containsVertex(vertex) {
return typeof this.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)) {
const keys = Object.keys(this.adjacencyMap)
for (const i of keys) {
const values = this.adjacencyMap[i]
let vertex = ''
for (const j of values) {
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)) {
const queue = [[source, 0]] // level of source is 0
const visited = new Set()
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 (const next of this.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 = new Set(), output = (value) => console.log(value)) {
if (visited.has(source)) {
// visited
return
}
output(`Visited node ${source}`)
visited.add(source)
for (const neighbour of this.adjacencyMap[source]) {
this.dfs(neighbour, visited, output)
}
}
}
const example = () => {
const g = new Graph()
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 }
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.