mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-05 08:16:50 +08:00
233ec596dc
* Add Graph3 (add DFS in Iterative Way) * Remove example code and add test code (Graph3) * Remove redundant code (like return undefined)
76 lines
1.7 KiB
JavaScript
76 lines
1.7 KiB
JavaScript
import { Graph } from '../Graph3'
|
|
|
|
describe('Test Graph3', () => {
|
|
const g = new Graph()
|
|
|
|
// Add Vertices
|
|
g.addVertex('A')
|
|
g.addVertex('B')
|
|
g.addVertex('C')
|
|
g.addVertex('D')
|
|
g.addVertex('E')
|
|
g.addVertex('F')
|
|
|
|
// Add Edges
|
|
g.addEdge('A', 'B')
|
|
g.addEdge('A', 'C')
|
|
g.addEdge('B', 'D')
|
|
g.addEdge('C', 'E')
|
|
g.addEdge('D', 'E')
|
|
g.addEdge('D', 'F')
|
|
g.addEdge('E', 'F')
|
|
|
|
/**
|
|
* A - B - D
|
|
* | / \
|
|
* C - - E - F
|
|
*
|
|
* DFS(Iterative): A-C-E-F-D-B
|
|
* DFS(Recursive): A-B-D-E-C-F
|
|
* BFS: A-B-C-D-E-F
|
|
*/
|
|
it('Check iterative DFS List', () => {
|
|
const iterativeDFSList = g.DFSIterative('A')
|
|
expect(iterativeDFSList).toEqual(['A', 'C', 'E', 'F', 'D', 'B'])
|
|
})
|
|
|
|
it('Check recursive DFS List', () => {
|
|
const recursiveDFSList = g.DFS('A')
|
|
expect(recursiveDFSList).toEqual(['A', 'B', 'D', 'E', 'C', 'F'])
|
|
})
|
|
|
|
it('Check BFS List', () => {
|
|
const BFSList = g.BFS('A')
|
|
expect(BFSList).toEqual(['A', 'B', 'C', 'D', 'E', 'F'])
|
|
})
|
|
|
|
/**
|
|
* Test After Remove 'B' Vertex
|
|
* A D
|
|
* | / \
|
|
* C - - E - F
|
|
*
|
|
* DFS(Iterative): A-C-E-F-D
|
|
* DFS(Recursive): A-C-E-D-F
|
|
* BFS: A-C-E-D-F
|
|
*/
|
|
|
|
it('Check iterative DFS List After Removing Vertex B', () => {
|
|
g.removeVertex('B')
|
|
const iterativeDFSList = g.DFSIterative('A')
|
|
expect(iterativeDFSList).toEqual(['A', 'C', 'E', 'F', 'D'])
|
|
})
|
|
|
|
it('Check recursive DFS List After Removing Vertex B', () => {
|
|
g.removeVertex('B')
|
|
const recursiveDFSList = g.DFS('A')
|
|
expect(recursiveDFSList).toEqual(['A', 'C', 'E', 'D', 'F'])
|
|
})
|
|
|
|
it('Check BFS List After Removing Vertex B', () => {
|
|
g.removeVertex('B')
|
|
const BFSList = g.BFS('A')
|
|
expect(BFSList).toEqual(['A', 'C', 'E', 'D', 'F'])
|
|
})
|
|
})
|