Python - หาความยาวเส้นทางที่ยาวที่สุดใน N-ary Tree

โจทย์: กำหนด Edge List ที่แต่ละรายการ (u, v) แสดงว่า u เป็นพาเรนต์ของ v หา ความยาวเส้นทางที่ยาวที่สุด (Diameter) ในต้นไม้ โดยนิยามความยาว = 1 + จำนวนโหนดในเส้นทาง

ตัวอย่าง

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

โครงสร้างต้นไม้:

        1
      / | \
     2  3  4
         / \
        5   8
       /
      7

อัลกอริทึม: Two BFS (Double BFS) หา Diameter

หลักการ: เริ่ม BFS จากโหนดไหนก็ได้ หาจุดไกลสุด f แล้ว BFS จาก f อีกครั้ง ระยะทางไกลสุดครั้งที่ 2 = Diameter

ขั้นตอนการทำงาน

1. สร้าง Adjacency List g จาก Edge List (Undirected)
2. ฟังก์ชัน bfs(o):
   • d[o] = 1 (ระยะจากตัวเอง = 1)
   • BFS ปกติ อัปเดต d[y] = d[x] + 1
   • ติดตามโหนดไกลสุด f
   • คืนค่า f
3. จากโหนดไหนก็ได้ใน g:
   • f = bfs(o) (หาจุดไกลสุดจากจุดเริ่มต้น)
   • รีเซ็ต d = {}
   • คืนค่า d[bfs(f)] (ระยะทางจากจุดไกลสุดไปจุดไกลสุดอีกฝั่ง)

โค้ด Python

def solve(edges):
    # สร้าง Adjacency List (Undirected)
    g = {}
    for u, v in edges:
        if u not in g:
            g[u] = []
        g[u].append(v)
        if v not in g:
            g[v] = []
        g[v].append(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.append(y)
        return f
    
    # Two BFS trick
    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))  # Output: 5

ความซับซ้อน

• Time Complexity: O(N) โดย N = จำนวนโหนด (BFS 2 รอบ)
• Space Complexity: O(N) สำหรับ Adjacency List และ Distance Map

หมายเหตุเกี่ยวกับโค้ดต้นฉบับ

โค้ดต้นฉบับมี for o in g: แต่มี return อยู่ในลูป ทำให้รันแค่รอบเดียว (ซึ่งก็เพียงพอแล้ว เพราะ BFS ครั้งแรกจากโหนดไหนก็ได้จะหาจุดปลายเส้นทางยาวสุดได้) แต่การเขียนที่ชัดเจนกว่าควรแยกนอกลูป:

def solve(edges):
    g = {}
    for u, v in edges:
        g.setdefault(u, []).append(v)
        g.setdefault(v, []).append(u)
    
    def bfs(start):
        dist = {start: 1}
        q = [start]
        farthest = start
        for x in q:
            for y in g[x]:
                if y not in dist:
                    dist[y] = dist[x] + 1
                    if dist[y] > dist[farthest]:
                        farthest = y
                    q.append(y)
        return farthest, dist
    
    # เริ่มจากโหนดแรก
    any_node = next(iter(g))
    farthest1, _ = bfs(any_node)
    farthest2, dist2 = bfs(farthest1)
    return dist2[farthest2]

# ทดสอบ
edges = [(1, 2), (1, 3), (1, 4), (4, 5), (5, 7), (1, 6), (4, 8)]
print(solve(edges))  # 5

การทดสอบเพิ่มเติม

# เส้นตรง (Line)
print(solve([(1,2), (2,3), (3,4), (4,5)]))  # 5

# ดาว (Star)
print(solve([(1,2), (1,3), (1,4), (1,5)]))  # 3 (1-2-1-3 path length 3 nodes = 3)

# Binary Tree
edges = [(1,2), (1,3), (2,4), (2,5), (3,6), (3,7)]
print(solve(edges))  # 5 (4-2-1-3-6 or similar)