在Python中查找DAG的没有重复节点的最长路径的程序

在Python中查找DAG的没有重复节点的最长路径的程序

假设我们有一个由邻接表表示的有向无环图。我们必须找到图中没有节点重复的最长路径。

因此,如果输入如下所示:

在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
  • 对于图中的每个向量v,执行以下操作 –
    • p_len:=p_len和(1+dfs(v))的最大值
  • table[u]:=p_len
  • 返回p_len
  • 从主方法执行以下操作 –
  • 对于范围从0到n中的i,执行以下操作-
    • ans:= ans和dfs(i)的最大值
  • 返回ans

更多Python相关文章,请阅读:Python 教程

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

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程