寻求使用邻接表python列出所有最长路径的建议

问题描述 投票:1回答:1

由于我是图结构的新手,我正在写这本书来询问查找和列出最长路径的建议和建议。

enter image description here

根据我的目的,是在有向无环图中找到最长的路径。我找到了这个博客,并应用了部分代码以适合我的数据。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

预先感谢您的所有建议

python graph
1个回答
© www.soinside.com 2019 - 2024. All rights reserved.