无论如何我可以显示算法在查找元素时所遵循的路径
Is there anyway I can show the path the algorithm has followed in finding the element
我是 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']
我不完全确定你的代码做了什么,但对于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)
如果你的逻辑是这样的话,你显然可以使用不同的参数,但这是我会使用的一般结构。
我认为您对 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
我是 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']
我不完全确定你的代码做了什么,但对于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)
如果你的逻辑是这样的话,你显然可以使用不同的参数,但这是我会使用的一般结构。
我认为您对 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