Depth First Traversal or DFS for a Graph using Simple Java code

Depth First Traversal (or Search) for a graph is similar to Depth First Traversal of a tree. The only catch here is, unlike trees, graphs may contain cycles, so we may come to the same node again. To avoid processing a node more than once, we use a boolean visited array. 
For example, in the following graph, we start traversal from vertex 2. When we come to vertex 0, we look for all adjacent vertices of it. 2 is also an adjacent vertex of 0. If we don’t mark visited vertices, then 2 will be processed again and it will become a non-terminating process. A Depth First Traversal of the following graph is 2, 0, 1, 3.

First of all make a stack class:-

class stack{
public int[] s;
public int top;
public int SIZE_STACK=20;
public stack(){
s=new int[SIZE_STACK];
top=-1;
}
public void push(int x){
if(top>=SIZE_STACK){
System.out.println("Stack is Full");
}
s[++top]=x;
}
public int pop(){
if(top==-1){
System.out.println("Stack is Empty,Nothing to Pop");
}else{
return s[top--];
}
return -1;
}
public int peek(){
return s[top];
}
public void display(){
for(int i=0;i<=top;i++){
System.out.println(s[i]+"\t");
}
}
public boolean isEmpty(){
if(top==-1)
return true;
return false;
}
}

Now Make a Vertex Class:-

class Vertex{
public char v;
boolean wasVisited;
public Vertex(char n){
v=n;
wasVisited=false;
}
}

Now Make the Graph Class:-

class Graph1{
public int[][] adjMatrix;
public int SIZE_GRAPH=20;
public int nVertex;
Vertex[] vertexList;
stack st;
public Graph1(){
adjMatrix=new int[SIZE_GRAPH][SIZE_GRAPH];
vertexList=new Vertex[SIZE_GRAPH];
st= new stack();
nVertex=0;
for(int i=0;i<SIZE_GRAPH;i++){
for(int j=0;j<SIZE_GRAPH;j++){
adjMatrix[i][j]=0;
}
}
}
public void addVertex(char n){
vertexList[nVertex++]=new Vertex(n);
}
public void addEdge(int x,int y){
adjMatrix[x][y]=1;
adjMatrix[y][x]=1;
}
public void displayVertex(int n){
System.out.println(vertexList[n].v+"->\t");
}
public int getUnvisitedVertex(int v){
for(int i=0;i<nVertex;i++){
if(adjMatrix[v][i]==1 && vertexList[i].wasVisited==false)
return i;
}
return -1;
}
public void displayAdmatrix(){
for(int i=0;i<nVertex;i++){
for(int j=0;j<nVertex;j++){
System.out.print(adjMatrix[i][j]+"\t");
}
System.out.println();
}
}
public void dfs(){
vertexList[0].wasVisited=true;
displayVertex(0);
st.push(0);
while(!st.isEmpty()){
int v=getUnvisitedVertex(st.peek());
//System.out.println("getUnvisitedVertex:"+v);
//st.display();
if(v==-1){
st.pop();
}else{
st.push(v);
vertexList[v].wasVisited=true;
displayVertex(v);
}
}
for(int i=0;i<nVertex;i++){
vertexList[i].wasVisited=false;
}
}
}


Now make another class for main function:-

class graph{
public static void main(String[] args){
Graph1 g=new Graph1();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addVertex('D');
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.displayAdmatrix();
g.dfs();
}
}

All code:-

import java.util.*;

class stack{
public int[] s;
public int top;
public int SIZE_STACK=20;
public stack(){
s=new int[SIZE_STACK];
top=-1;
}
public void push(int x){
if(top>=SIZE_STACK){
System.out.println("Stack is Full");
}
s[++top]=x;
}
public int pop(){
if(top==-1){
System.out.println("Stack is Empty,Nothing to Pop");
}else{
return s[top--];
}
return -1;
}
public int peek(){
return s[top];
}
public void display(){
for(int i=0;i<=top;i++){
System.out.println(s[i]+"\t");
}
}
public boolean isEmpty(){
if(top==-1)
return true;
return false;
}
}
class Vertex{
public char v;
boolean wasVisited;
public Vertex(char n){
v=n;
wasVisited=false;
}
}
class Graph1{
public int[][] adjMatrix;
public int SIZE_GRAPH=20;
public int nVertex;
Vertex[] vertexList;
stack st;
public Graph1(){
adjMatrix=new int[SIZE_GRAPH][SIZE_GRAPH];
vertexList=new Vertex[SIZE_GRAPH];
st= new stack();
nVertex=0;
for(int i=0;i<SIZE_GRAPH;i++){
for(int j=0;j<SIZE_GRAPH;j++){
adjMatrix[i][j]=0;
}
}
}
public void addVertex(char n){
vertexList[nVertex++]=new Vertex(n);
}
public void addEdge(int x,int y){
adjMatrix[x][y]=1;
adjMatrix[y][x]=1;
}
public void displayVertex(int n){
System.out.println(vertexList[n].v+"->\t");
}
public int getUnvisitedVertex(int v){
for(int i=0;i<nVertex;i++){
if(adjMatrix[v][i]==1 && vertexList[i].wasVisited==false)
return i;
}
return -1;
}
public void displayAdmatrix(){
for(int i=0;i<nVertex;i++){
for(int j=0;j<nVertex;j++){
System.out.print(adjMatrix[i][j]+"\t");
}
System.out.println();
}
}
public void dfs(){
vertexList[0].wasVisited=true;
displayVertex(0);
st.push(0);
while(!st.isEmpty()){
int v=getUnvisitedVertex(st.peek());
//System.out.println("getUnvisitedVertex:"+v);
//st.display();
if(v==-1){
st.pop();
}else{
st.push(v);
vertexList[v].wasVisited=true;
displayVertex(v);
}
}
for(int i=0;i<nVertex;i++){
vertexList[i].wasVisited=false;
}
}
}
class graph{
public static void main(String[] args){
Graph1 g=new Graph1();
g.addVertex('A');
g.addVertex('B');
g.addVertex('C');
g.addVertex('D');
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.displayAdmatrix();
g.dfs();
}
}

Out Put:-

A->B->C->D

Thanks have a good day.