Jul 6, 2019
BFS Implementation in C++
What is Breadth First Search(BFS)?
BFS is a graph traversal method that traverses the graph iterative way level by level. That means it traverses the graph “breadth first”, starting from the source then the neighbor of the source then the next level and so on.
For example:
If we traverse the given graph above, the output will be: ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘K’, ‘I’, ‘J’
‘A’ will be visited first as it is the source node. Then ‘B’, ‘C’, and ‘D’ is in the next level, so they will be visited. And it is the same way the rest of the nodes will be visited.
Implementation of BFS
We will make a class called graph and take a map that has char type as key and vector of char as value. Usually, we take a vector of vector to store values of the nodes but in this graph, as we are storing char values, the index will be char type that is why we have to take map or unordered_map. And we will declare a method to add the edges and a method to do breadth-first search.
Add Edge to the Graph
To add edges we have already declared a method. Now, let's implement the method.
The first two parameters of the method are the two nodes between which we want to add an edge and the third parameter is a boolean to know if the edge is bidirectional or not. The example graph we are implementing which is given above is undirected graph that means it is bidirectional, so I have given the default value as true. Then we are adding node2 to index of node1 and as our graph is bidirectional. Given below is the representation of how the edges are stored in the adjList.
Breadth First Search
Now let’s implement BFS to traverse each node of the graph and print them.
The method has one parameter which is the source node. We are maintaining a queue of character and we also have a map called visited which has char as key and bool as value. We take the visited map to keep track of the visited node so that one node is visited only once.
Initially, we take the source node visit it and put it in the queue.
Then as long as the queue is not empty remove a node from the queue and go the neighbors of that node and any of the neighbors is not visited then we will mark it as visited and push it into the queue.
In our example graph, the source node is ‘A’. So, the first element that will be put into the queue is ‘A’ and then we will remove ‘A’ from the queue and print it. Then, we will put the neighboring nodes of ‘A’ in the queue, i.e. ‘B’, ‘C’ and ‘D’ and after that we will pop ‘B’ from the queue and visit neighboring nodes of ‘B’, i.e. ‘E’ and ‘F’ and put them in the queue. And this process will go on until we have removed all the nodes from the queue. And the output will be:
A, B, C, D, E, F, K, I, J
Time Complexity of BFS
Time Complexity: O(V + E)
Here, V is the number of vertices and E is the number of edges. The time complexity is O(V + E) because we are traversing every node of the graph which takes O(V) time and for every node, we add its children node, so how many children nodes does a node have? it has as many children nodes as it has edges coming out of it. For instance, ‘A’ has 3 children nodes because there are 3 edges coming out of it and ‘B’ has 2 children node because there are 2edges coming out it and so on. So, this takes O(E) time. That makes the time complexity O(V) + O(E) -> O(V + E)
Space Complexity of BFS
Space complexity: O(V)
Here V is the number of vertices. The space complexity is O(V) because we are taking a queue that can have all the vertices in the worst case, so it takes O(V) space. And we are also taking a map to keep track of the visited node, the length of which will be equal to the number of vertices, so O(V). That makes the space complexity O(V) + O(V)-> O(V)
