queue.get() не удаляет элемент из очереди

Question

Я недавно начал программировать на Python (3.5), и я пытаюсь решить простую широтой первую задачу поиска в Python (см код)

import queue 
import networkx as nx 


def bfs(graph, start, target): 
    frontier = queue.Queue() 
    frontier.put(start) 
    explored = list() 

while not frontier.empty(): 
    state = frontier.get() 
    explored.append(state) 
    print(explored) 

    if state == target: 
     return 'success' 

    print(graph.neighbors(state)) 

    for neighbor in graph.neighbors(state): 
     if neighbor not in explored: 
      frontier.put(state) 

return 'Failure to find path' 

код возвращает бесконечный цикл, где кажется, что frontier.get() не удаляет элемент из очереди. Это делает цикл while бесконечным, поскольку первое значение в очереди всегда является начальным узлом, определенным в входе функции. Состояние переменной в каждом цикле равно одному (всегда начальный узел).

Что я делаю неправильно? Как я понял, очередь должна переместиться от стартового узла к соседям стартового узла, и поэтому цикл не должен возникать.

Answer 1

Две вещи. Во-первых, я предполагаю, что все, начиная с while, должно быть отступом на одном уровне.

Если я правильно читаю ваш алгоритм, я считаю, что ошибка находится на последней строке перед возвратом. У вас есть:

frontier.put(state) 

который просто вставляет узел, на который вы уже смотрели. Я думаю, что вы должны делать вместо этого:

frontier.put(neighbor) 

так, что вы исследуете все непосредственные соседи state. В противном случае вы просто продолжаете смотреть на начальный узел снова и снова.

Answer 2

Потому что вы снова положили значение state в очередь. Изменить это:

for neighbor in graph.neighbors(state): 
    if neighbor not in explored: 
     frontier.put(state) # Here you put the 'state' back! 

к этому:

for neighbor in graph.neighbors(state): 
    if neighbor not in explored: 
     frontier.put(neighbor) # Put in the neighbours instead.