访问所有节点并将它们添加到路径

Question

我正在尝试访问所有节点，返回到起始节点 (Neamt) 并将访问的节点添加到 path 但问题是如果我到达死胡同，城市将从 path.

这是代码生成的可能 path 中的第一个：

['Neamt', 'Iasi', 'Vaslui', 'Urziceni', 'Bucharest', 'Fagaras', 'Sibiu', 'Oradea', 'Zerind', 'Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Pitesti', 'Rimnicu Vileea']

如上path，没有'Hirsova', 'Eforie', 'Giurgiu'。真正发生的是当我在 PyCharm 上调试时：'Hirsova', 'Eforie', 'Giurgiu' 被添加到 path 但随后它们从 path.

中删除

我想把那些城市倒序加入path。如：

['Neamt', 'Iasi', 'Vaslui', 'Urziceni', 'Hirsova', 'Eforie', 'Hirsova', 'Urziceni', 'Bucharest', 'Giurgiu', 'Bucharest', 'Pitesti', 'Rimnicu Vileea', 'Craiova', 'Drobeta', 'Mehadia', 'Lugoj', 'Timisoara', 'Arad', 'Zerind', 'Oradea', 'Sibiu', 'Fagaras', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt',]

为什么要从 path 中删除它们，因为没有任何与 .append 方法相反的方法，例如 .delete?

def find_paths(node, cities, path, distance):
    # Add way point
    path.append(node)
    #print('path:', path)

# Fork paths for all possible cities not yet used
    for city in cities:
        if (city not in path) and (node in cities[city]):
            find_paths(city, dict(cities), list(path), distance)
#What has to be:
count = 0 # avoid adding end paths twice
    for city in cities[node].keys(): # only recurse on children not the whole list
        if city not in visited: 
            count += 1
            find_paths(city, cities, path, distance, visited)
    if count > 0 : # only add again if there were children
        path.append(node)
#////////////

if __name__ == '__main__':
    cities = {
    'Arad': {'Sibiu': 140, 'Timisoara': 118, 'Zerind': 75},
    'Hirsova': {'Eforie': 86, 'Urziceni': 98},
    'Bucharest': {'Fagaras': 211, 'Giurgiu': 90, 'Pitesti': 101, 'Urziceni': 85},
    'Craiova': {'Drobeta': 120, 'Pitesti': 138, 'Rimnicu Vileea': 146},
    'Drobeta': {'Craiova': 120, 'Mehadia': 75},
    'Eforie': {'Hirsova': 86},
    'Fagaras': {'Bucharest': 211, 'Sibiu': 99},
    'Giurgiu': {'Bucharest': 90},
    'Iasi': {'Neamt': 87, 'Vaslui': 92},
    'Lugoj': {'Mehadia': 70, 'Timisoara': 111},
    'Mehadia': {'Drobeta': 75, 'Lugoj': 70},
    'Neamt': {'Iasi': 87},
    'Oradea': {'Sibiu': 151, 'Zerind': 71},
    'Pitesti': {'Bucharest': 101, 'Craiova': 138, 'Rimnicu Vileea': 97},
    'Rimnicu Vileea': {'Craiova': 146, 'Pitesti': 97, 'Sibiu': 80},
    'Sibiu': {'Arad': 140, 'Fagaras': 99, 'Oradea': 151, 'Rimnicu Vileea': 80},
    'Timisoara': {'Arad': 118, 'Lugoj': 111},
    'Urziceni': {'Bucharest': 85, 'Hirsova': 98, 'Vaslui': 142},
    'Vaslui': {'Iasi': 92, 'Urziceni': 142},
    'Zerind': {'Arad': 75, 'Oradea': 71}
    }

    #print("Start: Neamt")
    find_paths('Neamt', cities, [], 0)

Answer 1

没有任何内容被删除，您只是看到 find_paths 的不同帧具有不同的 path 值。 list(path) 制作副本，以便每个函数调用都收到自己的列表，一旦函数调用结束并且您移回递归堆栈，您会看到 path 的旧值没有附加节点它。

Answer 2

您只需在进入递归之前和之后进行 depth-first 搜索和添加节点。这会在您开始路径时将名称放在列表中，然后在递归展开时再次返回。过程是：

添加城市
在 children 上递归（如果 child 未被访问）
再次添加城市（如果不是路径的终点）

您需要添加路径终点检查，这样您就不会连续两次添加 Eforie 等城市。如果一个城市没有未去过的children，你就不要再添加了。为此，只需跟踪递归计数即可。

类似于：

def find_paths(node, cities, path, distance, visited = set()):

    visited.add(node) # keep track of visited nodes
    path.append(node)

    # Fork paths for all possible cities not yet used
    count = 0 # avoid adding end paths twice
    for city in cities[node].keys(): # only recurse on children not the whole list
        if city not in visited: 
            count += 1
            find_paths(city, cities, path, distance, visited)
    if count > 0 : # only add again if there were children
        path.append(node)

a = []
find_paths('Neamt', cities, a, 0)
print(a)

结果

['Neamt', 'Iasi', 'Vaslui', 'Urziceni', 'Bucharest', 'Fagaras', 'Sibiu', 'Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Pitesti', 'Rimnicu Vileea', 'Pitesti', 'Craiova', 'Drobeta', 'Mehadia', 'Lugoj', 'Timisoara', 'Zerind', 'Oradea', 'Zerind', 'Arad', 'Sibiu', 'Fagaras', 'Giurgiu', 'Bucharest', 'Hirsova', 'Eforie', 'Hirsova', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt']

访问所有节点并将它们添加到路径

Visiting All Nodes and Adding Them to Path

python

algorithm

graph-algorithm