Saturday, August 13, 2011

Depth First Search Program in Java


DFS:Depth First Search is a Method to Traverse a Tree and find the Required Element in a Tree.This Algorithm is referred to as Depth First Search because is Spans the Tree in Various Levels or Depths to Find an Element.

DFS uses a Stack to Insert the Elements of a Tree as it is spanned. Several Variables are used to Indicate whether a Node is Visited ,Unvisited or in Processing State.The Complete Java Source Code to Implement DFS is provided below
 import java.io.*;   
  import java.lang.*;   
  /** Compose  
  * @author www.c-madeeasyblogspot.com   
  */   
  class stack   
  {   
   int a[]=new int[20],top=0;   
   void push(int p)   
   {   
    a[top]=p;   
    top++;   
   }   
   int pop()   
   {   
    int h;   
    top--;   
    h=a[top];   
    return h;   
   }   
  }   
  public class DFS {   
   /**   
   * @param args the command line arguments   
   */   
   public static void main(String[] args) {   
    stack mystack=new stack();   
    int n=0;   
    String[] label=new String[10];   
    int x;   
    int status[]=new int[10];   
    int am[][]=new int[50][50];   
    int a[]=new int[10];   
    DataInputStream get=new DataInputStream(System.in);   
   try   
   {   
   System.out.println("Enter the no of vertices");   
   n=Integer.parseInt(get.readLine());   
   System.out.println("Enter labels");   
   for(int i=0;i<n;i++)   
   {   
    label[i]=get.readLine();   
   }   
    System.out.println("Enter AM");   
    for(int i=0;i<n;i++){   
     for(int j=0;j<n;j++)   
     {   
     am[i][j]=Integer.parseInt(get.readLine());    
     status[i]=1;   
     }   
    }   
     mystack.push(0);   
     status[0]=2;   
     x=mystack.pop();   
     a[0]=x;   
     status[0]=3;   
    for(int i=1;i<n;i++)   
    {   
    for(int j=0;j<n;j++)    
    {   
    if(am[x][j]==1&&status[j]==1)    
    {   
     mystack.push(j);   
     status[j]=2;   
    }   
    }   
    x=mystack.pop();   
    a[i]=x;   
    status[x]=3;   
    }   
    System.out.println("DFS is");   
    for(int i=0;i<n;i++)   
    {   
     int m=a[i];   
     System.out.print(" "+label[m]);   
    }    
   }   
  catch(Exception e)   
   {   
   System.out.println(e.getMessage());   
   }   
   }   
  }   

WJJHAEUVSUQD

7 comments:

Post a Comment

Subscribe

The Source Codes Published in this Blog can be used freely for Educational purposes but should not be reproduced on any other Blog or Website without the consent of the author.