如何跟踪此对象图深度优先搜索算法的深度？

我有这个代码遍历树，进行深度优先搜索。每个元素都只处理一次。很好。如何跟踪此对象图深度优先搜索算法的深度？

-(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对象添加属性（或实例变量），因为它应该以任何种类的对象图的通用方式重新使用。

有没有人有一个想法如何做到这一点？我必须引入另一个数组来跟踪访问节点吗？

来源

2011-04-26 Proud Member

我想你需要堆深处为好。如果你有一个递归的版本，这就是你实际上已经做了的事情。这只是因为你会使用调用堆栈而不是像现在这样做的显式堆栈，所以存储将是“不可见的”。

如果它可以帮助您，您可以轻松地将深度优先搜索转换为宽度优先搜索，方法是将数组用作队列而不是堆栈。（只要removeFirstObject而不是removeLastObject。）然后你就会知道你总是按照非递减深度的顺序来看节点。但是，如果您需要确切的深度，我认为您仍需要添加一些存储空间来跟踪何时必须增加当前深度。

更新：

你应该能够做一个DFS没有完全堆栈，相反，如果你按照备份树的节点的父指针。这将使维持深度变得简单。但是，您必须小心，不要通过重新扫描孩子以找出您所在的位置来打破线性时间最坏情况的复杂性。

如果您没有父指针，应该可以堆叠足够的信息来跟踪父母。但是这意味着你在堆栈上放置了比现在更多的信息，所以对于直接堆叠深度没有什么改进。

顺便说一句，仔细查看你的算法，当你得到下一个当前节点时，你不是在查看数组的错误的一面吗？它应该像这样工作：

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

来源

2011-04-26 09:33:55 njlarsson

不幸的是我真的需要DFS。无法将其更改为BFS。 – 2011-04-26 10:03:33

我编辑了我的答案，查看更新。 – njlarsson 2011-04-28 09:01:06

我不理解你的符号，但如果我正确地阅读你处理一个节点，并将所有的孩子添加到你的工作清单。

如果您可以将该部分更改为使用递归，则可以跟踪树深度，因为它将是递归深度。

因此，不是添加子节点，而是为每个子节点递归。

心连心

马里奥

来源

2011-04-26 09:21:05

我特意避免了递归，因为图可能变得很大。递归是一件坏事。易于实施。但很糟糕。 – 2011-04-26 10:02:35

你可以使用尾递归。很多编译器都实现了这一点。我也不完全同意递归是坏的声明。 – 2011-04-26 10:37:49

我相信你在做的实际上是BFS。你正在使用列表。为了做DFS，你应该使用堆栈;

This可能是深度道有用的，你可能会考虑向量p（父母）

来源

2011-04-26 10:11:19 Madrugada

-1

假设你正在做BFS，最容易做的事情是引入深度另一个队列，反映您的节点队列。初始化深度为零。每次您推入节点队列时，将当前深度+1推入深度队列。

来源

2014-10-09 02:30:46 nicodjimenez

如何跟踪此对象图深度优先搜索算法的深度？

回答

相关问题