反向广度优先遍历C＃

Question

任何人有在C＃准备执行反向广度优先遍历算法的？

通过反向广度优先遍历，我的意思是不是在搜索公共节点开始的树形结构，我想从底部查找树逐步收敛到一个公共节点。

让我们看看下面的图中，这是一个广度优先遍历的输出：

在我的反向广度优先遍历，9，10，11和12将是第几个节点实测值（它们的顺序并不重要，因为他们都是一阶）。 5，6，7和8是第二几个节点发现，依此类推。 1将是最后一个节点发现。

任何想法或指针？

编辑：改变“广度优先搜索”到“广度优先遍历”澄清的问题

Answer 1

运行从rootNode正常BFS和让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。

Answer 2

使用一个堆栈和队列的一个组合。

执行使用队列（我想你知道已经这样做），并保持在堆栈上推的节点，你遇到他们的“正常” BFS。

一旦与BFS完成，堆栈将包含反向BFS顺序。