This Tutorial Covers Breadth First Search in C++ in Which The Graph or Tree is Traversed Breadthwise. You will Also Learn BFS Algorithm & Implementation:
This explicit C++ tutorial will give you a detailed explanation of traversal techniques that can be performed on a tree or graph.
Traversal is the technique using which we visit each and every node of the graph or a tree. There are two standard methods of traversals.
- Breadth-first search(BFS)
- Depth-first search(DFS)
=> See Here To Explore The Full C++ Tutorials list.
Table of Contents:
Breadth First Search (BFS) Technique In C++
In this tutorial, we will discuss in detail the breadth-first search technique.
In the breadth-first traversal technique, the graph or tree is traversed breadth-wise. This technique uses the queue data structure to store the vertices or nodes and also to determine which vertex/node should be taken up next.
Breadth-first algorithm starts with the root node and then traverses all the adjacent nodes. Then, it selects the nearest node and explores all the other unvisited nodes. This process is repeated until all the nodes in the graph are explored.
Breadth-First Search Algorithm
Given below is the algorithm for BFS technique.
Consider G as a graph which we are going to traverse using the BFS algorithm.
Let S be the root/starting node of the graph.
- Step 1: Start with node S and enqueue it to the queue.
- Step 2: Repeat the following steps for all the nodes in the graph.
- Step 3: Dequeue S and process it.
- Step 4: Enqueue all the adjacent nodes of S and process them.
- [END OF LOOP]
- Step 6: EXIT
Pseudocode
The pseudo-code for the BFS technique is given below.
Procedure BFS (G, s)
G is the graph and s is the source node
begin
let q be queue to store nodes
q.enqueue(s) //insert source node in the queue
mark s as visited.
while (q is not empty)
//remove the element from the queue whose adjacent nodes are to be processed
n = q.dequeue( )
//processing all the adjacent nodes of n
for all neighbors m of n in Graph G if w is not visited
q.enqueue (m) //Stores m in Q to in turn visit its adjacent nodes
mark m as visited.
end
Traversals With Illustrations
Let 0 be the starting node or source node. First, we enqueue it in the visited queue and all its adjacent nodes in the queue.
Next, we take one of the adjacent nodes to process i.e. 1. We mark it as visited by removing it from the queue and put its adjacent nodes in the queue (2 and 3 already in queue). As 0 is already visited, we ignore it.
Next, we dequeue node 2 and mark it as visited. Then, its adjacent node 4 is added to the queue.
Next, we dequeue 3 from the queue and mark it as visited. Node 3 has only one adjacent node i.e. 0 which is already visited. Hence, we ignore it.
At this stage, only node 4 is present in the queue. Its adjacent node 2 is already visited, hence we ignore it. Now we mark 4 as visited.
Next, the sequence present in the visited list is the breadth-first traversal of the given graph.
If we observe the given graph and the traversal sequence, we can notice that for the BFS algorithm, we indeed traverse the graph breadth-wise and then go to the next level.
BFS Implementation
#include<iostream>
#include <list>
using namespace std;
// a directed graph class
class DiGraph
{
int V; // No. of vertices
// Pointer to an array containing adjacency lists
list<int> *adjList;
public:
DiGraph(int V); // Constructor
// add an edge from vertex v to w
void addEdge(int v, int w);
// BFS traversal sequence starting with s ->starting node
void BFS(int s);
};
DiGraph::DiGraph(int V)
{
this->V = V;
adjList = new list<int>[V];
}
void DiGraph::addEdge(int v, int w)
{
adjList[v].push_back(w); // Add w to v’s list.
}
void DiGraph::BFS(int s)
{
// initially none of the vertices is visited
bool *visited = new bool[V];
for(int i = 0; i < V; i++)
visited[i] = false;
// queue to hold BFS traversal sequence
list<int> queue;
// Mark the current node as visited and enqueue it
visited[s] = true;
queue.push_back(s);
// iterator 'i' to get all adjacent vertices
list<int>::iterator i;
while(!queue.empty())
{
// dequeue the vertex
s = queue.front();
cout << s << " ";
queue.pop_front();
// get all adjacent vertices of popped vertex and process each if not already visited
for (i = adjList[s].begin(); i != adjList[s].end(); ++i)
{
if (!visited[*i])
{
visited[*i] = true;
queue.push_back(*i);
}
}
}
}
// main program
int main()
{
// create a graph
DiGraph dg(5);
dg.addEdge(0, 1);
dg.addEdge(0, 2);
dg.addEdge(0, 3);
dg.addEdge(1, 2);
dg.addEdge(2, 4);
dg.addEdge(3, 3);
dg.addEdge(4, 4);
cout << "Breadth First Traversal for given graph (with 0 as starting node): "<<endl;
dg.BFS(0);
return 0;
}
Output:
Breadth-First Traversal for the given graph (with 0 as starting node):
0 1 2 3 4
We have implemented the BFS in the above program. Note that the graph is in the form of an adjacency list and then we use an iterator to iterate through the list and perform BFS.
We have used the same graph that we used for illustration purposes as an input to the program to compare the traversal sequence.
Runtime Analysis
If V is the number of vertices and E is the number of edges of a graph, then the time complexity for BFS can be expressed as O (|V|+|E|). Having said this, it also depends on the data structure that we use to represent the graph.
If we use the adjacency list (like in our implementation), then the time complexity is O (|V|+|E|).
If we use the adjacency matrix, then the time complexity is O (V^2).
Apart from the data structures used, there is also a factor of whether the graph is densely populated or sparsely populated.
When the number of vertices exceeds the number of edges, then the graph is said to be sparsely connected as there will be many disconnected vertices. In this case, the time complexity of the graph will be O (V).
On the other hand, sometimes the graph may have a higher number of edges than the number of vertices. In such a case, the graph is said to be densely populated. The time complexity of such a graph is O (E).
To conclude, what the expression O (|V|+|E|) means is depending on whether the graph is densely or sparsely populated, the dominating factor i.e. edges or vertices will determine the time complexity of the graph accordingly.
Applications Of BFS Traversal
- Garbage Collection: The garbage collection technique, “Cheney’s algorithm” uses breadth-first traversal for copying garbage collection.
- Broadcasting In Networks: A packet travels from one node to another using the BFS technique in the broadcasting network to reach all nodes.
- GPS Navigation: We can use BFS in GPS navigation to find all the adjacent or neighboring location nodes.
- Social Networking Websites: Given a person ‘P’, we can find all the people within a distance, ‘d’ from p using BFS till the d levels.
- Peer To Peer Networks: Again BFS can be used in peer to peer networks to find all the adjacent nodes.
- Shortest Path And Minimum Spanning Tree In The Un-weighted Graph: BFS technique is used to find the shortest path i.e. the path with the least number of edges in the un-weighted graph. Similarly, we can also find a minimum spanning tree using BFS in the un-weighted graph.
Conclusion
The breadth-first search technique is a method that is used to traverse all the nodes of a graph or a tree in a breadth-wise manner.
This technique is mostly used to find the shortest path between the nodes of a graph or in applications that require us to visit every adjacent node like in networks.
=> Click Here For The Free C++ Course.