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

No comments:

Post a Comment

Which is the Best Photo Watermarking Software

Photo Theft is becoming more and more common in the web with the outburst of social websites like Facebook,Google Plus and Image sharing se...