2. BFS #

Created Tuesday 31 March 2020

This is also a traversal/search technique.

In constrast with DFS, here we first print all the neighbours of the current node. Then we explore each one of them. We need a queue here.

1. We’ll use a queue for this. We’ll put the neighbours inside. When done, we’ll pop the current node.
2. But when we see all neigbours after coming from the predeccessor, we can again put(erraneously) it in the queue. To avoid this, we use a visited array.
3. We go through all vertices, calling BFS from it if they are absent from visited, at the same time checking if visited.size()<V. This ensures that disconnected components are also taken into account.

• Note that if we don’t pop the queue but traverse it like an array. We don’t require a visited array. We can scan the whole queue-array if we the node has already been visited. **The queue is our **to-be explored list. Time and space complexity is the same as storing a visited array, it’s actually better to use a visited array/map , reallocs are lesser.
• Note that a node may be on the right side but still be a neighbour of the current node. Repeat 1.
• Also we cannot neglect the left side because it contains the predecessors. So **the whole queue-array is important and needs to be scanned. **Here space requirement is O(V). and Time requirement is O(V^2^). Repeat 2.
• In a nutshell, using an queue-array or a seperated visited are equivalent. We use a hashmap for added performance and easier code. Repeat 3.
• If we use a hashmap for visited, our time complexity will be O(V+E).

Implementation tip In loops check if visited.size()==V, stop if it is.

• Use dynamic DSs.
• TC: O(V+E) - we visit the neighbours of all vertices.
• SC: O(V) - We store vertices, |V|-1 for the worst case scenario.

BFS.cpp

Applications

• Most problems are just variations of DFS and BFS. These are the first principles for Graphs.