Friday, 22 August 2014

DSPS: Revised version of GRAPHS (BFS)

#include<iostream>
using namespace std;
#define size 10
#define true 1
#define false 0
class graph
{
public:
    int g[size][size];
    int visit[size],rear,front,q[size];
    int n,e;
public:
    graph();
    void getmatrix();
    void displaygraph();
    void bfs(int);
};

graph::graph()
{
 for(int i=0;i<size;i++)
     {
         for(int j=0;j<size;j++)
         {
             g[i][j]=false;
         }
     }
 for(int i=0;i<size;i++)
     {
     visit[i]=false;
     }

}
void graph::getmatrix()
{

    int v1,v2;
    cout<<"Enter no. of nodes:";
    cin>>n;
    cout<<"Enter no. of edges:";
    cin>>e;
    for(int i=0;i<e;i++)
    {
        cout<<"Enter edge in the form of V1 and V2:";
        cin>>v1>>v2;
        g[v1][v2]=g[v2][v1]=true;
    }

    cout<<"Entered Graph is"<<endl;
    for(int k=0;k<n;k++)
         {
        cout<<"|";
             for(int l=0;l<n;l++)
             {
                 cout<<g[k][l]<<"\t";

             }
             cout<<"|";
             cout<<endl;
           
         }
}
void graph::bfs(int v1)
{
    int v2;
    front=rear=-1;
    visit[v1]=true;
    q[++rear]=v1;

    while(front!=rear)
    {
     v1=q[++front];
     cout<<v1<<" ";
     for(v2=0;v2<n;v2++)
      {
        if(g[v1][v2]==true && visit[v2]==false)
        {
        q[++rear]=v2;
        visit[v2]=true;
        }
    }
   }
}



int main()
{
    graph g;
    int v;
    g.getmatrix();
    cout<<"enter the starting vertex for BFS traversal";
    cin>>v;
    cout<<"The BFS tarversal is:";
    g.bfs(v);
    return 0;
}

No comments:

Post a Comment