merge: Graph (TheAlgorithms#850)

Yatin-kathuria · web-flow · commit c33b19a73130 · 2021-11-27T11:08:35.000+05:30
* Modify Graph bfs method

* add dfs in graph
diff --git a/Data-Structures/Graph/Graph.js b/Data-Structures/Graph/Graph.js
@@ -3,22 +3,19 @@ class Graph {
     this.adjacencyMap = {}
   }
 
-  addVertex (v) {
-    this.adjacencyMap[v] = []
+  addVertex (vertex) {
+    this.adjacencyMap[vertex] = []
   }
 
   containsVertex (vertex) {
     return typeof (this.adjacencyMap[vertex]) !== 'undefined'
   }
 
-  addEdge (v, w) {
-    let result = false
-    if (this.containsVertex(v) && this.containsVertex(w)) {
-      this.adjacencyMap[v].push(w)
-      this.adjacencyMap[w].push(v)
-      result = true
+  addEdge (vertex1, vertex2) {
+    if (this.containsVertex(vertex1) && this.containsVertex(vertex2)) {
+      this.adjacencyMap[vertex1].push(vertex2)
+      this.adjacencyMap[vertex2].push(vertex1)
     }
-    return result
   }
 
   printGraph (output = value => console.log(value)) {
@@ -35,7 +32,6 @@ 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)) {
@@ -55,6 +51,22 @@ 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
+      return
+    }
+
+    output(`Visited node ${source}`)
+    visited.add(source)
+    for (const neighbour of this.adjacencyMap[source]) {
+      this.dfs(neighbour, visited, output)
+    }
+  }
 }
 
 const example = () => {
@@ -69,11 +81,21 @@ const example = () => {
   g.addEdge(2, 4)
   g.addEdge(2, 5)
 
+  // Graph
+  // 1 -> 2 3
+  // 2 -> 1 4 5
+  // 3 -> 1
+  // 4 -> 2
+  // 5 -> 2
+
   // Printing the adjacency list
   // g.printGraph()
 
   // Breadth first search at node 1
   g.bfs(1)
+
+  // Depth first search at node 1
+  g.dfs(1)
 }
 
 export { Graph, example }
