如何跟踪的深度在这个对象图的深度优先搜索算法？ [英] How to track the depth in this object graph depth-first search algorithm?

问题描述

我有这个code的遍历一棵树，做了深度优先搜索。每一个元素都被解决一次。好极了。

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:

一个有孩子的B，J。 B有孩子C. C有孩子D. D有孩子的E，F，I。

A has childs B, J. B has child C. C has child D. D has childs E, F, I.

当A是深度级别1，那么B 2，C为3。

When A is at depth level 1, then B is 2 and C is 3.

使用递归这是非常容易跟踪当前深度级别的。自称以前只是inrement一个变量，并自称为后递减的。

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?

推荐答案

我想你需要堆深处为好。这就是你实际上已经做无论如何，如果你有一个递归版本。这只是存储将是看不见的，因为你会使用一个明确的堆栈像你现在正在做的调用堆栈来代替。

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.

如果它可以帮助你，你可以很容易地转换深度优先搜索广度优先搜索，利用阵列作为一个队列，而不是一个堆栈。 （只要做，而不是removeLastObject removeFirstObject）。然后，你会知道，你总是看节点，以非递减的深度。但是，如果您需要确切的深处，我觉得你还是需要添加一些存储跟踪时，你必须增加当前的深度。

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.

更新：

您应该能够做一个DFS没有栈完全，相反，如果你按照节点备份树的父指针。这将使保持深度简单。但你必须要小心，不要被孩子们重新扫描，找出你打破线性时间的最坏情况下的复杂性。

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:

push root
while stack not empty:
   current = pop
   push all children of current

这篇关于如何跟踪的深度在这个对象图的深度优先搜索算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！