# 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

`https://www.techieindoor.com/go-lang-tutorial/`
` https://en.wikipedia.org/wiki/Breadth-first_search`