Skip to content

Instantly share code, notes, and snippets.

@bluurn
Created January 30, 2019 09:15
Show Gist options
  • Save bluurn/27503d27f84158d49abf4476daba55d7 to your computer and use it in GitHub Desktop.
Save bluurn/27503d27f84158d49abf4476daba55d7 to your computer and use it in GitHub Desktop.
JS: Implementation of Graph
class Graph {
constructor() {
this.adjList = new Map();
}
addVertex(v) {
this.adjList.set(v, []);
return this;
}
addEdge(v, w) {
this.adjList.get(v).push(w);
this.adjList.get(w).push(v);
return this;
}
toString() {
var paths = '';
for(var key of this.adjList.keys()) {
var path = `${key} -> `;
for(var value of this.adjList.get(key)) {
path += `${value} `;
}
paths += `${path}\n`;
}
return paths;
}
bfs(startingVertex, cb) {
var queue = new Queue;
var visited = new Set;
queue.enqueue(startingVertex);
visited.add(startingVertex);
while(!queue.isEmpty()) {
var vertex = queue.dequeue();
cb(vertex);
var neighbours = this.adjList.get(vertex);
for(var i = 0; i < neighbours.length; i++) {
if(!visited.has(neighbours[i])) {
queue.enqueue(neighbours[i]);
visited.add(neighbours[i]);
}
}
}
}
dfs(startingVertex, cb) {
var visited = new Set;
function recur(vertex, adjList) {
visited.add(vertex);
cb(vertex);
var neighbours = adjList.get(vertex);
for(var i = 0; i < neighbours.length; i++) {
if(!visited.has(neighbours[i])) {
recur(neighbours[i], adjList)
}
}
}
recur(startingVertex, this.adjList);
}
}
var graph = new Graph();
var vertices = ['A', 'B', 'C', 'D', 'E', 'F'];
for(var i = 0; i < vertices.length; i++) {
graph.addVertex(vertices[i]);
}
graph
.addEdge('A', 'B')
.addEdge('A', 'D')
.addEdge('A', 'E')
.addEdge('B', 'C')
.addEdge('D', 'E')
.addEdge('E', 'F')
.addEdge('E', 'C')
.addEdge('C', 'F');
console.log(graph.toString());
console.log('BFS')
graph.bfs('A', console.log);
console.log('DFS')
graph.dfs('A', console.log);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment