C++ program to implement Breadth First Search algorithm

C++ program traverse the graph using Breadth First Search algorithm. In second program I have created adjacency list from adjacency matrix and travese it using BFS traversal.

C++ program to implement Breadth First Search algorithm

#include<iostream>
using namespace std;
class graph
{
    int a[10][10],n,start;
public:
    void getdata();
    void bfs_traverse();
};
void graph::getdata()
{
    cout<<"Enter the number of vertices in the graph ";
    cin>>n;
    cout<<"Enter the adjacency matrix of graph "<<endl;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin>>a[i][j];
    cout<<"Enter the vertex from which you want to traverse ";
    cin>>start;
}
void graph::bfs_traverse()
{
    int *visited= new int[n];
    int queue[10],front=-1,rear=0,i;
    for(int j=0;j<n;j++)
        visited[j]=0;
    cout<<"Traversing the graph using breadth first search algorithm : "<<endl;
    queue[rear]=start;
    visited[start]=1;
    while(front!=rear)
    {
        cout<<queue[++front]<<endl;
        i=queue[front];
        for(int j=0;j<n;j++)
            if(a[i][j]!=0&&visited[j]!=1)
            {
              queue[++rear]=j;
              visited[j]=1;
            }
    }
}
int main()
{
    graph bfs;
    bfs.getdata();
    bfs.bfs_traverse();
    return 0;
}

C++ program to create adjacency list and implement Breadth First Search algorithm

#include<iostream>
using namespace std;
struct graphnode
{
    int ver_no;
    graphnode *next;
};
class graph
{
    int a[10][10],n,start;
    graphnode *ver[10];
public:
    graph()
    {
        for(int i=0;i<10;i++)
            ver[i]=NULL;
    }
    void getdata();
    void bfs_traverse();
    void matrix_to_list();
};
void graph::getdata()
{
    cout<<"Enter the number of vertices ";
    cin>>n;
    cout<<"Enter the adjacency matrix\n";
    for(int i=0;i<n;i++)
        for(int y=0;y<n;y++)
            cin>>a[i][y];
    cout<<"Enter the starting node ";
    cin>>start;
}
void graph::matrix_to_list()
{
    graphnode *ne,*temp;
    for(int i=0;i<n;i++)
    {
        for(int y=0;y<n;y++)
        {
            if(a[i][y]!=0)
            {
                ne=new graphnode;
                ne->ver_no=y;
                ne->next=NULL;
                if(ver[i]==NULL)
                {
                    ver[i]=ne;
                    temp=ne;
                }
                else
                {
                    temp->next=ne;
                    temp=temp->next;
                }
            }
        }
    }
}
void graph::bfs_traverse()
{
    int *visited= new int[n];
    graphnode *temp;
    int queue[10],front=-1,rear=0,i;
    for(int j=0;j<n;j++)
        visited[j]=0;
    cout<<"The breadth first search of the graph is : "<<endl;
    queue[rear]=start;
    visited[start]=1;
    while(front!=rear)
    {
        cout<<queue[++front]<<endl;
        temp=ver[queue[front]];
        while(temp!=NULL)
        {
            if(visited[temp->ver_no]!=1)
            {
                queue[++rear]=temp->ver_no;
                visited[temp->ver_no]=1;
            }
            temp=temp->next;
        }
    }
}
int main()
{
    graph bfs;
    bfs.getdata();
    bfs.matrix_to_list();
    bfs.bfs_traverse();
    return 0;
}