How to implement depth first search algorithm(DFS) using java.

DFS (Depth first search) Traversal algorithm can be applied to either Tree or Graph.

fig.1

Consider above bi-directional graph, where in there are 10 nodes. If one wants to traverse from node-0 to node-9 Using DFS then in below sequence, nodes will be discovered.

1. node-0 will be added to the stack{0}.
2. node-0 will be removed and node-1 & 7 will be added{1,7}.
3. node-7 will be removed and node-6 & 8 will be added {1,6,8}.
4. node-8 will be removed and node-2 will be added{1,6,2}.
5. node-2 will be removed and node-3 & 5 will be added{1,6,3,5}.
6. node-5 will be removed and node-4 will be added as node-2 & 3 are already visited{1,6,3,4}.
7. node-4 will be removed and node-9 will be added{1,6,3,9}.
8. node-9 will be removed{1,6,3}.
9. node-3 will be removed{1,6}.
10. node-6 will be removed{1}. 
11. node-1 will be removed{}.

So, {0,7,8,2,5,4,9,3,6,1} will be the node traversal order.

Solution:
Below is the implementation of DFS in java using Stack as a data structure,

package com.mayank4java.algorithms;

import java.util.Stack;

public class DFSTraversalAlgorithm {
private int[][] graph;
private boolean[] isVisited;

public DFSTraversalAlgorithm(int noOfNodes) {
graph = new int[noOfNodes][noOfNodes];
isVisited = new boolean[noOfNodes];
}

public void addLink(int srcNode, int destNode) {
graph[srcNode][destNode] = 1;
graph[destNode][srcNode] = 1;
}

public void doDFS(int startNode) {
System.out.println("DFSTraversalAlgorithm.doDFS()");

Stack<Integer> stack = new Stack<Integer>();
stack.push(startNode);
isVisited[startNode] = true;
while (!stack.isEmpty()) {
int a = stack.pop();
System.out.println("@Node : " + a);
int[] row = graph[a];

for (int i = 0; i < row.length; i++) {

if (row[i] != 0 && !(isVisited[i])) {
stack.push(i);
isVisited[i] = true;
}
}
}
}

public static void main(String[] args) {
DFSTraversalAlgorithm graph = new DFSTraversalAlgorithm(10);
graph.addLink(0, 1);
graph.addLink(0, 7);
graph.addLink(7, 1);
graph.addLink(1, 2);
graph.addLink(7, 8);
graph.addLink(7, 6);
graph.addLink(2, 8);
graph.addLink(8, 6);
graph.addLink(6, 5);
graph.addLink(2, 5);
graph.addLink(2, 3);
graph.addLink(3, 5);
graph.addLink(3, 4);
graph.addLink(5, 4);
graph.addLink(4, 9);

graph.doDFS(0);
}

}

That is it folks!😃

Hope this post helped you.Also don't forget to share and leave your comments below.