我怎样才能找到最大深度

Question

如何制作 FindMaxDepth 方法/此函数将查找树的最长深度（根节点与最后一个叶节点之间的距离），该函数将采用的输入是：（graph, rootNode ) 并且输出将是一个数值。

例子：如果输入下图，startNode = A，输出必须是4

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": [],
}
visited = []


def dfs(visited, graph, root):
    if root not in visited:
        visited.append(root)
        print(root)
        for child in graph[root]:
            dfs(visited, graph, child)


dfs(visited, graph, "A")


def bfs(graph, root):
    visited = []
    queue = []
    visited.append(root)
    queue.append(root)
    while queue:
        x = queue.pop(0)
        print(x)
        for child in graph[x]:
            if child not in visited:
                visited.append(child)
                queue.append(child)


# bfs(graph, "A")

Answer 1

bfs 可以在内部跟踪它，因为它不是递归的。 dfs 需要全局（或模拟全局）来跟踪最大值。

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": [],
}
visited = []


def dfs(visited, graph, root, depth=0):
    global maxdepth
    maxdepth = max(depth,maxdepth)
    if root not in visited:
        visited.append(root)
        print(root)
        for child in graph[root]:
            dfs(visited, graph, child, depth+1)


maxdepth = 0
dfs(visited, graph, "A")
print("max depth", maxdepth)


def bfs(graph, root):
    maxdepth = 0
    visited = []
    queue = []
    visited.append(root)
    queue.append((root,1))
    while queue:
        x,depth = queue.pop(0)
        maxdepth = max(maxdepth,depth)
        print(x)
        for child in graph[x]:
            if child not in visited:
                visited.append(child)
                queue.append((child,depth+1))
    return maxdepth

print("max depth", bfs(graph, "A"))

Answer 2

一个更简单的解决方案是将每个 child 的深度加 1：

def depth(root):
  children = graph[root]
  
  if len(children) == 0:
    return 1
  
  return 1 + max( depth(child) for child in children )

Answer 3

您不需要为树结构跟踪访问过的节点，因为不会有循环引用。节点的递归遍历就足够了：

def maxDepth(graph,node):
    return 1 + max((maxDepth(graph,n) for n in graph[node]),default=0)

输出：

graph = {
    "A": ["B", "C"],
    "B": ["D", "E"],
    "C": ["F"],
    "D": [],
    "E": ["F"],
    "F": [],
}
print(maxDepth(graph,"A")) # 4

我怎样才能找到最大深度

How can i find the max depth

python

depth-first-search