import java.io.*;
import java.util.*;
class Graph
{
int v[][],q[];
boolean flag[];
int rear=-1,front=-1,size,v1,v2;
Graph(int siz)
{
size=siz;
v=new int[size][size];
q=new int[size];
flag=new boolean[size];
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
v[i][j]=0;
}
q[i]=0;
flag[i]=false;
}
}
void create()throws Exception
{
DataInputStream di=new DataInputStream(System.in);
char ch='y';
do
{
System.out.println("\nEnter the edges of graph : ");
v1=Integer.parseInt(di.readLine());
v2=Integer.parseInt(di.readLine());
v[v1][v2]=1;
v[v2][v1]=1;
System.out.println("\nDo you want to enter more edges(y/n):");
String s=di.readLine();
ch=s.charAt(0);
}while(ch!='n');
}
void mat()throws Exception
{
System.out.println("\nMatrix for the Graph is:\n");
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
System.out.print(v[i][j]+" ");
}
System.out.println();
}
}
void bfs(int x)throws Exception
{
rear++;
q[rear]=x;
flag[rear]=true;
for(int i=0;i<size;i++)
{
x=q[++front];
System.out.println(x);
for(int j=0;j<size;j++)
{
if(v[x][j]==1 && flag[j]==false)
{
flag[j]=true;
q[++rear]=j;
}
}
}
for(int i=0;i<size;i++)
{
flag[i]=false;
}
}
void dfs(int i)throws Exception
{
System.out.println(i);
flag[i]=true;
for(int j=0;j<size;j++)
{
if(v[i][j]==1&&flag[j]==false)
{
dfs(j);
}
}
}
public static void main(String args[ ])throws Exception
{
int siz,x;
DataInputStream dis=new DataInputStream(System.in);
System.out.print("\nEnter total no of vertices: ");
siz=Integer.parseInt(dis.readLine());
Graph g=new Graph(siz);
try
{
g.create();
g.mat();
System.out.println("\nBreadth First Search Traversal");
System.out.print("\nEnter vertex from which you want to traverse:");
x=Integer.parseInt(dis.readLine());
g.bfs(x);
System.out.println("\nDepth First search Traversal");
System.out.print("\nEnter vertex from which you want to traverse:");
x=Integer.parseInt(dis.readLine());
g.dfs(x);
}
catch(Exception e)
{}
}
}
/*
OUTPUT
C:\java\bin>javac Graph.java
C:\java\bin>java Graph
Enter total no of vertices: 4
Enter the edges of graph :
0
1
Do you want to enter more edges(y/n):
y
Enter the edges of graph :
0
2
Do you want to enter more edges(y/n):
y
Enter the edges of graph :
1
3
Do you want to enter more edges(y/n):
y
Enter the edges of graph :
2
3
Do you want to enter more edges(y/n):
n
Matrix for the Graph is:
0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0
Breadth First Search Traversal
Enter vertex from which you want to traverse:0
0
1
2
3
Depth First search Traversal
Enter vertex from which you want to traverse:0
0
1
3
2
*/
No comments:
Post a Comment