Python, рекурсивный ширина первого поиска

Question

Я пытаюсь найти кратчайший путь на сетке (список списков кортежей) Я получил это до сих пор:

def planPath(self, x, y, goal, board): 
    visited = [] 
    path = [] 
    def pathFinder(curr): 
     visited.append(curr) 
     neighbors = None 
     if curr == goal: 
      visited.append(curr) 
      return curr 
     neighbors = [neighbor for neighbor in curr.neighbors if type(neighbor) is not Land.Water and neighbor not in visited] 
     neighbors.sort(key=lambda neighbor: abs(neighbor.location[0] - goal.location[0]) + abs(neighbor.location[1] - goal.location[1]) + abs(neighbor.elevation - goal.elevation), reverse=False) 

х, у текущее местоположение , очевидно, и доска, ну и вся доска. Мысль заключалась в том, что он будет рекурсивным. Для каждого вызова я получал бы соседей для текущего узла, отфильтровывал воду (неравномерно) и посещал. Затем сортируйте ближе к цели. Далее я хочу пройти и сделать первый поиск по ширине. Поэтому я буду расширять всех соседей, затем расширять каждого из своих соседей и так далее. Каждая ветка продолжалась до тех пор, пока у них не будет соседей, они вернут Ничего и сделают это. Тогда конечным результатом является то, что единственным, кто будет возвращаться, станет первый брелок, который достигнет цели, т. Е. Самый короткий. Кто-нибудь знает, как я могу это сделать?

Я думал, это:

for neighbor in neighbors: 
    next = pathFinder(neighbor) 
    if next: 
     visited.append(cure) 
     return curr 
    else: return None 

но, поправьте меня, если я ошибаюсь, но это привело бы к глубине первого поиска, а не вширь.

Answer 1

Следующее является псевдо-кодом, который может помочь вам

BFS(v) 
    let neighbors be the set of all neighbours of vertex v 
    for neighbor in neighbors: 
     if neighbor is not visited: 
      visit neighbour 
    for neighbor in neighbors: 
     recurisvely call BFS(neighbor)