# Example of Depth-First Search (DFS) algorithm in Java

## Depth-first Search

A very common and natural way to traverse a graph, directed or undirected, is analogous to a pre-order traversal of a binary tree and it is called a depth-first search, or **DFS** for short. DFS is a backtrack-style traversal that visits a node and then recursively visits all nodes adjacent to it that have not yet been visited. To prevent the algorithm from going into an endless loop by revisiting nodes, when a node is visited for the first time it is *marked*.

Here’s an animation showing Depth-first search traversing through a tree.

For this example, our graph has 8 nodes, A through H:

- A has an edge to node B.
- B has an edge to node G.
- B has edges to nodes C and D.
- C has an edge to node D.
- D has an edge to node E.
- E has edges to nodes F and G.
- G has an edge to node H.

## DFS using Recursion

```
import java.util.LinkedList;
// Class to represent a node in the graph
class Node {
String name;
LinkedList<Node> neighbors;
boolean visited;
public Node(String name) {
this.name = name;
this.neighbors = new LinkedList<>();
this.visited = false;
}
}
public class DepthFirstSearch {
public static void main(String[] args) {
// Create eight nodes
Node A = new Node("A");
Node B = new Node("B");
Node C = new Node("C");
Node D = new Node("D");
Node E = new Node("E");
Node F = new Node("F");
Node G = new Node("G");
Node H = new Node("H");
// Add edges: A -> B
A.neighbors.add(B);
// B -> G, B -> C, B -> D
B.neighbors.add(G);
B.neighbors.add(C);
B.neighbors.add(D);
// C -> D
C.neighbors.add(D);
// D -> E
D.neighbors.add(E);
// E -> F, E -> G
E.neighbors.add(F);
E.neighbors.add(G);
// G -> H
G.neighbors.add(H);
// Put all nodes in a linked list
Node[] nodes = {A, B, C, D, E, F, G, H};
// Perform DFS starting from node A
dfs(A);
}
public static void dfs(Node node) {
// Mark the current node as visited
node.visited = true;
System.out.print(node.name + " ");
// Recursively visit all unvisited neighbors
for (Node neighbor : node.neighbors) {
if (!neighbor.visited) {
dfs(neighbor);
}
}
}
}
```

This prints:

```
A B G H C D E F
```

Here, the the DFS algorithm **starts** at node A and visits its neighbors B, G, H, C, D, E, F in that order

- Our DFS algorithm starts at node A and visits its only neighbor: node B.
- Then the algorithm visits node G, which is a neighbor of B, and then node H, which is a neighbor of G.
- After visiting all the nodes reachable from node A, the algorithm
*backtracks*to node B and visits its other neighbor: node C. - Node C has a neighbor, node D, which the algorithm then visits.
- Finally, the algorithm backtracks to node E and visits its neighbors, nodes F and G, in that order.

The `isVisited`

variable is used to **keep a track** of which nodes have been visited by the DFS algorithm already. It is important to mark a node as visited when it is first encountered, as this helps the algorithm avoid visiting the same node multiple times and getting stuck in an infinite loop. For example if we have the following graph:

```
A -- B
| |
C -- D
```

If we start the DFS algorithm at node A and do **not** mark nodes as visited, the algorithm will visit node B and then follow the the graph through nodes D and C back to A. It will then repeat indefinitely and will get stuck in an infinite loop. This is why we must mark nodes as visited.

## Iterative DFS without using Recursion

Alternatively, we can implement DFS without recursion using a Stack. The `dfsIterative()`

method below takes a starting node as its argument and then performs DFS on the graph starting from that node. It uses Stack data structure to store the nodes that need to be visited and marks each node as visited after visiting them. It uses Stack (as opposed to Queue) because DFS explores the depth of the graph first before exploring its breadth.

```
public static void dfsIterative(Node start) {
Stack<Node> stack = new Stack<>();
stack.push(start);
start.visited = true;
while (!stack.isEmpty()) {
Node current = stack.pop();
System.out.print(current.name + " ");
for (Node neighbor : current.neighbors) {
if (!neighbor.visited) {
stack.push(neighbor);
neighbor.visited = true;
}
}
}
}
```