โปรแกรมหาความยาวของเส้นทางที่ยาวที่สุดใน DAG โดยไม่ซ้ำนโหนดใน Python

สมมติว่าเรามีกราฟทิศทางไม่มีวัฏจักร (DAG) ที่แสดงด้วยรายการติดกัน (adjacency list) เราต้องการหาเส้นทางที่ยาวที่สุดในกราฟโดยไม่ให้มีการซ้ำนโหนด

เช่น ถ้าข้อมูลนำเข้าคือกราฟที่โหนด 0 เชื่อมไป 1,2 โหนด 1 เชื่อมไป 3,4 โหนด 3 เชื่อมไป 4 โหนด 4 เชื่อมไป 2 ผลลัพธ์จะเป็น 4 เนื่องจากเส้นทางคือ 0 → 1 → 3 → 4 → 2 ความยาว 4

ขั้นตอนการแก้ปัญหา (DFS + Memoization)

• ans := 0, n := จำนวนโหนด
• table := array ขนาด n เติม -1
• ฟังก์ชัน dfs(u):
  • ถ้า table[u] != -1 คืน table[u]
  • p_len := 0
  • วนทุกโหนด v ใน graph[u]:
    • p_len := max(p_len, 1 + dfs(v))
  • table[u] := p_len, คืน p_len
• จากเมธอดหลัก วน i 0 ถึง n-1: ans := max(ans, dfs(i))
• คืน ans

ตัวอย่างโค้ด

class Solution:
    def solve(self, graph):
        ans = 0
        n = len(graph)
        table = [-1] * n
        def dfs(u):
            if table[u] != -1:
                return table[u]
            p_len = 0
            for v in graph[u]:
                p_len = max(p_len, 1 + dfs(v))
            table[u] = p_len
            return p_len
        for i in range(n):
            ans = max(ans, dfs(i))
        return ans

ob = Solution()
graph = [
    [1, 2],
    [3, 4],
    [],
    [4],
    [2],
]
print(ob.solve(graph))

ข้อมูลนำเข้า

graph = [[1, 2],[3, 4],[],[4],[2]]

ผลลัพธ์

4