In this article, we will discuss the breadth-first search or bfs algorithm. The breadth-first search algorithm for graphs is similar to the breadth-first search algorithm for trees. The only difference is, since a graph may contain a cycle so we may encounter the same node again and again. To avoid dealing with the same node again, we can divide the set of vertices into two categories:
1. Visited
2. Not visited
For this purpose, a boolean array is maintained to mark the nodes that we have encountered yet. In breadth first search algorithm, the queue is used for the traversal.
Implementation of Breadth first search algorithm
1. The very first step is to declare a queue and push the starting vertex or root.
2. Then, we need to initialize a visited array and mark it as visited.
3. We need to keep doing the following processes until our queue gets empty:
Get the vertex stored at the front of the queue and mark it as visited.
Remove this vertex from the queue.
Explore all the direct neighbours of this vertex and insert them in the queue.
The following is the implementation code of breadth first search algorithm:
Source Code
#include <bits/stdc++.h> usingnamespacestd; // template to work for // node of any type template<typename T> // Create a class classGraph { // To maintain edges unordered_map<T , list<T>> edges; public: // add edge voidadd_edge(T x , T y) { edges[x].push_back(y); edges[y].push_back(x); } // bfs () function // for breadth first search traversal voidbfs(T src) { // Create a visited array of boolean type unordered_map<T , bool> visited; // Create a queue queue<T> que; // Insert the node in queue que.push(src); // Mark source vertex as visited visited[src] = true; // Iterate till queue gets empty while(!que.empty()) { T node = que.front(); cout << node << ' '; que.pop(); for(T nbr : edges[node]) { if(!visited[nbr]) { que.push(nbr); visited[nbr] = true; } } } } }; intmain() { // Create an object Graph<int> graph; // Add edges graph.add_edge(1, 2); graph.add_edge(1, 3); graph.add_edge(2, 3); graph.add_edge(3, 4); cout << "The Breadth First Traversal starting from the vertex 1:" << " \n"; // Call bfs() method graph.bfs(1); return0; }
Time complexity: O(V + E) where V signifies the number of vertices and E signifies the number of edges
Space complexity: O(V) where V signifies the number of vertices
Breadth-first search for disconnected graph
A graph unlike a tree may be disconnected. In that case, we need to tweak our code a little bit. Consider the following program in which we loop over all vertices so that we don’t miss out any component:
Source Code
#include <bits/stdc++.h> usingnamespacestd; // template to work for // node of any type template<typename T> // Create a class classGraph { // To maintain edges unordered_map<T , list<T>> edges; public: // add edge voidadd_edge(T x , T y) { edges[x].push_back(y); edges[y].push_back(x); } // bfs () function // for breadth first search traversal voidbfs(T V) { // Create a visited array of boolean type unordered_map<T , bool> visited; for(int currentNode = 1 ; currentNode <= V ; currentNode++) { // If already visited then skip // the following steps if(visited[currentNode]) continue; T src = currentNode; // Create a queue queue<T> que; // Insert the node in queue que.push(currentNode); // Mark source vertex as visited visited[currentNode] = true; // Iterate till queue gets empty while(!que.empty()) { T node = que.front(); cout << node << ' '; que.pop(); for(T nbr : edges[node]) { if(!visited[nbr]) { que.push(nbr); visited[nbr] = true; } } } } } }; intmain() { // Create an object Graph<int> graph; // Add edges // Note that the graph is // disconnected graph.add_edge(1, 2); graph.add_edge(2, 3); graph.add_edge(4, 5); graph.add_edge(4, 6); graph.add_edge(5, 6); cout << "The Breadth First Traversal of the graph:" << " \n"; // Call bfs() method graph.bfs(6); return0; }
As you can see, all the nodes have been traversed.
Conclusion
In this article, we discussed the breadth first search algorithm in graph. We also learned about how we can traverse a disconnected graph. We believe that you must have learned something new through this article.
