GeezerVison is showing github.com — merge: Add Graph3 (add DFS in Iterative Way) (#944) · Algorithms-Learn/JavaScript@233ec59
File treeExpand file treeCollapse file tree Open diff view settings Expand file treeCollapse file tree Open diff view settings Collapse file Copy file name to clipboard +108Lines changed: 108 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +class Graph { | | 2 | + constructor () { | | 3 | + this.adjacencyObject = {} | | 4 | + } | | 5 | + | | 6 | + addVertex (vertex) { | | 7 | + if (!this.adjacencyObject[vertex]) this.adjacencyObject[vertex] = [] | | 8 | + } | | 9 | + | | 10 | + addEdge (vertex1, vertex2) { | | 11 | + this.adjacencyObject[vertex1].push(vertex2) | | 12 | + this.adjacencyObject[vertex2].push(vertex1) | | 13 | + } | | 14 | + | | 15 | + removeEdge (vertex1, vertex2) { | | 16 | + this.adjacencyObject[vertex1] = this.adjacencyObject[vertex1].filter( | | 17 | + (v) => v !== vertex2 | | 18 | + ) | | 19 | + this.adjacencyObject[vertex2] = this.adjacencyObject[vertex2].filter( | | 20 | + (v) => v !== vertex1 | | 21 | + ) | | 22 | + } | | 23 | + | | 24 | + removeVertex (vertex) { | | 25 | + while (this.adjacencyObject[vertex].length) { | | 26 | + const adjacentVertex = this.adjacencyObject[vertex].pop() | | 27 | + this.removeEdge(vertex, adjacentVertex) | | 28 | + } | | 29 | + } | | 30 | + | | 31 | + /** | | 32 | + * Return DFS (Depth First Search) List Using Recursive Method | | 33 | + */ | | 34 | + DFS (start) { | | 35 | + if (!start) return null | | 36 | + | | 37 | + const result = [] | | 38 | + const visited = {} | | 39 | + const adjacencyObject = this.adjacencyObject | | 40 | + | | 41 | + function dfs (vertex) { | | 42 | + if (!vertex) return null | | 43 | + visited[vertex] = true | | 44 | + result.push(vertex) | | 45 | + adjacencyObject[vertex].forEach((neighbor) => { | | 46 | + if (!visited[neighbor]) { | | 47 | + dfs(neighbor) | | 48 | + } | | 49 | + }) | | 50 | + } | | 51 | + | | 52 | + dfs(start) | | 53 | + return result | | 54 | + } | | 55 | + | | 56 | + /** | | 57 | + * Return DFS(Depth First Search) List Using Iteration | | 58 | + */ | | 59 | + DFSIterative (start) { | | 60 | + if (!start) return null | | 61 | + | | 62 | + const stack = [start] | | 63 | + const visited = {} | | 64 | + visited[start] = true | | 65 | + | | 66 | + const result = [] | | 67 | + let currentVertex | | 68 | + | | 69 | + while (stack.length) { | | 70 | + currentVertex = stack.pop() | | 71 | + result.push(currentVertex) | | 72 | + | | 73 | + this.adjacencyObject[currentVertex].forEach((neighbor) => { | | 74 | + if (!visited[neighbor]) { | | 75 | + visited[neighbor] = true | | 76 | + stack.push(neighbor) | | 77 | + } | | 78 | + }) | | 79 | + } | | 80 | + return result | | 81 | + } | | 82 | + | | 83 | + BFS (start) { | | 84 | + if (!start) return null | | 85 | + | | 86 | + const queue = [start] | | 87 | + const visited = {} | | 88 | + visited[start] = true | | 89 | + | | 90 | + let currentVertex | | 91 | + const result = [] | | 92 | + | | 93 | + while (queue.length) { | | 94 | + currentVertex = queue.shift() | | 95 | + result.push(currentVertex) | | 96 | + | | 97 | + this.adjacencyObject[currentVertex].forEach((neighbor) => { | | 98 | + if (!visited[neighbor]) { | | 99 | + visited[neighbor] = true | | 100 | + queue.push(neighbor) | | 101 | + } | | 102 | + }) | | 103 | + } | | 104 | + return result | | 105 | + } | | 106 | +} | | 107 | + | | 108 | +export { Graph } |
Collapse file Copy file name to clipboard +75Lines changed: 75 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +import { Graph } from '../Graph3' | | 2 | + | | 3 | +describe('Test Graph3', () => { | | 4 | + const g = new Graph() | | 5 | + | | 6 | + // Add Vertices | | 7 | + g.addVertex('A') | | 8 | + g.addVertex('B') | | 9 | + g.addVertex('C') | | 10 | + g.addVertex('D') | | 11 | + g.addVertex('E') | | 12 | + g.addVertex('F') | | 13 | + | | 14 | + // Add Edges | | 15 | + g.addEdge('A', 'B') | | 16 | + g.addEdge('A', 'C') | | 17 | + g.addEdge('B', 'D') | | 18 | + g.addEdge('C', 'E') | | 19 | + g.addEdge('D', 'E') | | 20 | + g.addEdge('D', 'F') | | 21 | + g.addEdge('E', 'F') | | 22 | + | | 23 | + /** | | 24 | + * A - B - D | | 25 | + * | / \ | | 26 | + * C - - E - F | | 27 | + * | | 28 | + * DFS(Iterative): A-C-E-F-D-B | | 29 | + * DFS(Recursive): A-B-D-E-C-F | | 30 | + * BFS: A-B-C-D-E-F | | 31 | + */ | | 32 | + it('Check iterative DFS List', () => { | | 33 | + const iterativeDFSList = g.DFSIterative('A') | | 34 | + expect(iterativeDFSList).toEqual(['A', 'C', 'E', 'F', 'D', 'B']) | | 35 | + }) | | 36 | + | | 37 | + it('Check recursive DFS List', () => { | | 38 | + const recursiveDFSList = g.DFS('A') | | 39 | + expect(recursiveDFSList).toEqual(['A', 'B', 'D', 'E', 'C', 'F']) | | 40 | + }) | | 41 | + | | 42 | + it('Check BFS List', () => { | | 43 | + const BFSList = g.BFS('A') | | 44 | + expect(BFSList).toEqual(['A', 'B', 'C', 'D', 'E', 'F']) | | 45 | + }) | | 46 | + | | 47 | + /** | | 48 | + * Test After Remove 'B' Vertex | | 49 | + * A D | | 50 | + * | / \ | | 51 | + * C - - E - F | | 52 | + * | | 53 | + * DFS(Iterative): A-C-E-F-D | | 54 | + * DFS(Recursive): A-C-E-D-F | | 55 | + * BFS: A-C-E-D-F | | 56 | + */ | | 57 | + | | 58 | + it('Check iterative DFS List After Removing Vertex B', () => { | | 59 | + g.removeVertex('B') | | 60 | + const iterativeDFSList = g.DFSIterative('A') | | 61 | + expect(iterativeDFSList).toEqual(['A', 'C', 'E', 'F', 'D']) | | 62 | + }) | | 63 | + | | 64 | + it('Check recursive DFS List After Removing Vertex B', () => { | | 65 | + g.removeVertex('B') | | 66 | + const recursiveDFSList = g.DFS('A') | | 67 | + expect(recursiveDFSList).toEqual(['A', 'C', 'E', 'D', 'F']) | | 68 | + }) | | 69 | + | | 70 | + it('Check BFS List After Removing Vertex B', () => { | | 71 | + g.removeVertex('B') | | 72 | + const BFSList = g.BFS('A') | | 73 | + expect(BFSList).toEqual(['A', 'C', 'E', 'D', 'F']) | | 74 | + }) | | 75 | +}) |
|