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

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

因此，如果输入如下所示

那么输出将为5，因为路径是[1，4，5，7]，总共有4个节点，因此路径长度为1 + 4 = 5。

为了解决这个问题，我们将采取以下步骤−

• g：从给定的边缘列表生成图的邻接列表
• d：一个新的映射
• 定义一个函数bfs()。这将采取o
• d[o]：= 1
• f：=o
• q：=[o]
• 对于q中的每个x，执行以下操作
  • 对于g[x]中的每个y，执行以下操作
    • 如果y不在d中，则
    • d[y]：= d[x] +1
    • 如果d[y] > d[f]，则
      • f：=y
    • 将y插入q
• 返回f
• 从主方法中，执行以下操作−
• 对于g中的每个o，执行以下操作
  • f：= bfs(o)
  • d：=一个新的映射
  • 返回d[bfs(f)]
• 返回0

示例

让我们看一下以下实现，以获得更好的理解−

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