Skip to content

Commit 5b57332

Browse files
Doha2012Doha2012
committed
depth first search
1 parent ba9d52a commit 5b57332

4 files changed

Lines changed: 171 additions & 0 deletions

File tree

‎data-structures/src/main/java/com/baeldung/graph/Graph.java‎

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
package com.baeldung.graph;
2+
3+
import java.util.ArrayList;
4+
import java.util.List;
5+
import java.util.Stack;
6+
7+
public class Graph {
8+
9+
private List<List<Integer>> neighbours;
10+
private int n;
11+
12+
public Graph(int n) {
13+
this.n = n;
14+
this.neighbours = new ArrayList<List<Integer>>(n);
15+
for (int i = 0; i < n; i++) {
16+
this.neighbours.add(new ArrayList<Integer>());
17+
}
18+
}
19+
20+
public void addEdge(int src, int dest) {
21+
this.neighbours.get(src)
22+
.add(dest);
23+
}
24+
25+
public void dfsWithoutRecursion(int start) {
26+
Stack<Integer> stack = new Stack<Integer>();
27+
boolean[] isVisited = new boolean[n];
28+
stack.push(start);
29+
while (!stack.isEmpty()) {
30+
int current = stack.pop();
31+
isVisited[current] = true;
32+
System.out.print(" " + current);
33+
for (int dest : neighbours.get(current)) {
34+
if (!isVisited[dest])
35+
stack.push(dest);
36+
}
37+
}
38+
}
39+
40+
public void dfs(int start) {
41+
boolean[] isVisited = new boolean[n];
42+
dfsRecursive(start, isVisited);
43+
}
44+
45+
private void dfsRecursive(int current, boolean[] isVisited) {
46+
isVisited[current] = true;
47+
System.out.print(" " + current);
48+
for (int dest : neighbours.get(current)) {
49+
if (!isVisited[dest])
50+
dfsRecursive(dest, isVisited);
51+
}
52+
}
53+
54+
public void topologicalSort(int start) {
55+
Stack<Integer> result = new Stack<Integer>();
56+
boolean[] isVisited = new boolean[n];
57+
topologicalSortRecursive(start, isVisited, result);
58+
while (!result.isEmpty()) {
59+
System.out.print(" " + result.pop());
60+
}
61+
}
62+
63+
private void topologicalSortRecursive(int current, boolean[] isVisited, Stack<Integer> result) {
64+
isVisited[current] = true;
65+
for (int dest : neighbours.get(current)) {
66+
if (!isVisited[dest])
67+
topologicalSortRecursive(dest, isVisited, result);
68+
}
69+
result.push(current);
70+
}
71+
}

‎data-structures/src/main/java/com/baeldung/tree/BinaryTree.java‎

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22

33
import java.util.LinkedList;
44
import java.util.Queue;
5+
import java.util.Stack;
56

67
public class BinaryTree {
78

@@ -147,6 +148,68 @@ public void traverseLevelOrder() {
147148
}
148149
}
149150

151+
152+
public void traverseInOrderWithoutRecursion() {
153+
Stack<Node> stack = new Stack<Node>();
154+
Node current = root;
155+
stack.push(root);
156+
while(! stack.isEmpty()) {
157+
while(current.left != null) {
158+
current = current.left;
159+
stack.push(current);
160+
}
161+
current = stack.pop();
162+
System.out.print(" " + current.value);
163+
if(current.right != null) {
164+
current = current.right;
165+
stack.push(current);
166+
}
167+
}
168+
}
169+
170+
public void traversePreOrderWithoutRecursion() {
171+
Stack<Node> stack = new Stack<Node>();
172+
Node current = root;
173+
stack.push(root);
174+
while(! stack.isEmpty()) {
175+
current = stack.pop();
176+
System.out.print(" " + current.value);
177+
178+
if(current.right != null)
179+
stack.push(current.right);
180+
181+
if(current.left != null)
182+
stack.push(current.left);
183+
}
184+
}
185+
186+
public void traversePostOrderWithoutRecursion() {
187+
Stack<Node> stack = new Stack<Node>();
188+
Node prev = root;
189+
Node current = root;
190+
stack.push(root);
191+
192+
while (!stack.isEmpty()) {
193+
current = stack.peek();
194+
boolean hasChild = (current.left != null || current.right != null);
195+
boolean isPrevLastChild = (prev == current.right || (prev == current.left && current.right == null));
196+
197+
if (!hasChild || isPrevLastChild) {
198+
current = stack.pop();
199+
System.out.print(" " + current.value);
200+
prev = current;
201+
} else {
202+
if (current.right != null) {
203+
stack.push(current.right);
204+
}
205+
if (current.left != null) {
206+
stack.push(current.left);
207+
}
208+
}
209+
}
210+
}
211+
212+
150213
class Node {
151214
int value;
152215
Node left;

‎data-structures/src/test/java/com/baeldung/graph/GraphUnitTest.java‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package com.baeldung.graph;
2+
3+
import org.junit.Test;
4+
5+
public class GraphUnitTest {
6+
7+
@Test
8+
public void givenDirectedGraph_whenDFS_thenPrintAllValues() {
9+
Graph graph = createDirectedGraph();
10+
graph.dfs(0);
11+
System.out.println();
12+
graph.dfsWithoutRecursion(0);
13+
}
14+
15+
@Test
16+
public void givenDirectedGraph_whenGetTopologicalSort_thenPrintValuesSorted() {
17+
Graph graph = createDirectedGraph();
18+
graph.topologicalSort(0);
19+
}
20+
21+
private Graph createDirectedGraph() {
22+
Graph graph = new Graph(6);
23+
graph.addEdge(0, 1);
24+
graph.addEdge(0, 2);
25+
graph.addEdge(1, 3);
26+
graph.addEdge(2, 3);
27+
graph.addEdge(3, 4);
28+
graph.addEdge(4, 5);
29+
return graph;
30+
}
31+
}

‎data-structures/src/test/java/com/baeldung/tree/BinaryTreeUnitTest.java‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -87,6 +87,8 @@ public void givenABinaryTree_WhenTraversingInOrder_ThenPrintValues() {
8787
BinaryTree bt = createBinaryTree();
8888

8989
bt.traverseInOrder(bt.root);
90+
System.out.println();
91+
bt.traverseInOrderWithoutRecursion();
9092
}
9193

9294
@Test
@@ -95,6 +97,8 @@ public void givenABinaryTree_WhenTraversingPreOrder_ThenPrintValues() {
9597
BinaryTree bt = createBinaryTree();
9698

9799
bt.traversePreOrder(bt.root);
100+
System.out.println();
101+
bt.traversePreOrderWithoutRecursion();
98102
}
99103

100104
@Test
@@ -103,6 +107,8 @@ public void givenABinaryTree_WhenTraversingPostOrder_ThenPrintValues() {
103107
BinaryTree bt = createBinaryTree();
104108

105109
bt.traversePostOrder(bt.root);
110+
System.out.println();
111+
bt.traversePostOrderWithoutRecursion();
106112
}
107113

108114
@Test

0 commit comments

Comments
 (0)