查找未排序数据的路径

Question

我有这个数据：

data = [
    {"start": "MIA", "end": "FCA"},
    {"start": "FCA", "end": "GVK"},
    {"start": "GVK", "end": "LSD"}
]

根据这些数据，我需要找到一条路径。在上述情况下，路径将从 MIA 到 FCA，然后是 FCA 到 GVK，最后是 GVK 到 LSD。路径永远不会有分支，它永远不会回到它已经通过的点，没有循环。作为输出，我只需要获取 data 数组每个元素的 "end" 点：["FCA", "GVK", "LSD"]

所以，这就是我尝试过的方法：

def find_path(connections, counter, data):
    if connections[-1] == data[counter]["start"]:
        connections.append(data[counter]["end"])
        if len(connections) == len(data):
            return connections
    return find_path(connections, counter+1, data)

之所以有效，是因为 data 已排序。但是当我像这样更改 data 时：

data = [
    {"start": "FCA", "end": "GVK"},
    {"start": "MIA", "end": "FCA"},
    {"start": "GVK", "end": "LSD"}
]

失败了。

问题：实现此目的的巧妙方法是什么？

我想过在函数到达数据末尾时重置函数顶部的counter：counter = 0 if counter == len(data) else counter，但是这样我就得打折在connections 此处的索引：if connections[-1] == data[counter]["start"]: 并在此处的不同位置追加 data 元素：connections.append(data[counter]["end"])。我觉得有点乱。

Answer 1

以下递归函数将完成这项工作：

data = [
    {"start": "FCA", "end": "GVK"},
    {"start": "MIA", "end": "FCA"},
    {"start": "GVK", "end": "LSD"}
]

def find_path(data, start='', result=[]):
    l = data.copy()
    for d in data:
        if d['start'] == start:
            result.append(d['end'])
            l.remove(d)
            find_path(l, result[-1], result)
    return result

print(find_path(data, 'MIA'))

输出：

['FCA', 'GVK', 'LSD']

查找未排序数据的路径

Find path with unsorted data

python

algorithm

graph-algorithm