列表间最短路径

Question

假设我有这样一个列表：

[
[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]？你知道吗

Answer 1

可以对生成器使用递归：

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]