Breadth-first search

Hi all


I have this paragraph, I think it can be summarised as a Breadth-first search description.

Quote:

---

Starting at the root node 0, your branch-and-bound algorithm explores paths to every reachable node in the graph while keeping in mind the cost of the partially explored path. As such, the algorithm keeps track of the cost of reaching every node in the tree from the root. It will also prune paths below a particular node in the tree if the cost of the node exceeds the cost of an already completed tour.

---

Am I right?

Thanks.

Quote:

---

Originally Posted by jordanguyoflove

I have this paragraph, I think it can be summarised as a Breadth-first search description.

---

There are subtle differences between the algorithm described above and BFS. First, BFS doesn't keep in mind the cost of partially explored paths, as BFS doesn't know anything about costs or paths. Another obvious one is that a BFS may start at any node, but w.l.o.g. you may call this one the root node. Also, BFS doesn't prune subtrees. Furthermore, your text states that branch-and-bound visits every reachable node but also prunes certain paths, which seems strange: why visit a node if it's pruned?. Anyway, if b-n-b doesn't visit nodes in pruned subtrees, there's another difference: a full BFS always diverges in trees that contain nodes with infinitely many outgoing edges, while a pruning b-n-b must not necessarily do so.

Your text describes an algorithm that uses some sort of a search algorithm (that is required to visit every node) and adds cost and pruning. It would make sense to use BFS here, but the text describes what the algorithm does, not how; it could be DFS as well.

Greets,
Philip

That paragraph isn't requiring a breadth-first traversal. In fact I would do it by a depth-first traversal, passing the height into each recursive call. I'd then return true if the depth of that node was too deep, and the previous call would respond to a true return value by deleting that part of the tree and NULLing the appropriate child pointer.
To use a BFS would require you to keep track of all nodes above a certain node, rather than only those that lead down to that node. This suggests using a deque, which would have higher memory requirements.

Quote:

---

Originally Posted by iMalc

To use a BFS would require you to keep track of all nodes above a certain node, rather than only those that lead down to that node.

---

No, BFS doesn't need to keep track of the visited nodes in acyclic graphs, such as trees. It's easy to teach BFS to keep track of its current depth.

Greets,
Philip

Thanks.
I am going to write my own function.

Quote:

---

Originally Posted by Snafuist

No, BFS doesn't need to keep track of the visited nodes in acyclic graphs, such as trees. It's easy to teach BFS to keep track of its current depth.

Greets,
Philip

---

Oh certainly it can be done without remembering all nodes from at least the previous depth, however the only way to accomplish that is to go down the entire tree to the new depth each time, meaning that you visit many of the nodes much more than one time. I think on average it's about twice as many times you visit each node (considering that the bottommost level doesn't get visited twice).
I would never consider implementing such an ineficient solution. So I shall reprhase: "To do a BFS efficiently, would require you to keep track of all nodes from the previous level".
Still, certainly no reason to prefer BFS over a depth-first solution here.

Using an ADT as a queue instead of using a stack as with a BFS is analogus to a search party looking for a lost skier in the mountains. Where as a DFS is refering to one person digging at every point in the snow feeling for the body.

Quote:

---

Originally Posted by iMalc

Quote:

---

Originally Posted by Snafuist

No, BFS doesn't need to keep track of the visited nodes in acyclic graphs, such as trees. It's easy to teach BFS to keep track of its current depth.

---

Oh certainly it can be done without remembering all nodes from at least the previous depth, however the only way to accomplish that is to go down the entire tree to the new depth each time, meaning that you visit many of the nodes much more than one time.

---

No, you only need to visit every node exactly once. Consider how BFS works:

1. Enqueue the root node.
2. Dequeue a node.
3. Enqueue any of its successors.
4. If the queue is empty, every node on the graph has been visited -- quit
5. Repeat from Step 2.

(add the search part as appropriate)

In order to keep track of the current depth, you do the following: mark the root node as being white. In step 3, mark the children of white nodes as being black, the children of black nodes as being white. In step 2, if you pop a node with a different color than the previous one, you increase the depth by 1. The marking is done in constant time and every node is visited exactly once. Regarding the runtime, there's no difference to the original BFS, except that you now know the current depth.

Greets,
Philip

Quote:

---

Originally Posted by Snafuist

No, you only need to visit every node exactly once. Consider how BFS works:

1. Enqueue the root node.
2. Dequeue a node.
3. Enqueue any of its successors.
4. If the queue is empty, every node on the graph has been visited -- quit
5. Repeat from Step 2.

(add the search part as appropriate)

In order to keep track of the current depth, you do the following: mark the root node as being white. In step 3, mark the children of white nodes as being black, the children of black nodes as being white. In step 2, if you pop a node with a different color than the previous one, you increase the depth by 1. The marking is done in constant time and every node is visited exactly once. Regarding the runtime, there's no difference to the original BFS, except that you now know the current depth.

Greets,
Philip

---

Congratulations, you just described "remembering all nodes from at least the previous depth" that I mentioned earlier. Rather than 'colouring' nodes, the way I would do that would be by simply using a single sentinel node to mark the point between levels.
Yes in my first post I casually said "all nodes above a certain node", when I meant "all nodes directly above a certain node", i.e. on the previous level. We're on the same page!

Do you understand that a DFS only have to keep track of log(n) nodes at any time during the search (assuming a perfectly balanced tree for the moment)? Whereas a BFS search using a deque (as we're both describing) requires storing many more nodes at any given time? E.g. a tree of 127 nodes requires storing a maximum of 7 nodes on the stack during a DFS, whereas a BFS going from the second-to-last level to the last level requires holding between 32 and 64 nodes in the queue. Do I need to draw a diagram?


slingerland3g, you don't need to provide an anology for my bennefit. I fully understand and have implemented all sorts of tree visiting routines many times. There isn't anything new to me being discussed here.
However, can you explain why your analogy implies that a good BFS would be faster than a good DFS, when both examine every node exactly once? And to top it off, a BFS has to remember more nodes during the search, as I've just reminded us all above. If you still don't follow then I invite you to implement the two and learn where you're going wrong with your analysis.

iMalc, sorry for your confusion but I was addressing the OP. Besides I am just a student of all this myself. So a good discussion nevertheless. I have been working out of the Algorithms in C, 3rd Ed, which goes into some pretty good details of all of this. Would be a good read if you are interested. Also it is not that one particular method is better than the other, but your approach and how you need to use stack space or set up ADT queues and what ordering your are needing to traverse the graph(level ordering?). Going into graph traversal implementations sparks many heated debates.