Breadth First Search

Input	No. of nodes in graph (tested for 10 nodes) and its adjacency matrix 
Output	Breadth First traversal of Graph
Complexity	O(V+E)

BFS(G)
1. Initialize all vertices to the ready state (STATUS = 1)
2.  Put the starting vertex A in QUEUE and change the status of A to the waiting state (STATUS = 2). 
3.  Repeat Steps 4 and 5 until QUEUE is empty.
4. Remove the front vertex N of QUEUE. Process N, and set STATUS (N) = 3, the processed state. 
5.  Examine each neighbour J of N
(a) If STATUS (J) = 1 (ready state), add J to the rear of QUEUE and reset STATUS (J) - 2 (waiting state). 
(b) If STATUS (J) = 2 (waiting state) or STATUS (J) = 3 (processed state), ignore the vertex J. 
     	[End of Step 3 loop.] 
6. Exit.

//WAP to implement Breadth First Search

#include<stdio.h>
#include<conio.h>
int n,adj[10][10],visited[10];
void input();
void bfs(int);

int main()
{
	int s;
	printf("Enter no. of nodes in a Graph ");
	scanf("%d",&n);
	input();
	printf("From which node u wanna start bfs ");
	scanf("%d",&s);
	if(s>n)
		printf("Invalid node ");
	else
	{
		printf("BFS output is :\n");
		bfs(s);
	}
	getch();
}

void input()
{
	int i,j,nbr;
	char ch;
	for(i=1;i<=n;i++)
	for(j=1;j<=n;j++)
		adj[i][j]=0;	//initialise adjacency matrix to 0
	for(i=1;i<=n;i++)
	{
		printf("Enter neighbour(s) of %d\n",i);
		ch='y';
		while(ch=='y')	//input neighbour of each vertex
		{
			scanf("%d",&nbr);
			if(nbr>n)
			{
			printf("Invalid neighbour");
			break;
			}
			adj[i][nbr]=1;
			adj[nbr][i]=1;
			printf("Wanna add more neighbour(y/n): ");
			fflush(stdin);
			scanf("%c",&ch);
		}
	}
	printf("adj mat. is :\n");	//print the adjacency matrix
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			printf("%d\t",adj[i][j]);
		}
		printf("\n");
	}
}

void bfs(int s)
{
	int queue[10];
	int left=1,right=1,i,j,flag,out;
	for(i=0;i<=n;i++)
	{
		visited[i]=0;	//initialise every vertex to be non visited
	}
	visited[s]=1;		//initialise starting vertex to be visited
	i=1;
	queue[right]=s;
	while(i<=n)
	{
		printf(" %d",queue[right]);	//print sequence of output in BFS
		out=queue[right];
		for(j=1;j<=n;j++)
		{
		if(adj[out][j]==1&&visited[j]==0)	//check for adjacent node with non visited nature
		{
			flag=right;
			visited[j]=1;
			while(flag>=1)
			{
			queue[flag+1]=queue[flag];
			flag--;
			}
			queue[left]=j;
			right++;
		}
		}
		right--;
		i++;
		out=queue[right];
	}
}

import java.io.*;
class bfs1
{
public static void main(String args[]) throws IOException
{
	int i,n,j,k;
	System.out.println("No. of vertices :") ;
	           BufferedReader br= new BufferedReader (new InputStreamReader(System.in));
	n =Integer.parseInt(br.readLine());
	int q[] = new int[10];
	int m[] = new int[10];
	int a[][] = new int[10][10];
	for (i=0; i<10; i++)
	{
		m[i] = 0;
	}
	System.out.println("\n\nEnter 1 if edge is present, 0 if not");
	for (i=0; i<n; i++)
	{
		System.out.println("\n");
		for (j=i; j<n; j++)
		{
			System.out.println("Edge between " + (i+1) + " and " + (j+1)+ ":" );
			
	    		a[i][j]=Integer.parseInt(br.readLine());
			a[j][i]=a[i][j];	
		}
		a[i][i]=0;
	}
	System.out.println("\nOrder of accessed nodes : \n");
	q[0] = 0; m[0] = 1;
        int u;
        int node=1;
     int  beg1=1, beg=0;
     while(node>0)
    {
  
       u=q[beg];beg++;
       System.out.println("  " +(u+1));
       node--;
       for(j=0;j<n;j++)
       {
         if(a[u][j]==1)
          {
            if(m[j]==0)
             {  
               m[j]=1;
               q[beg1]=j;
               node++;
		beg1++;
              }
          }
       }
    }    
  }
}