c# - C#中的反向广度优先遍历

Question

任何人都有 C# 中反向广度优先遍历算法的现成实现？

通过反向广度优先遍历，我的意思不是从公共节点开始搜索树，而是从底部搜索树并逐渐收敛到公共节点。

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

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

任何想法或指示？

编辑：将“广度优先搜索”更改为“广度优先遍历”以澄清问题

Answer 1

使用堆栈和队列的组合。

使用队列执行“正常”BFS（我假设您已经知道这样做了），并在遇到节点时继续将节点推送到堆栈上。

完成 BFS 后，堆栈将包含反向 BFS 顺序。

Answer 2

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