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

6 comments:

  • João Manuel G. Bonin says:
    June 13, 2012 at 7:38 PM

    Good Job!

    What's "Enter labels" and "Enter AM"?

  • Techman says:
    June 13, 2012 at 9:36 PM

    Those are specific values for the Tree Nodes

  • Nidz says:
    August 12, 2012 at 12:40 AM

    y is the status for?

  • CHETAN says:
    August 16, 2012 at 5:52 AM

    not getting what to write in AM
    --chetan

  • majid nawaz says:
    November 25, 2012 at 8:32 AM

    i think AM means Adjacent matrix.

  • NiggaInTheHood says:
    March 14, 2013 at 1:47 AM

    could you do dfs using stacks with pointers in c?

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.