在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