Improved DFS.

techpanja · techpanja · commit c08727a7d1ce · 2016-02-27T22:07:13.000-08:00
Adding recursion.
diff --git a/src/graphs/depthfirstsearch/DFS.java b/src/graphs/depthfirstsearch/DFS.java
@@ -23,6 +23,9 @@ private DFS() {
 
     }
 
+    /*
+    * DFS using Stack.
+    * */
     public static void dfs(Graph graph) {
         Vertex vertex = graph.getFirstVertex();
         if (vertex != null) {
@@ -42,24 +45,52 @@ public static void dfs(Graph graph) {
         }
     }
 
+    // Improving the complexity of the solution by removing the temp from dependsOn.
     private static Vertex getUnvisitedVertex(Vertex vertex) {
         for (Vertex temp : vertex.getDependsOn()) {
             if (!temp.isVisited()) {
+                vertex.getDependsOn().remove(temp);
                 return temp;
             }
         }
         return null;
     }
 
+    /*
+    * DFS using recursion.
+    * */
+    public static void dfsRecursion(Graph graph) {
+        Vertex vertex = graph.getFirstVertex();
+        dfs(vertex);
+    }
+
+    public static void dfs(Vertex vertex) {
+        if (vertex != null) {
+            System.out.println(vertex);
+            vertex.setVisited(true);
+            for (Vertex temp : vertex.getDependsOn()) {
+                if (!temp.isVisited()) {
+                    dfs(temp);
+                }
+            }
+
+        }
+    }
+
     public static void main(String[] args) {
         Graph graph = new DirectedGraph(6);
+//        graph.addEdge("v1", "v2");
+//        graph.addEdge("v2", "v3");
+//        graph.addEdge("v3", "v4");
+//        graph.addEdge("v1", "v5");
+//        graph.addEdge("v1", "v6");
+
         graph.addEdge("v1", "v2");
-        graph.addEdge("v2", "v3");
-        graph.addEdge("v3", "v4");
-        graph.addEdge("v1", "v5");
-        graph.addEdge("v1", "v6");
+        graph.addEdge("v1", "v3");
+        graph.addEdge("v2", "v4");
+
         graph.displayGraphDependency();
-        dfs(graph);
+        dfsRecursion(graph);
     }
 
 }
