## 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 SIZE_GRAPH=20;
public int nVertex;
Vertex[] vertexList;
stack st;
public Graph1(){
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++){
}
}
}
vertexList[nVertex++]=new Vertex(n);
}
}
public void displayVertex(int n){
System.out.println(vertexList[n].v+"->\t");
}
public int getUnvisitedVertex(int v){
for(int i=0;i<nVertex;i++){
return i;
}
return -1;
}
for(int i=0;i<nVertex;i++){
for(int j=0;j<nVertex;j++){
}
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.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 SIZE_GRAPH=20;
public int nVertex;
Vertex[] vertexList;
stack st;
public Graph1(){
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++){
}
}
}
vertexList[nVertex++]=new Vertex(n);
}
}
public void displayVertex(int n){
System.out.println(vertexList[n].v+"->\t");
}
public int getUnvisitedVertex(int v){
for(int i=0;i<nVertex;i++){
return i;
}
return -1;
}
for(int i=0;i<nVertex;i++){
for(int j=0;j<nVertex;j++){
}
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();
`A->B->C->D`