扭转C＃广度优先遍历 [英] Reverse Breadth First traversal in C#

问题描述

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

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 :

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

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.

任何意见或指针？

编辑：改变广度优先搜索，以广度优先遍历，以澄清问题

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

推荐答案

运行从 rootNode中正常BFS让深度由[i] =链接深度I 节点列表。因此，对于你的例子，你将有：

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

深度[1] = {1}，深度[2] = {2，3，4 }等。。你可以用一个简单的搜索BFS建立这个。然后打印在深度[MAXDEPTH] ，那么那些在深度[MAXDEPTH - 1]的所有节点。等

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.

节点 I 的深度等于其父亲节点+ 1。根节点的深度的深度可以考虑1或0。

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.

这篇关于扭转C＃广度优先遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！