Apr 2, 2023 · Apr 2, 2023 · Apr 2, 2023 · Apr 2, 2023
diff --git a/Data-Structures/Graph/Graph.js b/Data-Structures/Graph/Graph.js
 class Graph {
  constructor() {
  constructor() {
    this.adjacencyMap = {}
    this.numberOfVertex = 0
  }

  addVertex(vertex) {
  addVertex(vertex) {
    this.adjacencyMap[vertex] = []
    this.numberOfVertex++
  }

  containsVertex(vertex) {
    return typeof(this.adjacencyMap[vertex]) !=='undefined'
  containsVertex(vertex) {
    return typeof this.adjacencyMap[vertex] !== undefined
  }

  addEdge(vertex1, vertex2) {
  addEdge(vertex1, vertex2) {
    if (this.containsVertex(vertex1) && this.containsVertex(vertex2)) {
      this.adjacencyMap[vertex1].push(vertex2)
      this.adjacencyMap[vertex2].push(vertex1)
    }
  }

  printGraph(output = value => console.log(value)) {
  printGraph(output =(value) => console.log(value)) {
    const keys = Object.keys(this.adjacencyMap)
    for (const i of keys) {
      const values = this.adjacencyMap[i]
   * Prints the Breadth first traversal of the graph from source.
   * @param {number} source The source vertex to start BFS.
   */
  bfs(source, output = value => console.log(value)) {
  bfs(source, output =(value) => console.log(value)) {
    const queue = [[source, 0]] // level of source is 0
    const visited = new Set()

    while (queue.length) {
      const [node, level] = queue.shift() // remove the front of the queue
      if (visited.has(node)) { // visited
      if (visited.has(node)) {
        // visited
        continue
      }

   * Prints the Depth first traversal of the graph from source.
   * @param {number} source The source vertex to start DFS.
   */
  dfs (source, visited = new Set(), output = value => console.log(value)) {
    if (visited.has(source)) { // visited
  dfs(source, visited = new Set(), output = (value) => console.log(value)) {
    if (visited.has(source)) {
      // visited
      return
    }

      this.dfs(neighbour, visited, output)
    }
  }

  _topologicalSort(neighbor, visited, stack) {
    // Mark the current node as visited.
    visited[neighbor] = true

    // Recur for all the vertices adjacent to thisvertex
    for (const i of this.adjacencyMap[neighbor]) {
      if (!visited[i]) {
        this._topologicalSort(i, visited, stack)
      }
    }

    // Push current vertex to stack which stores result
    stack.push(neighbor)
  }

  // The function to do Topological Sort. It uses recursive _topologicalSort()
  topologicalSort() {
    const stack = []

    // Mark all the vertices as not visited
    const visited = new Array(this.numberOfVertex)
    visited.fill(false)

    // Call the recursive helper function to store Topological Sort starting from all vertices one by one
    for (let i = 0; i < visited.length; i++) {
      if (visited[i] === false) {
        this._topologicalSort(i + 1, visited, stack)
      }
    }

    // Return stack in reverse order
    return stack.reverse()
  }
 }

 const example = () => {

  // Depth first search at node 1
  g.dfs(1)

  // Prints Topological sort of given graph
  g.topologicalSort()
 }

 export { Graph, example }
diff --git a/Data-Structures/Graph/test/Graph.test.js b/Data-Structures/Graph/test/Graph.test.js
 import { Graph } from '../Graph'

 describe('Graph', () => {
  const graph = new Graph()

  for (let v = 1; v <= 5; v++) {
    graph.addVertex(v)
  }

  graph.addEdge(1, 2)
  graph.addEdge(1, 3)
  graph.addEdge(2, 4)
  graph.addEdge(2, 5)

  it('returns any valid topological sort', () => {
    expect([
      [1, 2, 3, 4, 5],
      [1, 3, 2, 4, 5],
      [1, 3, 2, 5, 4],
      [1, 2, 4, 3, 5],
      [1, 2, 5, 3, 4],
      [1, 2, 4, 5, 3],
    ]).toContain(graph.topologicalSort())
  })
 })
Original file line number	Diff line number	Diff line change
		@@ -1,24 +1,26 @@
		class Graph {
		constructor() {
		constructor() {
		this.adjacencyMap = {}
		this.numberOfVertex = 0
		}

		addVertex(vertex) {
		addVertex(vertex) {
		this.adjacencyMap[vertex] = []
		this.numberOfVertex++
		}

		containsVertex(vertex) {
		return typeof(this.adjacencyMap[vertex]) !=='undefined'
		containsVertex(vertex) {
		return typeof this.adjacencyMap[vertex] !== undefined
		}

		addEdge(vertex1, vertex2) {
		addEdge(vertex1, vertex2) {
		if (this.containsVertex(vertex1) && this.containsVertex(vertex2)) {
		this.adjacencyMap[vertex1].push(vertex2)
		this.adjacencyMap[vertex2].push(vertex1)
		}
		}

		printGraph(output = value => console.log(value)) {
		printGraph(output =(value) => console.log(value)) {
		const keys = Object.keys(this.adjacencyMap)
		for (const i of keys) {
		const values = this.adjacencyMap[i]
Expand All		@@ -34,13 +36,14 @@ class Graph {
		* Prints the Breadth first traversal of the graph from source.
		* @param {number} source The source vertex to start BFS.
		*/
		bfs(source, output = value => console.log(value)) {
		bfs(source, output =(value) => console.log(value)) {
		const queue = [[source, 0]] // level of source is 0
		const visited = new Set()

		while (queue.length) {
		const [node, level] = queue.shift() // remove the front of the queue
		if (visited.has(node)) { // visited
		if (visited.has(node)) {
		// visited
		continue
		}

Expand All		@@ -56,8 +59,9 @@ class Graph {
		* Prints the Depth first traversal of the graph from source.
		* @param {number} source The source vertex to start DFS.
		*/
		dfs (source, visited = new Set(), output = value => console.log(value)) {
		if (visited.has(source)) { // visited
		dfs(source, visited = new Set(), output = (value) => console.log(value)) {
		if (visited.has(source)) {
		// visited
		return
		}

Expand All		@@ -67,6 +71,40 @@ class Graph {
		this.dfs(neighbour, visited, output)
		}
		}

		_topologicalSort(neighbor, visited, stack) {
		// Mark the current node as visited.
		visited[neighbor] = true

		// Recur for all the vertices adjacent to thisvertex
		for (const i of this.adjacencyMap[neighbor]) {
		if (!visited[i]) {
		this._topologicalSort(i, visited, stack)
		}
		}

		// Push current vertex to stack which stores result
		stack.push(neighbor)
		}

		// The function to do Topological Sort. It uses recursive _topologicalSort()
		topologicalSort() {
		const stack = []

		// Mark all the vertices as not visited
		const visited = new Array(this.numberOfVertex)
		visited.fill(false)

		// Call the recursive helper function to store Topological Sort starting from all vertices one by one
		for (let i = 0; i < visited.length; i++) {
		if (visited[i] === false) {
		this._topologicalSort(i + 1, visited, stack)
		}
		}

		// Return stack in reverse order
		return stack.reverse()
		}
		}

		const example = () => {
Expand DownExpand Up		@@ -96,6 +134,9 @@ const example = () => {

		// Depth first search at node 1
		g.dfs(1)

		// Prints Topological sort of given graph
		g.topologicalSort()
		}

		export { Graph, example }
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,25 @@
		import { Graph } from '../Graph'

		describe('Graph', () => {
		const graph = new Graph()

		for (let v = 1; v <= 5; v++) {
		graph.addVertex(v)
		}

		graph.addEdge(1, 2)
		graph.addEdge(1, 3)
		graph.addEdge(2, 4)
		graph.addEdge(2, 5)

		it('returns any valid topological sort', () => {
		expect([
		[1, 2, 3, 4, 5],
		[1, 3, 2, 4, 5],
		[1, 3, 2, 5, 4],
		[1, 2, 4, 3, 5],
		[1, 2, 5, 3, 4],
		[1, 2, 4, 5, 3],
		]).toContain(graph.topologicalSort())
		})
		})