如何跟蹤此對象圖深度優先搜索算法的深度？

我有這個代碼遍歷樹，進行深度優先搜索。每個元素都只處理一次。很好。如何跟蹤此對象圖深度優先搜索算法的深度？

-(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

如何跟蹤此對象圖深度優先搜索算法的深度？

回答

相關問題