# Depth First Search Algorithm implementation in Java.

Depth First Search(DFS) Algorithm is used for the graph traversal and it internally uses a stack which follows LIFO(Last In First Out) principle. In DFS we are trying to go away from the starting source vertex into the graph as deep as possible until we have to backtrack to the preceding vertex.

Initially all the vertices are marked unvisited(false). The DFS algorithm starts at the vertex u in the graph. By starting at vertex u it considers the edges from u to other vertices. If the edge leads to an already visited vertex, then backtrack to current vertex u. If the edge leads to an unvisited vertex, then go to that vertex and start processing from that vertex. This means the new vertex becomes current vertex. Follow this procedure until we reach dead-end. At this point start backtracking.

Code :

import java.util.*;
class Graph {

```    private int V;

Graph(int v)
{
V=v;
for(int i=0;i<v;i++)
{
}
}

{
}
void DFS(int v)
{
boolean visited[]= new boolean[V];

DFS1(v,visited);
}

void DFS1(int v, boolean visited[])
{
visited[v]=true;
System.out.print(v+" -> ");

while(i.hasNext())
{
int n = i.next();
if(!visited[n]) {
DFS1(n,visited);
}
}
}

public static void main(String arg[]) {
Graph g = new Graph(4);

g.DFS(2);//source
}
```

}

Time Complexity : O(V + E)

Applications :

1- Topological Sorting

2-Detection of Cycle in Graph

3-For unweighted graph, DFS produces minimum spanning tree.