C#中的反向宽度第一次遍历

Question

任何人都可以在C#中实现Reverse Breadth First遍历算法？

通过反向宽度第一次遍历,我的意思是不是从公共节点开始搜索树,而是想从底部搜索树并逐渐收敛到公共节点.

让我们看下图,这是广度优先遍历的输出:

在我逆向广度优先遍历9,10,11和12将是第一个找到的几个节点(它们的顺序并不重要,因为他们都是第一顺序).5,6,7和8是发现第二几个节点,依此类推.1将是找到的最后一个节点.

任何想法或指针？

编辑:将"广度优先搜索"更改为"广度优先遍历"以澄清问题

Answer 1

使用堆栈和队列的组合.

使用队列(我假设您已经知道)执行"正常"BFS,并在遇到它们时继续推送堆栈上的节点.

一旦完成BFS,堆栈将包含反向BFS订单.

Answer 2

从中运行正常的BFS rootNode并让它depth[i] = linked list of nodes with depth i.因此,对于您的示例,您将拥有:

depth[1] = {1}, depth[2] = {2, 3, 4} etc..您可以使用简单的BFS搜索来构建它.然后打印出所有节点depth[maxDepth],那么那些depth[maxDepth - 1]等.

节点i的深度等于其父节点的深度+ 1.根节点的深度可以被认为是1或0.