BFS в узлах графа

Question

Graph

Я пытаюсь выполнить BFS на этом графике, начиная с узла 16. Но мой код дает ошибочный вывод. Не могли бы вы помочь мне. Благодарю.

visited_nodes = set() 
queue = [16] 
pardaught = dict() 
exclu = list() 
path = set() 
for node in queue: 
    path.add(node) 
    neighbors = G.neighbors(node) 
    visited_nodes.add(node) 
    queue.remove(node) 
    queue.extend([n for n in neighbors if n not in visited_nodes]) 

newG = G.subgraph(path) 
nx.draw(newG, with_labels=True) 

Мой вывод: Output

Answer 1

Причиной вашей проблемы является то, что вы удаляете вещи из (начало) queue в то время как цикл через него. По мере того, как он заставляет его двигаться вперед, но поскольку элемент удален с самого начала, список «шагает» один в противоположном направлении. Конечным результатом является то, что он, кажется, прыгает 2 за раз. Вот пример:

integer_list = [1,2,3] 
next_int = 4 
for integer in integer_list: 
    print integer 
    integer_list.remove(integer) 
    integer_list.append(next_int) 
    next_int += 1 

производит вывод

Answer 2

path должен быть list, не setset, поскольку не имеет никакого порядка. Это должно работать:

visited_nodes = set() 
path = [] 
queue = [16] 

while queue: 
    node = queue.pop(0) 
    visited_nodes.add(node) 
    path.append(node) 

    for neighbor in G.neighbors(node): 
     if neighbor in visited_nodes: 
      continue 
     queue.append(neighbor)