我一直在学习python中的图形算法,我想知道为什么在结果中会得到一个重复的路径。
这是我的密码

from collections import defaultdict

our_graph = defaultdict(list)


def run_graph():
    print('Creating Graph...')
    add_edges("London", "Barcelona")
    add_edges("Barcelona", "Madrid")
    add_edges("Madrid", "Ottawa")
    add_edges("Madrid", "Berlin")
    add_edges("London", "Ottawa")

    print('\nOur Graph:')
    print(our_graph)

    print('\nEdges:')
    print(list_edges())

    print('\nTesting Paths To Invalid Nodes:')
    print(find_all_paths("LDN", "Ottawa"))
    print(find_all_paths("London", "X"))

    print('\nTesting Paths To Valid Nodes:')
    print(find_all_paths("London", "Ottawa"))
    print('---')
    print(find_all_paths("London", "Berlin"))


def add_edges(a, b):
    our_graph[a].append(b)
    our_graph[b].append(a)


def list_edges():
    edges = []
    for node in our_graph:
        for next_node in our_graph[node]:
            edges.append((node, next_node))
    return edges


def find_all_paths(start, end, path=[]):
    # If there isn't a node with that name
    if our_graph[start] == [] or our_graph[end] == []:
        return 'Can\'t find nodes ' + start + " " + end
    else:
        # create a path
        path = path + [start]
        # If start node is the end
        if start == end:
            return [path]
        paths = []
        newpaths = []
        # For each node
        for node in our_graph[start]:
            # If node not already in saved path
            if node not in path:
                # Search the paths of that new node
                newpaths = find_all_paths(node, end, path)
            # Append new path to paths
            for newpath in newpaths:
                paths.append(newpath)
        return paths


if __name__ == '__main__':
    run_graph()

我从print(find_all_paths("London", "Berlin"))得到的结果

[['London', 'Barcelona', 'Madrid', 'Berlin'], ['London', 'Ottawa', 'Madrid', 'Berlin'], ['London', 'Ottawa', 'Madrid', 'Berlin']]

正如你所看到的,伦敦-渥太华-马德里-柏林的路线是重复的。你能解释一下原因吗?

最佳答案

问题在于:

if node not in path:
    # Search the paths of that new node
    newpaths = find_all_paths(node, end, path)
# Append new path to paths
for newpath in newpaths:
    paths.append(newpath)

如果node已经在path中,则将使用旧的newpaths。您只需要在if语句下移动for循环:
if node not in path:
    # Search the paths of that new node
    newpaths = find_all_paths(node, end, path)
    # Append new path to paths
    for newpath in newpaths:
        paths.append(newpath)

或:
if node not in path:
    # Search the paths of that new node
    paths += find_all_paths(node, end, path)

另外,我建议使用defaultdict(set)而不是列表。

08-26 20:23
查看更多