Created
January 30, 2019 09:15
-
-
Save bluurn/27503d27f84158d49abf4476daba55d7 to your computer and use it in GitHub Desktop.
JS: Implementation of Graph
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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