Update Graph.java

omertopuz · web-flow · commit b9a95d37e551 · 2021-06-05T23:04:19.000+03:00
for dfsWithoutRecursion, when a node popped from the stack it should be checked that the current node is visited or not. Since stack has duplicated nodes, some nodes is visired doubly.
diff --git a/algorithms-searching/src/main/java/com/baeldung/algorithms/dfs/Graph.java b/algorithms-searching/src/main/java/com/baeldung/algorithms/dfs/Graph.java
@@ -29,11 +29,13 @@ public void dfsWithoutRecursion(int start) {
         stack.push(start);
         while (!stack.isEmpty()) {
             int current = stack.pop();
-            isVisited[current] = true;
-            visit(current);
-            for (int dest : adjVertices.get(current)) {
-                if (!isVisited[dest])
-                    stack.push(dest);
+            if(!isVisited[current]){
+                isVisited[current] = true;
+                visit(current);
+                for (int dest : adjVertices.get(current)) {
+                    if (!isVisited[dest])
+                        stack.push(dest);
+                }
             }
         }
     }

Original file line number	Diff line number	Diff line change
`@@ -29,11 +29,13 @@ public void dfsWithoutRecursion(int start) {`
`29`	`29`	`stack.push(start);`
`30`	`30`	`while (!stack.isEmpty()) {`
`31`	`31`	`int current = stack.pop();`
`32`		`- isVisited[current] = true;`
`33`		`- visit(current);`
`34`		`- for (int dest : adjVertices.get(current)) {`
`35`		`- if (!isVisited[dest])`
`36`		`- stack.push(dest);`
	`32`	`+ if(!isVisited[current]){`
	`33`	`+ isVisited[current] = true;`
	`34`	`+ visit(current);`
	`35`	`+ for (int dest : adjVertices.get(current)) {`
	`36`	`+ if (!isVisited[dest])`
	`37`	`+ stack.push(dest);`
	`38`	`+ }`
`37`	`39`	`}`
`38`	`40`	`}`
`39`	`41`	`}`