पायथन में एक एन-आरी पेड़ में सबसे लंबे पथ की लंबाई खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक किनारे की सूची है जहां प्रत्येक आइटम धारण कर रहा है (यू, वी) दर्शाता है कि आप वी के माता-पिता हैं। हमें पेड़ में सबसे लंबे पथ की लंबाई का पता लगाना है। पथ की लंबाई उस पथ में 1 + नोड्स की संख्या है।

तो, अगर इनपुट पसंद है

तो आउटपुट 5 होगा, क्योंकि पथ [1, 4, 5, 7] है, कुल 4 नोड हैं, इसलिए पथ की लंबाई 1 + 4 =5 है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

g :=दी गई किनारे सूची से ग्राफ़ की आसन्नता सूची
d :=एक नया नक्शा
एक फ़ंक्शन को परिभाषित करें bfs() । इसमें o
d[o] :=1
f :=o
क्यू:=[ओ]
क्यू में प्रत्येक x के लिए, करें
- g में प्रत्येक y के लिए[x], करें
  - यदि y d में नहीं है, तो
    - d[y] :=d[x] + 1
    - अगर घ[y]> d[f], तो
      - f :=y
    - q में y डालें
वापसी f
मुख्य विधि से, निम्न कार्य करें -
जी में प्रत्येक ओ के लिए, करें
- f :=bfs(o)
- d :=एक नया नक्शा
- रिटर्न डी[बीएफएस(एफ)]
वापसी 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)]