C++ Program to  implement Breadth First Search of Graph

Introduction
In this article we are going to implement a C++ program to find the Breadth First Search of an undirected graph.

Problem Statement

Represent a given graph using adjacency list and traverse each node using Breadth First Search (BFS).

Solution

The core idea of breadth first search of a graph is start from any vertex and explore ( visit ) all the vertices connected to it before moving to the next vertex. Keep this repeating till all the vertices are visited, with one condition that each vertex should be visited at once . 
 In the C++ implementation of Breadth First Search ( BFS ) we use Queue data structure. 
 As per the given problem statement ,  we have used Adjacency list ( Linked List  representation of graph) to represent the graph. 

Concept of Breadth First Search ( BFS ) using Queue

We will discuss the concept with a small example given below.
Breadth First Search BFS
Image 1.0

Start from any vertex of graph , let's say from vertex 0 . Enqueue it in queue and mark it as visited. Enqueue all the adjacent vertices of vertex 0 i.e. 1 and 2 mark them as visited . Print vertex 0 and dequeue it.
Now explore either vertex 1 or 2 , it dosen't matter ,we choose 1 for the sake of order. Vertex 2 and vertex 4 are connected to 1 , but as vertex 2 is already visited do not enqueue it . Enqueue vertex 4 and mark it visited. Dequeue 1 and print it . Now explore 2 and repeat the procedure until all the vertices are visited.  

#C++ Program to find BFS of Graph

Download the Code here

#include<iostream>
using namespace std;

 struct node
 {
     int data;
     node *next;
 };
 node *heads[10];

void adjacencyListRepre ( int );

node *createNode (int value);

void display ( int );

void bfs ( int vertices );

void enqueue ( int value );

int dequeue ();

//QUEUE

int Front = -1;
int Rear = -1;
int queue[20];


int main()
{
    int choise;

        int vertices;

        cout<<"Enter the number of vertices :";

        cin>>vertices;
  
    do{

        cout<<"------------------------------------------------------------------------\n";

        cout<<"\t\t\tBreadth First Search \n\n";

        cout<<"\t\t  1.Create a Graph \n";

        cout<<"\t\t  2.Display the Graph \n";

        cout<<"\t\t  3.Breadth First Search \n";

        cout<<"\t\t  4.Exit\ n";

        cout<<"\t  Your choise : ";

        cin>>choise;

        switch(choise)
        {
            case 1:
                {
                  
                       adjacencyListRepre (vertices);
                }

            break;

            case 2:
                         display (vertices);
 
            break;

            case 3:
                           bfs (vertices);      
            break;

        }


    }while(choise<4);

}


void adjacencyListRepre ( int vertices )
{
    int edges,ev;

    for ( int i=0;i<vertices;i++ )

        heads[i] = NULL;

    for ( int i = 0; i < vertices; i++ )
    {
        cout<<"Enter the number of edges connected to vertex "<<i<<" : ";
        cin>>edges;

        for ( int j = 0; j < edges; j++)
        {
            cout<<"Enter the "<<j+1 <<" th edge (Enter only ending vertex): ";
            cin>>ev;

            if ( heads[i]==NULL )

                heads[i] = createNode(ev);

            else
            {
                node *temp = heads[i];

                 while(temp->next!=NULL)

               temp = temp->next;

                temp->next = createNode(ev);

              
            }

        }
    }

  

}
void display (int vertices)
{

for (int i = 0; i < vertices; i++)
    {
        node *temp = heads[i];

        while(temp!=NULL)
            {
                cout<<"Edge from vertex "<<i<<" to verticex "<<temp->data<<"\n";

                temp = temp->next;
            }
            cout<<"\n";
    }
}

node *createNode ( int value )
{
    node *temp =new node;

    temp->data = value;

   temp->next = NULL;

   return temp;
}


void enqueue ( int value )
{
    if (Front ==-1&&Rear == -1)
    {
        Front = 0;
        Rear = 0;
    }
    else
    {
        Rear = Rear +1;
    }
    queue[Rear] =value;
}

int dequeue( )
{
    int x = queue[Front];

    if ( Front==Rear )
    {
        Front = -1;
        Rear = -1;
    }
    else
    {
        Front = Front+1;
    }
    return x;
}

void bfs ( int vertices )
{
    int visited [ vertices ] ;

    for ( int i = 0; i < vertices; i++ )
    {
        visited [i] = 0;
    }

    enqueue(0);

    visited[0] = 1;

    cout<<"\t  BFS is as : ";


    while ( Front!=( -1 ) )
    {
        int x= dequeue();

        cout<<"\t"<<x;

        node *temp = heads [x];

        while ( temp!=NULL )
        {
            if ( !visited[temp->data] )
            {
                enqueue(temp->data);

                visited[temp->data] = 1;
            }
            temp = temp->next;
        }
    }
cout<<"\n";
}

Note :  This code is successfully compiled and run under Linux distribution Ubuntu 18.04 LTS environment .  

Output :

Enter the number of vertices :5
------------------------------------------------------------------------
            Breadth First Search

        1.Create a Graph
        2.Display the Graph
        3.Breadth First Search
        4.Exit
    Your choise : 1
Enter the number of edges connected to vertex 0 : 2
Enter the 1 th edge (Enter only ending vertex): 1
Enter the 2 th edge (Enter only ending vertex): 2
Enter the number of edges connected to vertex 1 : 3
Enter the 1 th edge (Enter only ending vertex): 0
Enter the 2 th edge (Enter only ending vertex): 1
Enter the 3 th edge (Enter only ending vertex): 2
Enter the number of edges connected to vertex 2 : 4
Enter the 1 th edge (Enter only ending vertex): 0
Enter the 2 th edge (Enter only ending vertex): 1
Enter the 3 th edge (Enter only ending vertex): 3
Enter the 4 th edge (Enter only ending vertex): 4
Enter the number of edges connected to vertex 3 : 2
Enter the 1 th edge (Enter only ending vertex): 2
Enter the 2 th edge (Enter only ending vertex): 4
Enter the number of edges connected to vertex 4 : 3
Enter the 1 th edge (Enter only ending vertex): 1
Enter the 2 th edge (Enter only ending vertex): 2
Enter the 3 th edge (Enter only ending vertex): 3

------------------------------------------------------------------------
            Breadth First Search

        1.Create a Graph
        2.Display the Graph
        3.Breadth First Search
        4.Exit
    Your choise : 3
    BFS is as :     0    1    2    3    4
------------------------------------------------------------------------
            Breadth First Search

        1.Create a Graph
        2.Display the Graph
        3.Breadth First Search
        4.Exit
    Your choise : 2
Edge from vertex 0 to verticex 1
Edge from vertex 0 to verticex 2

Edge from vertex 1 to verticex 0
Edge from vertex 1 to verticex 1
Edge from vertex 1 to verticex 2

Edge from vertex 2 to verticex 0
Edge from vertex 2 to verticex 1
Edge from vertex 2 to verticex 3
Edge from vertex 2 to verticex 4

Edge from vertex 3 to verticex 2
Edge from vertex 3 to verticex 4

Edge from vertex 4 to verticex 1
Edge from vertex 4 to verticex 2
Edge from vertex 4 to verticex 3