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/
References:
https://en.wikipedia.org/wiki/Breadth-first_search