| class Graph { | |
| constructor() { | |
| this.adjacencyList = {} | |
| } | |
| addVertex(v) { | |
| if(!this.adjacencyList[v]) { | |
| this.adjacencyList[v] = [] | |
| } | |
| } | |
| addEdge(v1,v2){ | |
| this.adjacencyList[v1].push(v2) | |
| this.adjacencyList[v2].push(v1) | |
| } | |
| removeEdge(v1,v2){ | |
| this.adjacencyList[v1] = this.adjacencyList[v1].filter(v => v !== v2) | |
| this.adjacencyList[v2] = this.adjacencyList[v2].filter(v => v !== v1) | |
| } | |
| removeVertex(v) { | |
| while(this.adjacencyList[v].length) { | |
| const adjacentVertex = this.adjacencyList[v].pop() | |
| this.removeEdge(adjacentVertex,v) | |
| } | |
| delete this.adjacencyList[v] | |
| } | |
| print(){ | |
| console.log(JSON.stringify(this.adjacencyList)) | |
| } | |
| DFS(v) { | |
| let results = []; | |
| let visited = {}; | |
| const _DFS = (v) => { | |
| if(!v) return; | |
| results.push(v); | |
| visited[v] = true; | |
| let neighbours = this.adjacencyList[v] | |
| for(let neighbour of neighbours) { | |
| if(!visited[neighbour]){ | |
| _DFS(neighbour); | |
| } | |
| } | |
| } | |
| _DFS(v); | |
| console.log(results); | |
| console.log(visited); | |
| } | |
| DFS_Iterative(v) { | |
| let stack = []; | |
| let results = []; | |
| let visited = {}; | |
| stack.push(v); | |
| while(stack.length) { | |
| v = stack.pop(); | |
| if(!visited[v]) { | |
| results.push(v) | |
| visited[v] = true; | |
| for(let n of this.adjacencyList[v]){ | |
| stack.push(n) | |
| } | |
| } | |
| } | |
| console.log(results); | |
| console.log(visited); | |
| } | |
| BFS_Iterative(startVertex) { | |
| let queue = []; | |
| let results = []; | |
| let visited = {}; | |
| queue.push(startVertex); | |
| let currentVertex; | |
| while(queue.length){ | |
| currentVertex = queue.shift(); | |
| results.push(currentVertex); | |
| visited[currentVertex] = true; | |
| for(let n of this.adjacencyList[currentVertex]){ | |
| if(!visited[n]){ | |
| visited[n] = true; | |
| queue.push(n) | |
| } | |
| } | |
| } | |
| console.log(results) | |
| console.log(visited) | |
| } | |
| } | |
| const graph = new Graph() | |
| graph.adjacencyList["A"] = ["B","C"] | |
| graph.adjacencyList["B"] = ["A","D"] | |
| graph.adjacencyList["C"] = ["A" , "E"] | |
| graph.adjacencyList["D"] = ["B", "E" ,"F"] | |
| graph.adjacencyList["E"] = ["C","D", "F"] | |
| graph.adjacencyList["F"] = ["D","E"] | |
| graph.DFS('B') |