Can someone explain Breadth-first search?

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

You test each node connected to the root node. Then you test each node connected to the previous nodes. So on, until you find your answer.

Basically, each iteration tests nodes that are the same distance away from the root node.

Answer 3

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.

Answer 4

BEGIN

4;

4,2;

4,2,1; 4,2,3; 4,2,5;

4,2,1;(fail) 4,2,3,6; 4,2,5,6; 4,2,5,11;

4,2,3,6,7;(pass) 4,2,3,6,8; 4,2,5,6,7;(pass) 4,2,5,6,8; 4,2,5,11,12;

4,2,3,6,8,9; 4,2,3,6,8,10; 4,2,5,6,8,9; 4,2,5,6,8,10; 4,2,5,11,12;(fail)

4,2,3,6,8,9;(fail) 4,2,3,6,8,10;(fail) 4,2,5,6,8,9;(fail) 4,2,5,6,8,10;(fail)

END

Answer 5

Think of it as websites with links to other sites on them. Let A be our root node or our starting website.

A is the starting page    (Layer 1)
A links to AA, AB, AC     (Layer 2)
AA links to AAA, AAB, AAC (Layer 3)
AB links to ABA, ABB, ABC (Layer 3)
AC links to ACA, ACB, ACC (Layer 3)

This is only three layers deep. You search one layer at a time. So in this case you would start at layer A. If that does not match you go to the next layer, AA, AB and AC. If none of those websites is the one you are searching for then you follow the links and go to the next layer. In other words, you look at one layer at a time.

A depth first search (its complement) you would go from A to AA to AAA. In other words you would go DEEP before going WIDE.