Python 中查詢 DAG 中最長路徑（無重複節點）的程式

假設我們有一個由鄰接表表示的有向無環圖。我們需要找到圖中最長的路徑，且路徑中沒有重複的節點。

因此，如果輸入類似於

則輸出將是 4，因為路徑為 0 -> 1 -> 3 -> 4 -> 2，長度為 4。

為了解決這個問題，我們將遵循以下步驟：

• ans := 0
• n := 圖的節點數
• table := 一個大小為 n 的列表，並填充 -1
• 定義一個函式 dfs()。它將接收 u
• 如果 table[u] 不為 -1，則
  • 返回 table[u]
• p_len := 0
• 對於圖[u] 中的每個頂點 v，執行以下操作：
  • p_len := p_len 和 (1 + dfs(v)) 中的最大值
• table[u] := p_len
• 返回 p_len
• 在主方法中執行以下操作：
• 對於範圍從 0 到 n 的 i，執行以下操作：
  • ans := ans 和 dfs(i) 中的最大值
• 返回 ans

示例（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

Arnab Chakraborty

更新於：2020-12-12

895 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

開始學習