สมมติว่าเรามีกราฟ acyclic กำกับหนึ่งรายการที่แสดงโดยรายการที่อยู่ติดกัน เราต้องหาเส้นทางที่ยาวที่สุดในกราฟโดยไม่เกิดโหนดซ้ำ
ดังนั้นหากอินพุตเป็นแบบ
จากนั้นผลลัพธ์จะเป็น 4 เนื่องจากเส้นทางคือ 0 -> 1 -> 3 -> 4 -> 2 ที่มีความยาว 4
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- ตอบ :=0
- n :=จำนวนโหนดของกราฟ
- table :=รายการขนาด n และเติม -1
- กำหนดฟังก์ชัน dfs() สิ่งนี้จะพาคุณ
- ถ้า table[u] ไม่ใช่ -1 แล้ว
- กลับตาราง[u]
- p_len :=0
- สำหรับแต่ละ vectex v ในกราฟ[u] ทำ
- p_len :=สูงสุดของ p_len และ (1 + dfs(v))
- ตาราง[u] :=p_len
- ส่งคืน p_len
- จากวิธีหลัก ให้ทำดังนี้ -
- สำหรับ i ในช่วง 0 ถึง n ให้ทำ
- ans :=สูงสุดของ ans, dfs(i)
- คืนสินค้า
ตัวอย่าง (Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
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
