BFS in den Knoten eines Graphen

Question

Graph

Ich versuche BFS auf dieser grafischen Darstellung von Knoten 16 Aber mein Code geben fehlerhafte Ausgabe Start auszuführen. Kannst du mir bitte helfen? Vielen Dank.

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) 

Meine Ausgabe ist: Output

Answer 1

Die Ursache des Problems ist, dass Sie die Dinge aus (Beginn) queue während Schleife durch sie zu entfernen. Während der Schleife läuft es voraus, aber da das Element vom Anfang entfernt wird, "schreitet" die Liste in die entgegengesetzte Richtung. Das Endergebnis ist, dass es scheint, um 2 auf einmal zu springen. Hier ein Beispiel:

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 

Ausgabe erzeugt

Answer 2

path sollte ein list sein, nicht set seit set keine Ordnung hat. , die funktionieren sollte:

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)