36. BREADTH FIRST SEARCH IN JAVA

Code:

import java.io.*;

import java.util.Scanner;

class Queue

{

    int items[]=new int[10];

    int front,rear;

    Queue()

    {

        front=0;

        rear=-1;

    }

    void Insert(int e)

    {

        if(rear==9)

            System.out.println("Queue overflow");

        else

            items[++rear]=e;

    }

    int Empty()

    {

        return(rear<front? 1:0);

    }

    int Remove()

    {

        int x=0;

        if(Empty()==1)

        {

            System.out.println("Queue Underflow");

            return 0;

        }

        else

        {

            x=items[front++];

            return x;

        }

    }

}

class Graph

{

    int MAXSIZE=10;

    int adj[][]=new int[MAXSIZE][MAXSIZE];

    int visited[]=new int [MAXSIZE];

    Queue q=new Queue();

    void createGraph()

    {

        int n,i,j,parent,adj_parent,initial_node;

        int  ans=0,ans1=0;

        System.out.print("\nEnter total number elements in a Undirected Graph :");

        n=getNumber();

        for (i=1;i<=n;i++)

            for( j=1;j<=n;j++)

                adj[i][j]=0;

        for (int c=1;c<=50;c++)

            visited[c]=0;

        System.out.println("\nEnter graph structure for BFS  ");

        do

        {

            System.out.print("\nEnter parent node :");

            parent=getNumber();

            do

            {

                System.out.print("\nEnter adjacent node for node "+parent+ " : ");

                adj_parent=getNumber();

                adj[parent][adj_parent]=1;

                adj[adj_parent][parent]=1;

                System.out.print("\nContinue to add adjacent node for "+parent+"(1/0)?");

                ans1= getNumber();

            } while (ans1==1);

            System.out.print("\nContinue to add graph node?");

            ans= getNumber();

        }while (ans ==1);

        System.out.print("\nAdjacency matrix for your graph is :\n");

        for (i=1;i<=n;i++)

        {

            for (j=1;j<=n;j++)

            System.out.print(" "+adj[i][j]);

            System.out.print("\n");

        }

        System.out.println("\nYour Undirected Graph is :");

        for (i=1;i<=n;i++)

        {

            System.out.print("\nVertex "+i+"is connected to : ");

            for (j=1;j<=n;j++)

            {

                if (adj[i][j]==1)

                    System.out.print(" "+j);

            }

        }

        System.out.println("\nEnter the initial node for BFS traversal:");

        initial_node=getNumber();

        BFS (initial_node, n);

    }

    void BFS (int initial_node,int n)

    {

        int u,i;

        u = initial_node;

        visited[initial_node]=1;

        System.out.println("\nBFS traversal for given graph is : ");

        System.out.print(initial_node);

        q.Insert(initial_node);

        while(q.Empty()==0)

        {

            u = q.Remove();

            for (i=1;i<=n;i++)

            {

                if((adj[u][i]==1) && (visited[i]==0))

                {

                    q.Insert(i);

                    visited[i]=1;

                    System.out.print(" "+i);

                }

            }

        }

    }

    int getNumber()

    {

        int ne=0;

        Scanner in = new Scanner(System.in);

        ne=in.nextInt();

        return ne;

    }

}

public class BFS

{

    public static void main(String args[])

    {

        Graph g=new Graph();

        g.createGraph();

    }

}

Need the code??

Download Link = https://www.dropbox.com/s/719720g45rn2o6o/bfs.docx