Suppose the graph (figure 1(a)) is drawn showing interconnected cities. It is a two way graph. A person can move in any direction like from node 2 to node 4 or from node 4 to node 2. An edge represents the distance between two connected cities. Different search algorithms use different strategies to find path from source node to destination node.
Figure 2(a)
Beadth First Search (BFS)
BFS works level by level. In Breadth First Algorithm contrast to Depth first Search, all the child nodes of a parent node are explored before moving to next level and then further child nodes of these explored nodes until a goal node is found.
Suppose for above drawn graph (figure 2(a)) showing connected cities
Source node is 1
Destination node is 5
1) Source node is Node 1. On pressing any key, it shows Node 1 with highlighting colour another round as shown in figure 2(b)
Destination node is 5
1) Source node is Node 1. On pressing any key, it shows Node 1 with highlighting colour another round as shown in figure 2(b)
Figure 2(b)
2. Looks for child nodes of Parent Node 1. Node 4 and Node 5 are child nodes. It works in increasing order like Node 1 then Node 2 then Node 3, if Node 1, Node 2 and Node 3 are children node of any Parent node. So here Node 4 is explored first as shown in figure 2(c).
Figure 2(c)
3. In breadth First Search, all the child nodes of a node are explored at a level. So another child Node of Node 1 is Node 5. Hence Node 5 is explored after Node 4 as shown in figure 2(d).
Figure 2(d)
Hence Node 5 is destination node. So Breadth First Search is complete.
Here you can see that Breadth First Search takes lesser time than Depth First Search. Breadth First Search is very useful if destination node lies at upper levels as there is no need to go till very deep level. It saves time and storage requirement both.
