Reverse Breadth First traversal in C#

17
votes

Anyone has a ready implementation of the Reverse Breadth First traversal algorithm in C#?

By Reverse Breadth First traversal , I mean instead of searching a tree starting from a common node, I want to search the tree from the bottom and gradually converged to a common node.

Let's see the below figure, this is the output of a Breadth First traversal : alt text

In my reverse breadth first traversal , 9,10,11 and 12 will be the first few nodes found ( the order of them are not important as they are all first order). 5, 6, 7 and 8 are the second few nodes found, and so on. 1 would be the last node found.

Any ideas or pointers?

Edit: Change "Breadth First Search" to "Breadth First traversal" to clarify the question

2
c#graphgraph-algorithm
How do you find all leaves without traversing the entire tree? - Nifle
Not without knowing more about the problem. It's normally possible to start with one node and fan out, as in breadth-first search, depth-first search, iterative deepening, etc. How are we supposed to know a priori that 9, 10, 11, and 12 are three hops from 1? - David Thornley
Huh, how can the leafs be the only thing you have? A tree is not uniquely determined by the leafs, so you MUST also be given a tree, otherwise the problem makes no sense. - IVlad
If this isn't a homework question why have you decided specifically on needing the use of reverse breadth first as your solution as opposed to stating the whole problem? Not that R-BFS isn't the correct solution but on SO it's hard to answer question like theses without knowing the actual context of the problem. When all you have is a hammer everything looks like a nail. - Chris Marisic
@IVlad: If every node has a pointer to its parent and you have the leaves, then you know the entire tree. - 3dGrabber

2 Answers

19
votes

Use a combination of a stack and queue.

Do the 'normal' BFS using the queue (which I presume you know to do already), and keep pushing nodes on the stack as you encounter them.

Once done with the BFS, the stack will contain the reverse BFS order.

7
votes

Run a normal BFS from rootNode and let depth[i] = linked list of nodes with depth i. So for your example you'll have:

depth[1] = {1}, depth[2] = {2, 3, 4} etc.. You can build this with a simple BFS search. Then print all the nodes in depth[maxDepth], then those in depth[maxDepth - 1] etc.

The depth of a node i is equal to the depth of its father node + 1. The depth of the root node can be considered 1 or 0.