1

Pythonで、BFSではなくDFSを使用して、ノードごとに任意の数の子を持つツリーで最も深い葉の深さを返すコードを記述しようとしています。私は近くにいるように見えますが、次のコードにはまだ理解できないバグがあります（つまり、返された深さが正しくありません）。何か助けはありますか？

テストツリーは単純に次のようになります：[[1,2,3]、[4,5]、[6]、[7]、[8]、[]、[]、[]、[]]

def max_depth_dfs(tree): # DOESN'T WORK

    max_depth, curr_depth, Q = 0,0, [0]
    visited = set()

    while Q != []:
        n = Q[0]
        more = [v for v in tree[n] if v not in visited]
        if not more:
            visited.add(n)
            curr_depth -= 1
            Q = Q[1:]
        else:
            curr_depth += 1

        max_depth = max(max_depth, curr_depth)
        Q = more + Q

    return max_depth
4

4 に答える 4

1

バグ発見！

if not more:
    visited.add(n)
    curr_depth -= 1
    Q = Q[1:]

ノード 4 にアクセスすると、curr_depth は 2 になります。ノード 4 には子がないため、curr_depth を減らすと、curr_depth は 1 になります。ただし、次にアクセスするノードはノード 5 であり、ノード 5 の深さは 1 ではなく 2 です。したがって、curr_depth はツリー内のノードの正しい深さを記録しません。

次の解決策が役立つ場合があります。

def max_depth_dfs(tree):

    max_depth, curr_depth, Q = 0, 0, [0]
    visited = set()

    while Q != []:
        n = Q[0]

        max_depth = max(max_depth, curr_depth)

        if n in visited:
            curr_depth -= 1
            Q = Q[1:]
            continue

        #print n, curr_depth     #show the node and its depth in the tree

        visited.add(n)
        more = [v for v in tree[n]]
        if not more:
            Q = Q[1:]
        else:
            curr_depth += 1
            Q = more + Q

    return max_depth
于 2012-05-19T06:39:30.063 に答える
1

try .. catch枝と葉を区別していました。更新これ以上の例外はありません:)

from collections import Iterable
tree = [[1,2,3],[4,5, [1, 6]],[6],[7],[8],[],[],[],[]]

def max_depth(tree, level=0):
  if isinstance(tree, Iterable):
    return max([ max_depth(item, level+1) for item in tree])
  else: # leaf
    return level

print max_depth(tree)
于 2012-05-18T20:52:20.777 に答える
0

非再帰バージョンは次のとおりです。

from collections import Iterable

def max_depth_no_recur(tree):
  max_depth, node =  0, iter(tree)
  stack = [node]
  while stack:
    try:
      n = node.next()
    except StopIteration:
      if len(stack) > max_depth:
        max_depth = len(stack)
      node = stack.pop()
      continue

    if isinstance(n, Iterable):
        stack.append(node)
        node = iter(n)
  return max_depth
于 2012-05-18T21:36:19.990 に答える
0

Alex と Adonis から得たすべての良いフィードバックを考慮してコードを改良した後、現在、現在のバージョンを使用しています。

def max_depth_dfs(tree): # correct

max_depth, curr_depth, Q = 0, 0, [0]
visited = set()

while Q != []:

    n = Q[0]

    if n in visited:
        Q = Q[1:]
        curr_depth -= 1
        visited.remove(n) # won't go back, save memory 
        print 'backtrack from', n        
        continue

    # proper place to print depth in sync with node id
    print 'visiting', n, 'children=', tree[n], 'curr_depth=', curr_depth, 'Q=', Q,
    print visited # only current path, instead of visited part of tree

    if tree[n]:
        visited.add(n) # if leaf, won't ever try to revisit
        Q = tree[n] + Q
        curr_depth += 1
        max_depth = max(max_depth, curr_depth) # no need to check if depth decreases
    else:
        Q = Q[1:] # leaf: won't revisit, will go to peer, if any, so don't change depth
        print 'no children for', n

return max_depth
于 2012-05-19T18:33:34.127 に答える