Pythonのn-aryツリーで最長のパスの長さを見つけるプログラム

各アイテムが保持しているエッジリスト（u、v）があり、uがvの親であることを表しているとします。ツリー内で最も長いパスの長さを見つける必要があります。パスの長さは、1+そのパス内のノードの数です。

したがって、入力が次のような場合

パスが[1、4、5、7]であり、合計4つのノードがあるため、出力は5になります。したがって、パスの長さは1 + 4=5です。

これを解決するには、次の手順に従います-

• g：=指定されたエッジリストからのグラフの隣接リスト
• d：=新しい地図
• 関数bfs（）を定義します。これには時間がかかります
• 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
      • qにyを挿入
• return f
• メインの方法から、次の手順を実行します-
• gの各oについて、
  • f：=bfs（o）
  • d：=新しい地図
  • return 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