时间戳

首页 > 解决方案 > 使用邻接列表 python 征求意见以列出所有最长的路径

python - 使用邻接列表 python 征求意见以列出所有最长的路径

问题描述

由于我是图形结构的新手，因此我写信询问有关查找和列出最长路径的建议和建议。

在此处输入图像描述

根据我的目的是在有向无环图中找到最长的路径。我找到了这个博客，并应用了一些代码来适应我的数据。 https://www.geeksforgeeks.org/longest-path-in-a-directed-acyclic-graph-dynamic-programming/

    def dfs(node, adj, dp, vis): 

        # Mark as visited 
        vis[node] = True

        # Traverse for all its children 
        for i in range(0, len(adj[node])): 

            # If not visited 
            if not vis[adj[node][i]]: 
                dfs(adj[node][i], adj, dp, vis) 

            # Store the max of the paths 
            dp[node] = max(dp[node], 1 + dp[adj[node][i]]) 

    # to add an edge 
n = len(adj_Matrix)

## change to adjacency list to decrease the space that have kept zero.

adj = [[] for i in range(n + 1)] 

for i in range(len(adj_Matrix)):
    for j in range(len(adj_Matrix)):
        if(adj_Matrix[i][j] == 1):
            adj[i].append(j)


    # Function that returns the longest path 
    def findLongestPath(adj, n): 

        # Dp array 
        dp = [0] * (n + 1) 

        # Visited array to know if the node 
        # has been visited previously or not 
        vis = [False] * (n + 1) 

        # Call DFS for every unvisited vertex 
        for i in range(1, n + 1): 
            if not vis[i]: 
                dfs(i, adj, dp, vis) 

        ans = 0

        # Traverse and find the maximum of all dp[i] 
        for i in range(1, n + 1): 
            ans = max(ans, dp[i]) 

        return ans

该代码将结果10作为我的定向路径返回，但我想请教您如何获取此问题中所有最长路径的列表？有什么推荐的博客我需要学习吗？

例如，根据博客，结果返回数组中的最大值，但我希望看到结果返回每个节点中最长路径的列表，如：

node 1: 1->3->2->4
node 2: 2->4
node 3: 3->2->4
node 4: Null

提前感谢您的所有建议

标签： pythongraph

解决方案

将路径与长度一起存储在dp

def dfs(node, adj, dp, vis): 
    # Mark as visited 
    vis[node] = True
    # Traverse for all its children 
    for i in range(0, len(adj[node])): 
        # If not visited 
        if not vis[adj[node][i]]: 
            dfs(adj[node][i], adj, dp, vis) 
        # Store the max of the paths 
        dp[node] = max(dp[node], [node] + dp[adj[node][i]], key=lambda x: len(x))

# Function that returns the longest path 
def findLongestPath(adj, n): 
    # Dp array 
    dp = [[x] for x in range(n + 1)]
    # Visited array to know if the node 
    # has been visited previously or not 
    vis = [False] * (n + 1) 
    # Call DFS for every unvisited vertex 
    for i in range(1, n + 1): 
        if not vis[i]: 
            dfs(i, adj, dp, vis) 
    # Traverse and find the maximum of all dp[i] 
    return max([dp[i] for i in range(1, n + 1)], key=lambda x: len(x))

dp 现在存储来自每个节点的所有最长路径。要检索所有这些路径的列表，我们可以稍微修改该函数。

def findLongestPathFromEachNode(adj, n): 
    # Dp array 
    dp = [[x] for x in range(n)]
    # Visited array to know if the node 
    # has been visited previously or not 
    vis = [False] * (n + 1) 
    # Call DFS for every unvisited vertex 
    for i in range(1, n + 1): 
        if not vis[i]: 
            dfs(i, adj, dp, vis) 
    # Traverse and find the maximum of all dp[i]
    return dp[1:]

推荐阅读