Saturday, April 16, 2011

Breadth First Search with Queue


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();
    }
}