路径查找程序代码，getitem类型

Question

我想做一个“探路者”

def find_all_paths(start, end, graph, path=[]):
    path = path + [start]
    if start == end:
        return [path]
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(graph, node, end, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths


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

如果我在shell中输入find_all_paths(2,5,graph)，我应该返回从图字典中的键2到5个值的所有路径 正确的结果应该是

path=[[2,5],[2,3,4,5][2,4,5]]

代码不断给出错误值，例如

   for node in graph[start]:
TypeError: 'int' object has no attribute '__getitem__'

有人能帮我把这东西弄起来吗

Answer 1

有几个尴尬和错误：

使用None，而不是用列表初始化path参数。 并在函数体中创建空列表。你知道吗

def find_all_paths(start, end, graph, path=None):
    path = path or []

传递给find_all_paths的值与签名无关。 改为这样写：

newpaths = find_all_paths(node, end, graph, path)

因为值是整数，所以图形必须包含int，而不是strings。你知道吗

graph = {1: [2], 2: [3, 4, 5], 3: [4], 4: [5, 6], 5: [], 6: []}

以下是代码的固定版本：

def find_all_paths(start, end, graph, path=None):
    path = path or []
    path.append(start)
    if start == end:
        return [path]
    paths = []
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_paths(node, end, graph, path)
            for newpath in newpaths:
                paths.append(newpath)
    return paths

如果您尝试这样做：

graph = {1: [2], 2: [3, 4, 5], 3: [4], 4: [5, 6], 5: [], 6: []}
print(find_all_paths(2, 5, graph))

您将得到：

[[2, 3, 4, 5, 6]]