时间戳

首页 > 解决方案 > 列表列表之间的最短路径

python - 列表列表之间的最短路径

问题描述

假设我有一个这样的列表：

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

我想编写可以找到从1到的最短路径的代码7，在这种情况下，它将是1 -> 3 -> 7。

这是我到目前为止所拥有的：

start = 1
lst = [[1, [2, 3]], [2, [4, 5]], [4, [6, 7]], [3, [7]]]

def getIt(start):
    for nest in lst:
        if start == lst[0]:
            return(nest[1])

allLists = []
loopCleaner = []
def travel(paths, totalList):
    if paths is not None:
        if 7 in paths:
            allLists.append(totalList)
        else:
            for path in paths:
                if path not in loopCleaner:
                    loopCleaner.append(path)
                    totalList.append(path)
                    travel(getIt(path), totalList)

print(travel(lst, []))

我正在通过递归和循环的混合来尝试这个，但它要么输出太长的路径，要么只是没有输出。

我的逻辑： 获取所有可能的嵌套列表getIt。

然后通过递归遍历这些并在它下降时继续添加到总列表，直到在其中一个路径中找到 7。在这种情况下，我们结束并退出。我如何以一种简单的方式编码[1, 3, 7]？

标签： pythonloopsrecursion

解决方案

您可以将递归与生成器一起使用：

def paths(d, start, end, c = [], seen=[]):
  if end in d.get(start, []):
     yield c+[end]
  else:
     for i in filter(lambda x:x not in seen, d.get(start, [])):
        yield from paths(d, i, end, c = c+[i], seen=seen+[i])

data = [[1, [2, 3]], [2, [4, 5]], [4, [6, 7]], [3, [7]]]
print(min(list(paths(dict(data), 1, 7, c=[1])), key=len))

输出：

[1, 3, 7]

推荐阅读