python - 获取可能的路径

Question

我有一个简单的数据结构，显示有向图中的节点:

{
    'node1': [('V1', 'R1')],
    'node2': [('R1', 'R2'), ('R1', 'R3')],
    'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')],
    'node4': [('R4', 'Z1')],
    'node5': [('R5', 'Z1')]
}

我想获取从 V1 到 Z 的所有可能(有向)路径。例如，路径可能是:

[
    ('V1', 'R1'),
    ('R1', 'R2'),
    ('R2', 'R4'),
    ('R4', 'Z1')
]

然而，我在看似基本的算法上遇到了麻烦，我认为它涉及递归。

for node, connections in nodes.items():
    for connection in connections:

我从上面的方法开始，但我认为这是错误的方法。如果不使用像 itertools 这样的东西，建议的方法是什么？

Answer 1

鉴于数据结构中的元组是边，元组中的值是图的节点，因此可以以一种使算法更简单的方式重新组织数据:

graph = [edge for es in source.values() for edge in es]

由于图中可能存在循环，因此我们需要跟踪已经访问过的节点。考虑到这一点的递归函数，查找从起始节点到结束节点的所有路径，将图作为从节点到节点的边列表:

def find_path(start, end, edges, visited=None):
    if visited is None:
        visited = []
    for n1, n2, in edges:
        if n1 == start:
            if n2 == end:
                yield [n1, n2]
            elif n2 not in visited:
                for continuation in find_path(n2, end, edges, visited + [n1]):
                    yield [n1] + continuation

整个事情:

source = {
    'node1': [('V1', 'R1')],
    'node2': [('R1', 'R2'), ('R1', 'R3')],
    'node3': [('R2', 'R4'), ('R2', 'R5'), ('R3', 'R4'), ('R3', 'R5')],
    'node4': [('R4', 'Z1')],
    'node5': [('R5', 'Z1')]
}

graph = [edge for es in source.values() for edge in es]


def find_path(start, end, edges, visited=None):
    if visited is None:
        visited = []
    for n1, n2, in edges:
        if n1 == start:
            if n2 == end:
                yield [n1, n2]
            elif n2 not in visited:
                for continuation in find_path(n2, end, edges, visited + [n1]):
                    yield [n1] + continuation


print(list(find_path('V1', 'Z1', graph)))

输出:

[['V1', 'R1', 'R2', 'R4', 'Z1'], ['V1', 'R1', 'R2', 'R5', 'Z1'], ['V1', 'R1', 'R3', 'R4', 'Z1'], ['V1', 'R1', 'R3', 'R5', 'Z1']]

请注意，结果被转换为列表，因为该函数是一个生成器，它一次产生一个解决方案。对 list() 的调用将所有结果收集到一个输出中。