无论如何我可以显示算法在查找元素时所遵循的路径

Question

我是 python 的新手，我正在尝试编写广度优先搜索简单图的代码。我想展示算法如何遍历节点以找到目标节点。即，到达目标节点所遵循的路径。我有最短路径的代码，但我需要帮助编写基本广度优先搜索代码来完成我的任务。请原谅任何菜鸟错误或错误。 python 的任何提示和技巧也将是一个巨大的帮助。谢谢！！

graph = {'A': ['B', 'C'],
         'B': ['D', 'E'],
         'C': ['F', 'G'],
         'D': ['B'],
         'E': ['B'],
         'F': ['C'],
         'G': ['C']}

def BFS(graph, start, end):

    nodes = [[start]]
    explored = []

    while nodes:
        path = nodes.pop(0)
        current = path[-1]
        if current not in explored:
            neighbour = graph[current]
            for neighbour in neighbour:
                new = list(path)
                new.append(neighbour)
                nodes.append(new)
                if neighbour == end:
                    return new
            explored.append(nodes)
        print(explored)
    return "Couldn't Find"
BFS(graph,'A','F')

此示例的预期输出应为 ['A','B'],['A','C'],['A','C','F'] 我得到的输出是 ['A','B'],['A','C']

Answer 1

我不完全确定你的代码做了什么，但对于breadth-first搜索，我会这样做：

在您的函数之外，创建一个列表来表示 'path' 算法所遵循的。
将起始元素附加到此列表。
将您的搜索功能的参数之一作为此列表
在函数中，在执行递归调用之前，将调用将检查的元素追加到列表中。

def bfs(cur_node, explored_list):
    ...
    # Logic
    ...
    explored_list.append(next_node)
    bfs(next_node, explored_list)

explored_list = []
explored_list.append(start_node)
bfs(start_node, explored_list)

如果你的逻辑是这样的话，你显然可以使用不同的参数，但这是我会使用的一般结构。

Answer 2

我认为您对 return 和打印感到困惑。请注意，数组是可变的，这意味着更改相关数组会影响其值。如果你想让它们不可变，你需要把 array.copy() when assigning/appending 放到另一个变量

代码是 returning ['A','C','F'] 但是它正在打印 ['A','B'],['A','C'] 如果你想让 return 变成 ['A','B'],['A','C'],['A','C','F'] 你需要记录最后一个循环的节点。这是一个可能的解决方案

def BFS(graph, start, end):

    nodes = [[start]]
    explored = []
    previous_nodes=[]
    count = 0
    while nodes:
        count += 1
        print (count)
        print(f'explored is {explored}')
        print(f'nodes are {nodes}')

        path = nodes.pop(0)
        current = path[-1]
        if current not in explored:
            neighbours = graph[current]
            for neighbour in neighbours:
                new = list(path)
                new.append(neighbour)
                nodes.append(new)
                if neighbour == end:
                    return [previous_nodes,new]
            explored.append(nodes)
            previous_nodes.append(nodes.copy()[0])
        print(explored)
    return "Couldn't Find"
print('return is ',BFS(graph,'A','F'))

请注意，有许多具有数据结构的库可以让您的工作更轻松，例如 numpy 和 pandas

无论如何我可以显示算法在查找元素时所遵循的路径

Is there anyway I can show the path the algorithm has followed in finding the element

python

breadth-first-search