Menu Close

BFS | Breadth first search algorithm

In this tutorial, we are going to learn about breadth first search algorithm.

Breadth first search algorithm is a algorithm for traversing or searching in graph data structure. Graph may contain cycle. To avoid cycle, we use visited array as a boolean type. It is opposite to the depth first search algorithm.

Algorithm:

  • Set status 0 for ready state for each node in graph
  • Enqueue the starting node and set status as 1
  • Repeat the step 4 and 5 until queue is empty
  • Dequeue the node and process it
  • Enqueue all the neighbours node of this dequeued node that has state as 0. 
  • After this, Set these nodes status as 1

Example with code:

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int main()
{
    int vertex, edges, src, dst;
    
    cout<<"Enter the number vertex: ";
    cin>>vertex;
    
    int visited[vertex+1];
    
    for (int i = 0; i <= vertex; i++) {
        visited[i] = 0;
    }
    
    cout<<"\nEnter the edges : \n";
    cin>>edges;
    
    
    // Declear vector
    vector<vector<int> > arr(vertex+1);
    
    for (auto index_1 = 0; index_1 < edges ; index_1++) {
        cout<<"\nEnter Src vertex: ";
        cin>>src;
        cout<<"\nEnter dst vertex: ";
        cin>>dst;
        arr[src].push_back(dst);
    }
    
    
    queue<int> q;
    int src_ele;
    cout<<"\nEnter sorce element:";
    cin>>src_ele;
    q.push(src_ele);
    visited[src_ele] = true;
    while(!q.empty()) {
        int ele = q.front();
        q.pop();
        cout<<ele<<" ";
        for (auto i = arr[ele].begin(); i != arr[ele].end(); i++) {
            if (!visited[*i]) {
                q.push(*i);
                visited[*i] = true;
            }
        }
    }
}

Output:


Enter the number vertex: Program ended with exit code: 04


Enter the edges : 
5

Enter Src vertex: 1


Enter dst vertex: 2


Enter Src vertex: 1


Enter dst vertex: 3


Enter Src vertex: 1


Enter dst vertex: 4


Enter Src vertex: 2


Enter dst vertex: 4


Enter Src vertex: 3


Enter dst vertex: 4


Enter sorce element: 1

1 2 3 4 

To learn more about golang, Please refer given below link.

https://www.techieindoor.com/go-lang-tutorial/
https://www.techieindoor.com/go-lang-tutorial/

References:

 https://en.wikipedia.org/wiki/Breadth-first_search
Posted in algorithm, C++