Reverse Breadth First traversal in C#
-
24-09-2019 - |
Question
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 :
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
Solution
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.
OTHER TIPS
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.