gpt4 book ai didi

python - 在 networkx 图中查找给定长度的所有路径/步行

转载 作者:太空狗 更新时间:2023-10-30 01:58:26 31 4
gpt4 key购买 nike

我正在使用 networkx 并尝试在图中找到所有长度为 3 的路径,特别是具有三个边的路径。我试图在 networkx 文档中找到有关算法的一些信息,但我只能在图中找到最短路径的算法。如果最短路径是 14 -> 15 -> 16,我能否找到通过特定节点的路径长度,例如通过节点 14 -> 11 -> 12 -> 16 的路径?这是一个示例图的图像:

example graph

最佳答案

最简单的版本(下面是我认为更快的另一个版本):

def findPaths(G,u,n):
if n==0:
return [[u]]
paths = [[u]+path for neighbor in G.neighbors(u) for path in findPaths(G,neighbor,n-1) if u not in path]
return paths

这需要一个网络 G 和一个节点 u 和一个长度 n。它以递归方式查找从 u 的不包含 u 的邻居开始的所有长度为 n-1 的路径。然后它将 u 放在每个这样的路径的前面,并返回这些路径的列表。

注意,每个路径都是一个有序列表。它们都从指定的节点开始。所以对于你想要的,只需围绕这个循环:

allpaths = []
for node in G:
allpaths.extend(findPaths(G,node,3))

请注意,这将有任何 a-b-c-d 路径以及相反的 d-c-b-a 路径。

如果您发现“列表理解”很难解释,这里有一个等效的选项:

def findPathsNoLC(G,u,n):
if n==0:
return [[u]]
paths = []
for neighbor in G.neighbors(u):
for path in findPathsNoLC(G,neighbor,n-1):
if u not in path:
paths.append([u]+path)
return paths

为了优化这一点,尤其是在有很多循环的情况下,可能值得发送一组不允许的节点。在每个嵌套调用中,它会知道不包括递归中更高层的任何节点。这将代替 if u not in path 检查。代码会有点难以理解,但运行速度会更快。

def findPaths2(G,u,n,excludeSet = None):
if excludeSet == None:
excludeSet = set([u])
else:
excludeSet.add(u)
if n==0:
return [[u]]
paths = [[u]+path for neighbor in G.neighbors(u) if neighbor not in excludeSet for path in findPaths2(G,neighbor,n-1,excludeSet)]
excludeSet.remove(u)
return paths

请注意,我必须在递归调用之前将 u 添加到 excludeSet,然后在返回之前将其删除。

关于python - 在 networkx 图中查找给定长度的所有路径/步行,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28095646/

31 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com