TOPIC: DEPTH FIRST SEARCH IN JAVA.
SEIT
DATE:13/9/2012
*/
import java.io.*;
class Stack
{
int stk[]=new int[20];
int top;
Stack()
{
top=-1;
}
void push(int i)
{
if(top==19)
System.out.println("Stack Overflow!");
else
stk[++top]=i;
}
int peek()
{
return stk[top];
}
int pop()
{
if(this.isEmpty())
{
System.out.println("underflow");
return 0;}
else
{
System.out.println(stk[top]);
return stk[top--];
}}
boolean isEmpty()
{
if(top<0)
return true;
else
return false;
}
}
class vertex
{
int no;
boolean isv;
vertex()
{
isv=false;
}
vertex(int b)
{
no=b;
isv=false;
}
}
class graph
{
vertex vl[];
int adjm[][];
int nv=0;
Stack s;
graph()
{
System.out.println("our default size of vertex list is 20 and matrix is 20x20");
vl=new vertex[20];
adjm=new int[20][20];
for(int i=0;i<20;i++)
{
for(int j=0;j<20;j++)
{
adjm[i][j]=0;
}
}
s=new Stack();
}
void addVertex(int l)
{
vl[nv++]=new vertex(l);
}
void addEdge(int a,int b)throws Exception
{ if(a>20 || b>20)
throw new Exception("Vertex cannot be defined out of the boundary");
adjm[a][b]=1;
adjm[b][a]=1;
}
void display()
{
for (int i=0;i<nv;i++)
System.out.print(vl[i].no+" ");
}
void display(int v)
{
System.out.println(vl[v].no);
}
void dfs()
{
vl[0].isv=true;
display (0);
s.push(0);
for(int j=1;j<nv;j++)
{
int v=getAdj(s.peek());
if(v==-1)
s.pop();
else
{
vl[v].isv=true;
display (v);
s.push(v);
}
}
for(int i=0;i<nv;i++)
{
vl[i].isv=false;
}
}
int getAdj(int v)
{
for(int i=0;i<nv;i++)
if(v!=i)
if(adjm[v][i]==1 && vl[i].isv==false)
return i;
return -1;
}
}
class main
{
public static void main(String args[])throws Exception
{
graph g=new graph();
InputStreamReader isr=new InputStreamReader(System.in);
BufferedReader br=new BufferedReader(isr);
int ch;
PrintStream p=System.out;
one: for(int i=10;i>0;i++)
{
p.println();
p.println("1>INSERT VERTEX");
p.println("2>DISPLAY");
p.println("3>Depth First Search");
p.println("4>ADD EDGE");
p.println("5>EXIT");
ch=Integer.parseInt(br.readLine());
switch (ch)
{
case 1:
int o;
p.println("enter object");
o=Integer.parseInt(br.readLine());
g.addVertex(o);
break;
case 2:
g.display();
break;
case 3:
g.dfs();
break;
case 4:
p.println("enter start vertex");
int a=Integer.parseInt(br.readLine());
p.println("enter end vertex ");
int b=Integer.parseInt(br.readLine());
g.addEdge(a,b);
break;
case 5:
g=null;
System.gc();
break one;
}
}
System.out.println("thank u coded by TG");
}
}
/*
OUTPUT:
our default size of vertex list is 20 and matrix is 20x20
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
1
enter object
1
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
1
enter object
2
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
1
enter object
3
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
1
enter object
4
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
4
enter start vertex
0
enter end vertex
1
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
4
enter start vertex
0
enter end vertex
2
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
4
enter start vertex
1
enter end vertex
3
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
4
enter start vertex
2
enter end vertex
3
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
2
1 2 3 4
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
3
1
2
4
3
1>INSERT VERTEX
2>DISPLAY
3>Depth First Search
4>ADD EDGE
5>EXIT
5
thank u coded by TG
*/
