由于我是图结构的新手,我正在写这本书来询问查找和列出最长路径的建议和建议。
根据我的目的,是在有向无环图中找到最长的路径。我找到了这个博客,并应用了部分代码以适合我的数据。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
预先感谢您的所有建议