在 Python 中查找 n 叉树中最长路径长度的程序

假设我们有一个边列表，其中每个项目都持有 (u, v) 表示 u 是 v 的父级。我们必须找到树中最长路径的长度。路径长度为 1 + 该路径中的节点数。

所以，如果输入像

那么输出会是 5，因为路径是 [1, 4, 5, 7]，一共有 4 个节点，所以路径长度是 1 + 4 = 5。

示例

让我们看看以下实现以更好地理解 -

def solve(edges):
   g = {}
   for u, v in edges:
      if u not in g:
         g[u] = []
      g[u] += (v,)
      if v not in g:
         g[v] = []
      g[v] += (u,)
   d = {}

   def bfs(o):
      d[o] = 1
      f = o
      q = [o]
      for x in q:
         for y in g[x]:
            if y not in d:
               d[y] = d[x] + 1
               if d[y] > d[f]:
                  f = y
               q += (y,)
      return f

   for o in g:
      f = bfs(o)
      d = {}
      return d[bfs(f)]
   return 0

edges = [(1, 2),(1, 3),(1, 4),(4, 5),(5,7),(1,6),(4,8)]
print(solve(edges))

输入

[(1, 2),(1, 3),(1, 4),(4, 5),(5,7),(1,6),(4,8)]

5