如何跟踪此对象图深度优先搜索算法中的深度？
我有这段代码，它迭代一棵树，进行深度优先搜索。每个元素都只处理一次。非常好。
-(void)iterateOverTree:(TreeNode *)node
{
NSMutableArray * elements = [NSMutableArray array];
[elements addObject:node];
while([elements count])
{
TreeNode * current = [elements objectAtIndex:0];
[self doStuffWithNode:current];
for(TreeNode * child in current.children)
{
[elements addObject:child];
}
[elements removeLastObject];
}
}
但是：如何跟踪图表中的当前深度？我需要知道深度。例如，我有这些节点：
A 有子节点 B、J。 B有孩子C。 C有孩子D。 D 具有子级 E、F、I。
当 A 处于深度级别 1 时，B 为 2，C 为 3。
通过递归，可以非常轻松地跟踪当前深度级别。只需在调用自身之前增加变量并在调用自身之后减少变量即可。
但这里用这个奇特的 while 循环是不可能的。没有像递归那样发生盒中盒中的盒。
我真的不想向 TreeNode 对象添加属性（或实例变量），因为这应该可以以通用方式重用于任何类型的对象图。
有谁知道如何做到这一点？我必须引入另一个数组来跟踪访问过的节点吗？
I have this code which iterates over a tree, doing a depth-first search. Every element is tackled exactly once. Very good.
-(void)iterateOverTree:(TreeNode *)node
{
NSMutableArray * elements = [NSMutableArray array];
[elements addObject:node];
while([elements count])
{
TreeNode * current = [elements objectAtIndex:0];
[self doStuffWithNode:current];
for(TreeNode * child in current.children)
{
[elements addObject:child];
}
[elements removeLastObject];
}
}
BUT: How can I keep track of the current depth in the graph? I need to know the level of depth. So for example I have these nodes:
A has childs B, J.
B has child C.
C has child D.
D has childs E, F, I.
When A is at depth level 1, then B is 2 and C is 3.
With recursion it was very easy to keep track of the current depth level. Just inrement a variable before calling itself and decrement it after calling itself.
But here with this fancy while loop that is not possible. There is no box in the box in the box happening like with recursion.
I don't really want to have to add properties (or instance variables) to the TreeNode object as this should be re-usable in a generic way for any kind of object graph.
Does anyone have an idea how to do this? Must I introduce another array to keep track of visited nodes?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我认为你也确实需要堆叠深度。如果你有一个递归版本，这就是你实际上会做的事情。只是存储将是“不可见的”，因为您将使用调用堆栈而不是像现在一样使用显式堆栈。
如果它对您有帮助，您可以通过使用数组作为队列而不是堆栈，轻松地将深度优先搜索转换为广度优先搜索。 （只需执行removeFirstObject而不是removeLastObject。）然后您就会知道您始终按照非递减深度的顺序查看节点。但是，如果您需要精确的深度，我认为您仍然需要添加一些存储来跟踪何时必须增加当前深度。
更新：
如果您按照节点的父指针来备份树，那么您应该能够在完全没有堆栈的情况下执行 DFS。这将使保持深度变得简单。但您必须小心，不要通过重新扫描子项来找出您所在的位置，从而破坏线性时间最坏情况的复杂性。
如果您没有父指针，则应该可以堆叠足够的信息来跟踪父指针。但这意味着您在堆栈上放置的信息比当前所做的更多，因此与直接堆栈深度相比并没有太大的改进。
顺便说一句，仔细看看你的算法，当你得到下一个当前节点时，你不是在看数组的错误一侧吗？它应该像这样工作：
I think you do need to stack the depths as well. This is what you would actually have done anyway, if you had a recursive version. It's just that the storage would be “invisible”, since you would have used the call stack instead of an explicit stack like you are doing now.
If it helps you, you could easily convert the depth-first search to a breadth-first search, by using the array as a queue instead of a stack. (Just do removeFirstObject instead of removeLastObject.) Then you would know that you always look at the nodes in order of non-decreasing depth. However, if you need exact depths, I think you still need to add some storage for keeping track of when you have to increment the current depth.
Update:
You should be able to do a DFS without the stack altogether, if instead you follow parent pointers of the node to back up the tree. That would make maintaining the depth simple. But you would have to be careful not to break linear-time worst-case complexity by rescanning children to find out where you were.
If you don't have parent pointers, it should be possible to stack just enough information to keep track of the parents. But this would mean that you put some more information on the stack than you are currently doing, so it would not be much of an improvement over stacking the depths directly.
By the way, looking carefully on your algorithm, aren't you looking at the wrong side of the array when you get the next current node? It should work like this:
我不理解你的符号，但如果我读得正确，你会处理一个节点并将所有子节点添加到你要做的工作列表中。
如果您可以将该部分更改为使用递归，则可以跟踪树深度，因为它将是递归深度。
因此，不要添加子节点，而是对每个子节点进行递归。
马里奥
Im not understanding your notation, but if I read correctly you process a node and add all children to your list of work to do.
If you could change that part to using a recursion, you could track the tree-depth since it would be the recursion depth.
So instead of adding the child node, recurse for each child node.
hth
Mario
我相信你所做的实际上是 BFS。您正在使用列表。为了进行DFS，你应该使用堆栈；
这可能对深度追踪很有用，你可以看看向量 p （父母的）
I believe what you are doing actually is BFS. You are working with lists. For doing DFS, you should use a stack;
This might be useful for the depth track, you might look into the vector p (of parents)
假设您正在执行 BFS，最简单的方法是引入另一个镜像节点队列的深度队列。将深度初始化为零。每次推入节点队列时，将当前深度+1推入深度队列。
Supposing you are doing BFS, the easiest thing to do is to introduce another queue for depth that mirrors your nodes queue. Initialize the depth to zero. Each time you push to the node queue, push the current depth + 1 to the depth queue.