पायथन में n-ary ट्री में सबसे लंबे पथ की लंबाई खोजने का प्रोग्राम

मान लीजिए हमारे पास एक एज लिस्ट है जहां प्रत्येक आइटम (u, v) रखता है जो दर्शाता है कि u, v का पैरेंट है। हमें ट्री में सबसे लंबे पथ की लंबाई ढूंढनी है। पथ की लंबाई 1 + उस पथ में नोड्स की संख्या है।

उदाहरण के लिए, यदि इनपुट है:

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

एल्गोरिदम (दो BFS पास)

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))  # आउटपुट: 5

इनपुट

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