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

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]