Tuesday, September 21, 2010

DSA:Depth First Search

package javaapplication8;
import java.io.*;
class graph
{
    int a[][];
    int f[];
    int vtx;

    graph(int v)
    {
        vtx=v;
        f=new int[vtx+1];
        a=new int[vtx+1][vtx+1];
    }
    void getdata()throws Exception
    {
        int i,j;
            for(i=1;i<(vtx+1);i++)
              {
                 for(j=1;j
                    {
                        System.out.println(i+"->"+j);
                         System.out.print("\t 0-->no\t 1-->yes\n");
                            InputStreamReader isrx=new InputStreamReader(System.in);
                            BufferedReader brx=new BufferedReader(isrx);
                             int bx=Integer.parseInt(brx.readLine());
          
                            a[i][j]=bx;
        }
    }
    }
    void visited(int s)
        {
            f[s]=1;
        }
    void dft(int s)
        {
            visited(s);
            System.out.println(s+"");
              for(int i=s,j=1;j<(vtx+1);j++)
                  {
                    if(a[i][j]==1)
                       {
                         if(f[j]==0)
                            {
                             dft(j);
                            }
              
                        }
                    }
            }
        void disgraph()
            {
                for(int i=1;i<(vtx+1);i++)
                { for(int j=1;j<(vtx+1);j++)
                     {     System.out.print(a[i][j]+"\t ");
                          
                     }
                  System.out.println("");
        }
}
}
    class javaapplication8
    {
       public static void main(String[] args)throws Exception
     { int h;
                System.out.println("enter the number of vertex");
               InputStreamReader isr2=new InputStreamReader(System.in);
                BufferedReader br2=new BufferedReader(isr2);
                h=Integer.parseInt(br2.readLine());
                graph g=new graph(h);
                g.getdata();
                g.disgraph();
                System.out.println ("........DFT.............");      
                g.dft(1);
              
     }
   }

No comments:

Post a Comment