Can someone explain Breadth-first search?

Question

Can someone explain Breadth-first search to solve the below kind of problems

I need to find all the paths between 4 and 7

Answer 1

You look at all the nodes adjacent to your start node. Then you look at all the nodes adjacent to those (not returning to nodes you've already looked at). Repeat until satisfying node found or no more nodes.

For the kind of problem you indicate, you use the process described above to build a set of paths, terminating any that arrive at the desired destination node, and when your graph is exhausted, the set of paths that so terminated is your solution set.

Answer 2

Breadth first search (BFS) means that you process all of your starting nodes' direct children, before going to deeper levels. BFS is implemented with a queue which stores a list of nodes that need to be processed.

You start the algorithm by adding your start node to the queue. Then you continue to run your algorithm until you have nothing left to process in the queue.

When you dequeue an element from the queue, it becomes your active node. When you are processing your active node, you add all of its children to the back of the queue. You terminate the algorithm when you have an empty queue.

Since you are dealing with a graph instead of a tree, you need to store a list of your processed nodes so you don't enter into a loop.

Once you reach node 7 you have a matching path and you can stop doing the BFS for that recursive path. Meaning that you simply don't add its children to the queue. To avoid loops and to know the exact path you've visited, as you do your recursive BFS calls, pass up the already visited nodes.