从给定图中寻找所有路径 Python

Question

我需要找到一个给定图中的所有路径。目前我可以做到这一点，但我的递归代码效率不高，而且我的图非常复杂。所以我需要一个更好的算法。以下是我目前的代码：

def findLeaves(gdict):
    # takes graph and find its leaf nodes
    leaves = []
    for endNode in gdict.iterkeys():
        if not gdict[endNode]:
            leaves.append(endNode)
    return leaves

graphPaths = {}    
def findPaths(gname, gdict, leave, path):
    # finds all noncycle paths
    if not gdict:
        return []
    temp = [node for node in gdict.iterkeys() if leave in gdict[node].keys() and node not in path] 
    if temp:
        for node in temp:
            findPaths(gname, gdict, node, [node] + path) 
    else:
        graphPaths[gname].append(path)   




    # main
    leaves = findLeaves(graph['graph'])
    graphPaths['name'] = []

    seenNodes = []
    for leave in leaves:
        findPaths(graph['name'], graph['graph'], leave, [leave])

这个图只有一个起始节点，这让递归函数的实现变得简单。每个叶子节点在反向遍历时都需要到达这个起始节点。起始节点是指没有任何边指向它的节点。

我有很多图，所以我把它们存放在一个字典里。字典的键是图的名称。以下是我数据的一个例子：

graph['graph']: {
0: {1: {}}, 
1: {2: {}, 3: {}}, 
2: {3: {}}, 
3: {4: {}}, 
4: {5: {}}, 
5: {6: {}}, 
6: {7: {}}, 
7: {6: {}, 5: {}}
}

graph['name'] = nameofthegraph

这个结构是从 pygraphviz 中获取的，它简单地展示了任何节点的出边。字典的键是节点，值是指向其他节点的出边。然而，当我处理非常复杂的图时，如下图所示，这段代码无法找到所有路径。

你能建议一个更好的算法吗？或者有没有办法优化我的算法以应对复杂的图？

Answer 1

你为什么需要从一个给定的图中找出所有路径呢？是在什么情况下需要的？我问这个问题是因为图论在计算机领域非常流行，可能有一个算法正好符合你的需求……

比如说，如果你最终需要比较所有路径来找到最佳路径，你可能会对“最短路径问题”感兴趣，可以看看这个链接：在两个图节点之间找到所有路径 和 https://en.wikipedia.org/wiki/Shortest_path_problem

关于“优化”这个话题，Python 允许你使用列表推导式、多线程和/或基于子进程的代码。

你也可以尝试使用“原生图数据库”（比如 neo4j），来存储你的节点，然后使用一些内置的方法，比如：http://neo4j.com/docs/stable/cypherdoc-finding-paths.html 来完成这个工作。

祝好