Python：如何在递归循环中找到多个路径，当多个子节点回指父节点时？

Question

我正在使用递归的方法来寻找从某个点A到点D的路径。我的目标是遍历一个图来找到这些路径。

假设这个图是这样的：

图 = {'A':['路线1','路线2'],'B':['路线1','路线2','路线3','路线4'], 'C':['路线3','路线4'], 'D':['路线4'] }

可以通过以下方式访问：

A -> 路线1, 路线2

B -> 路线2, 路线3, 路线4

C -> 路线3, 路线4

从A到D有两条路径：

路线1 -> 路线2 -> 路线4

路线1 -> 路线2 -> 路线3 -> 路线4

因为点B和点A都有路线1和路线2，所以会出现无限循环。因此，我在每次访问节点时添加了一个检查（0或1的值）。

不过，添加了检查后，我只得到了一个解决方案：路线1 -> 路线2 -> 路线4，而没有得到另一个可能的解决方案。

下面是实际的代码：路线将被替换为反应。

def find_all_paths(graph,start, end, addReaction, passed = {}, reaction = [] ,path=[]):

    passOver =  passed 

    path = path + [start]   
    reaction = reaction + [addReaction]
    if start == end:
        return [reaction] 
    if not graph.has_key(start):
        return []

    paths=[]
    reactions=[]

    for x in range (len(graph[start])):    
        for y in range (len(graph)):
            for z in range (len(graph.values()[y])):
                if (graph[start][x] == graph.values()[y][z]): 
                    if passOver.values()[y][z] < 161 :
                        passOver.values()[y][z] = passOver.values()[y][z] + 1
                            if (graph.keys()[y] not in path):
                                newpaths = find_all_paths(graph, (graph.keys()[y]), end, graph.values()[y][z], passOver , reaction, path)
                            for newpath in newpaths:
                                reactions.append(newpath)
    return reactions

这是方法调用：dic_passOver是一个字典，用来记录节点是否被访问过。

solution = (find_all_paths( graph, "M_glc_DASH_D_c', 'M_pyr_c', 'begin', dic_passOver ))

我的问题似乎是，一旦访问过某条路线，就无法再访问它，因此其他可能的解决方案就无法找到。为了解决这个问题，我设置了一个最大递归次数为161，这样就能找到我特定代码的所有可能路线。

if passOver.values()[y][z] < 161 :
                        passOver.values()[y][z] = passOver.values()[y][z] + 1

然而，这样的方法效率很低，而且我的数据大多数是有成千上万的索引的图。此外，我也不知道为了找到所有路线，允许访问节点的次数应该是多少。这个161的数字是手动算出来的。

Answer 1

嗯，我不太明白你图的表示方式。不过，这里有一个通用的算法，可以用来找到所有路径，并且避免无限循环。

首先，你需要把你的图用字典的方式表示出来，这个字典把每个节点和它连接的节点集合对应起来。比如：

graph = {'A':{'B','C'}, 'B':{'D'}, 'C':{'D'}}

这意味着从 A 你可以到达 B 和 C。从 B 你可以到达 D，而从 C 也可以到达 D。我们假设这些连接是单向的。如果你想要双向连接，只需要为两个方向都添加连接。

如果你按照这种方式表示你的图，你可以使用下面的函数来找到所有路径：

def find_all_paths(start, end, graph, visited=None):
    if visited is None:
        visited = set()

    visited |= {start}
    for node in graph[start]:
        if node in visited:
            continue
        if node == end:
            yield [start,end]
        else:
            for path in find_all_paths(node, end, graph, visited):
                yield [start] + path

使用示例：

>>> graph = {'A':{'B','C'}, 'B':{'D'}, 'C':{'D'}}
>>> for path in find_all_paths('A','D', graph):
...   print path
... 
['A', 'C', 'D']
['A', 'B', 'D']
>>> 

编辑以考虑评论，澄清图的表示方式

下面是一个函数，用来将你的图的表示方式（假设我理解正确，并且路径是双向的）转换成上面算法所用的那种表示方式。

def change_graph_representation(graph):
    reverse_graph = {}
    for node, links in graph.items():
        for link in links:
            if link not in reverse_graph:
                reverse_graph[link] = set()
            reverse_graph[link].add(node)

    result = {}
    for node,links in graph.items():
        adj = set()
        for link in links:
            adj |= reverse_graph[link]
        adj -= {node}
        result[node] = adj
    return result

如果你需要找到路径时关注的是连接，而不是经过的节点，你可以这样保留这些信息：

def change_graph_representation(graph):
    reverse_graph = {}
    for node, links in graph.items():
        for link in links:
            if link not in reverse_graph:
                reverse_graph[link] = set()
            reverse_graph[link].add(node)

    result = {}
    for node,links in graph.items():
        adj = {}
        for link in links:
            for n in reverse_graph[link]:
                adj[n] = link
        del(adj[node])
        result[node] = adj
    return result

然后使用这个修改过的搜索：

def find_all_paths(start, end, graph, visited=None):
    if visited is None:
        visited = set()

    visited |= {start}
    for node,link in graph[start].items():
        if node in visited:
            continue
        if node == end:
            yield [link]
        else:
            for path in find_all_paths(node, end, graph, visited):
                yield [link] + path

这样你就能得到按照连接来表示的路径，而不是经过的节点。希望这对你有帮助 :)