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