โปรแกรมหาความยาวของพาธที่ยาวที่สุดใน n-ary tree ใน Python

สมมุติว่าเรามี edge list ที่แต่ละอันมีไว้ (u, v) แทน u เป็น parent ของ v. เราต้องหาความยาวของ path ที่ยาวที่สุดใน tree ความยาวเส้นทางคือ 1 + จำนวนโหนดในเส้นทางนั้น

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 5 เนื่องจากเส้นทางคือ [1, 4, 5, 7] มีทั้งหมด 4 โหนด ดังนั้นความยาวเส้นทางคือ 1 + 4 =5

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

g :=รายการที่อยู่ติดกันของกราฟจากรายการขอบที่กำหนด
d :=แผนที่ใหม่
กำหนดฟังก์ชัน bfs() นี้จะใช้เวลา o
d[o] :=1
f :=o
q :=[o]
สำหรับแต่ละ x ใน q ทำ
- สำหรับแต่ละ y ใน g[x] ทำ
  - ถ้า y ไม่อยู่ใน d แล้ว
    - d[y] :=d[x] + 1
    - ถ้า d[y]> d[f] แล้ว
      - f :=y
    - แทรก y ใน q
กลับมา f
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
สำหรับแต่ละ o ใน g ทำ
- 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)]