Program:
import java.io.*;
class quelist
{
public int front;
public int rear;
public int maxsize;
public int[] que;
public quelist(int size)
{
maxsize = size;
que = new int[size];
front = rear = -1;
}
public void display()
{
for(int i = front;i<=rear;i++)
System.out.print(que[i]+" ");
}
public void enque(int x)
{
if(front==-1)
front = 0;
que[++rear]=x;
}
public int deque()
{
int temp = que[front];
front = front +1;
return temp;
}
public boolean isempty()
{
return((front>rear)||(front==- 1));
}
}
class vertex
{
public char label;
public boolean wasvisited;
public vertex(char lab)
{
label = lab;
wasvisited = false;
}
}
class graph
{
public final int MAX = 20;
public int nverts;
public int adj[][];
public vertex vlist[];
quelist qu;
public graph()
{
nverts = 0;
vlist = new vertex[MAX];
adj = new int[MAX][MAX];
qu = new quelist(MAX);
for(int i=0;i<MAX;i++)
for(int j=0;j<MAX;j++)
adj[i][j] = 0;
}
public void addver(char lab)
{
vlist[nverts++] = new vertex(lab);
}
public void addedge(int start,int end)
{
adj[start][end] = 1;
adj[end][start] = 1;
}
public int getadjunvis(int i)
{
for(int j=0;j<nverts;j++)
if((adj[i][j]==1)&&(vlist[j]. wasvisited==false))
return j;
return (MAX+1);
}
public void display(int i)
{
System.out.print(vlist[i]. label);
}
public int getind(char l)
{
for(int i=0;i<nverts;i++)
if(vlist[i].label==l)
return i;
return (MAX+1);
}
public void brfs()
{
vlist[0].wasvisited = true;
display(0);
qu.enque(0);
int v2;
while(!(qu.isempty()))
{
int v1 = qu.deque();
while((v2=getadjunvis(v1))!=( MAX+1))
{
vlist[v2].wasvisited = true;
display(v2);
qu.enque(v2);
}
}
System.out.print("\n");
}
}
class bfs
{
public static void main(String args[])throws IOException
{
graph gr = new graph();
InputStreamReader isr = new InputStreamReader(System.in);
BufferedReader br = new BufferedReader(isr);
System.out.println("Enter the number of vertices");
int n = Integer.parseInt(br.readLine() );
System.out.println("Enter the labels for the vertices");
for(int i=0;i<n;i++)
{
String temp = br.readLine();
char ch = temp.charAt(0);
gr.addver(ch);
}
System.out.println("Enter the number of edges");
int edg = Integer.parseInt(br.readLine() );
System.out.println("Enter the vertices which you need to connect");
for(int j=0;j<edg;j++)
{
System.out.println("Enter the first vertex");
String t = br.readLine();
char c = t.charAt(0);
int start = gr.getind(c);
System.out.println("Enter the second vertex");
t = br.readLine();
c = t.charAt(0);
int end = gr.getind(c);
gr.addedge(start,end);
}
System.out.print("The vertices in the graph traversed breadthwise:");
gr.brfs();
}
}
This is my own Blog for user relationship.Our House location of the map 8°15'45"N 77°14'3"E.And in my house located in Mullanganavilai village in Kanyakumari dist. Just tell your commands in this bolg.
Wednesday, October 9, 2013
BFS Program using Queue
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment