bfs.java

java program Webmaster will activate your member account after checking your files. If you do not w

//Name: 
//Roll No.: 
//S.E.(comps)

//Program To Implement Bredth First Search

import java.io.*;
import java.util.*;
class Queues
{
	int items[]=new int[10];
	int front,rear;
	Queues()
	{
		front=0;
		rear=-1;
	}

	void insert(int e)
	{
		if(rear==9)
			System.out.println("Queue Overflow");
		else
			items[++rear]=e;
	}

	boolean empty()
	{
		if(rear<front)
			return true;
		else
			return false;
	}

	int remove()
	{
		return items[front++];
	}

	int search(int key)
	{
		int i=0;
		while(i<10)
			if(key==items[i])
			return i;
		else
			i++;
		return -1;
	}
}

class BFS
{
	static int v;
	static int adj[][];
	static boolean visited[];
	public static void main(String args[])
	{
		Scanner read=new Scanner(System.in);
		int i,j;
		System.out.println("Enter the no. of vertices in the graph: ");
		v=read.nextInt();
		adj=new int[v+1][v+1];
		visited=new boolean[v+1];
		for(i=1;i<=v;i++)
		{
			for(j=1;j<=v;j++)
			{
				System.out.println("Is vertex "+j+" adjacent to vertex "+i);
				System.out.println();
				System.out.println("Enter 1 if yes and 0 if no");
                adj[i][j]=read.nextInt();
			}
		}
		for(i=1;i<=v;i++)
		{
			visited[i]=false;
			System.out.println("Breadth First Search of the graph is as shown: "); 
			for(i=1;i<=v;i++)
			{
				if(visited[i]==false)
				bfs(i);
			}
		}
	}
	public static void bfs(int k)
	{
		int j;
		Queues q=new Queues();
		q.insert(k);
		while(!q.empty())
		{
			k=q.remove();
			visited[k]=true;
		System.out.print(k+" ");
        for(j=1;j<=v;j++)
			if(adj[k][j]==1)
			if(visited[j]==false && q.search(j)==-1)
			q.insert(j);
		}
	}
}

/*Output:
Enter the no. of vertices in the graph:
5
Is vertex 1 adjacent to vertex 1

Enter 1 if yes and 0 if no
1
Is vertex 2 adjacent to vertex 1

Enter 1 if yes and 0 if no
1
Is vertex 3 adjacent to vertex 1

Enter 1 if yes and 0 if no
1
Is vertex 4 adjacent to vertex 1

Enter 1 if yes and 0 if no
0
Is vertex 5 adjacent to vertex 1

Enter 1 if yes and 0 if no
0
Is vertex 1 adjacent to vertex 2

Enter 1 if yes and 0 if no
0
Is vertex 2 adjacent to vertex 2

Enter 1 if yes and 0 if no
1
Is vertex 3 adjacent to vertex 2

Enter 1 if yes and 0 if no
0
Is vertex 4 adjacent to vertex 2

Enter 1 if yes and 0 if no
1
Is vertex 5 adjacent to vertex 2

Enter 1 if yes and 0 if no
1
Is vertex 1 adjacent to vertex 3

Enter 1 if yes and 0 if no
0
Is vertex 2 adjacent to vertex 3

Enter 1 if yes and 0 if no
0
Is vertex 3 adjacent to vertex 3

Enter 1 if yes and 0 if no
1
Is vertex 4 adjacent to vertex 3

Enter 1 if yes and 0 if no
0
Is vertex 5 adjacent to vertex 3

Enter 1 if yes and 0 if no
0
Is vertex 1 adjacent to vertex 4

Enter 1 if yes and 0 if no
0
Is vertex 2 adjacent to vertex 4

Enter 1 if yes and 0 if no
0
Is vertex 3 adjacent to vertex 4

Enter 1 if yes and 0 if no
0
Is vertex 4 adjacent to vertex 4

Enter 1 if yes and 0 if no
1
Is vertex 5 adjacent to vertex 4

Enter 1 if yes and 0 if no
0
Is vertex 1 adjacent to vertex 5

Enter 1 if yes and 0 if no
0
Is vertex 2 adjacent to vertex 5

Enter 1 if yes and 0 if no
0
Is vertex 3 adjacent to vertex 5

Enter 1 if yes and 0 if no
0
Is vertex 4 adjacent to vertex 5

Enter 1 if yes and 0 if no
0
Is vertex 5 adjacent to vertex 5

Enter 1 if yes and 0 if no
1
Breadth First Search of the graph is as shown:
1 2 3 4 5
*/