python - 获取可能的路径

问题描述

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

{
    '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？

标签： pythonalgorithmgraph-algorithm

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

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()所有结果收集到单个输出中。

python - 获取可能的路径

问题描述

解决方案

推荐阅读