2

我正在使用递归来查找从某个点 A 到某个点 D 的路径。我正在遍历一个图来查找路径。

让我们说：

图 = {'A':['route1','route2'],'B':['route1','route2','route3','route4'],'C':['route3','route4 '], 'D':['route4'] }

可通过以下方式访问：

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 个值）时，我都会添加一个检查。

但是通过检查，我只得到一个解决方案：route1 -> route2 -> route4，而不是其他可能的解决方案。

这是实际的编码：路由将被反应取代。

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 是手动计算出来的。

4

1 回答 1

3

好吧，我无法理解您对图表的表示。但这是一种通用算法，可用于查找所有避免无限循环的路径。

首先，您需要将您的图形表示为一个字典，它将节点映射到它们所连接的一组节点。例子：

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

这意味着 fromA你可以去Band 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

这将为您提供要遵循的链接而不是要遍历的节点的路径。希望这可以帮助 ：）

于 2013-02-26T00:58:29.163 回答