Depth First Search (DFS) algorithm in java

Depth-First Search

Depth First Search (DFS) is a searching algorithm that starts searching the destination from the root to the last depth of each branch first, then goes to the next branch to search the destination.
The animation will make the concept more clear.

To learn DFS, you can download a complete PowerPoint slide on DFS.

Then for implement Depth First Search (DFS), you can use the following java code:

import java.util.*;
  public class Dfs {
      public static int WHITE=1, GREY=2, BLACK=3, INF=310000, NIL=-1;
      public int num_v, num_e, time=0;
      public int adj[][] = new int[20][20];
      public int color[] = new int[20];
      public int p[] = new int[20];
      public int d[] = new int[20];
      public int f[] = new int[20];
  public void initialization() {
     int k,j;
     for(k=0;k<20;k++)
     {
         for(j=0;j<20;j++)
         {
             adj[k][j]=0;
         }
     }
 }
 public void build_adj_matrix() {
     int i,a,b;
     Scanner g=new Scanner(System.in);
     num_v=g.nextInt();
     num_e=g.nextInt();
     for(i=1;i<=num_e;i++)
     {
         a=g.nextInt();
         b=g.nextInt();
         adj[a][b]=1;
         //adj[b][a]=1;
     }
 }
 public void DFS() {
     int i,u;
     for(i=1;i<=num_v;i++)
     {
         color[i]=WHITE;
         p[i]=NIL;
     }
      for(u=1;u<=num_v;u++)
     {
         if(color[u]==WHITE)
             DFS_Visit(u);
     }
  }
  public void DFS_Visit(int u) {
     int i, v;
     color[u]=GREY;
     time = time+1;
     d[u] = time;
      for(v=1;v<=num_v;v++)
     {
         if(adj[u][v]==1)
         {
             if(color[v]==WHITE)
             {
                 p[v]=u;
                 DFS_Visit(v);
             }
         }
     }
     color[u]=BLACK;
     time = time+1;
     f[u] = time; }
  public void distance_output() {
     int i;
     System.out.println("Discovery time and finish time of vertices:");
     for(i=1;i<=num_v;i++)
     {
         System.out.println("node "+i+" is "+d[i]+"/"+f[i]);
     }
 }
      public static void main(String[] args) {
         Dfs g = new Dfs();
         g.initialization();
         g.build_adj_matrix();
         g.DFS();
         g.distance_output();
     }
 }

You can practice Depth First Search (DFS) from here.

Happy coding...

Depth First Search (DFS) algorithm in java