Python Implementieren Breitensuche

Question

Ich habe ein Online-Beispiel gefunden, jedoch ist nur die Reihenfolge der BFS-Elemente nicht ausreichend für die Berechnung. Nehmen wir an, die Wurzel ist die erste Ebene des BFS-Baums, dann sind die Kinder die zweite Ebene usw. Wie kann ich wissen, in welcher Ebene sie sich befinden und wer der Elternteil jedes Knotens ist (ich werde ein Objekt erstellen) um seine Eltern- und Baumebene zu speichern)?

# sample graph implemented as a dictionary 
graph = {'A': ['B', 'C', 'E'], 
     'B': ['A','D', 'E'], 
     'C': ['A', 'F', 'G'], 
     'D': ['B'], 
     'E': ['A', 'B','D'], 
     'F': ['C'], 
     'G': ['C']} 

# visits all the nodes of a graph (connected component) using BFS 
def bfs_connected_component(graph, start): 
    # keep track of all visited nodes 
    explored = [] 
    # keep track of nodes to be checked 
    queue = [start] 

    # keep looping until there are nodes still to be checked 
    while queue: 
     # pop shallowest node (first node) from queue 
     node = queue.pop(0) 
     if node not in explored: 
      # add node to list of checked nodes 
      explored.append(node) 
      neighbours = graph[node] 

      # add neighbours of node to queue 
      for neighbour in neighbours: 
       queue.append(neighbour) 
    return explored 

bfs_connected_component(graph,'A') # returns ['A', 'B', 'C', 'E', 'D', 'F', 'G'] 

Answer 1

Sie können die Ebenen jedes Knotens verfolgen, indem Sie dem Startknoten zuerst die Ebene 0 zuweisen. Dann für jeden Nachbarn des Knotens X Ebene level_of_X + 1 zuweisen.

Außerdem schiebt Ihr Code den gleichen Knoten mehrmals in die Warteschlange. Ich habe eine separate Liste visited verwendet, um das zu vermeiden.

# sample graph implemented as a dictionary 
graph = {'A': ['B', 'C', 'E'], 
     'B': ['A','D', 'E'], 
     'C': ['A', 'F', 'G'], 
     'D': ['B'], 
     'E': ['A', 'B','D'], 
     'F': ['C'], 
     'G': ['C']} 


# visits all the nodes of a graph (connected component) using BFS 
def bfs_connected_component(graph, start): 
    # keep track of all visited nodes 
    explored = [] 
    # keep track of nodes to be checked 
    queue = [start] 

    levels = {}   # this dict keeps track of levels 
    levels[start]= 0 # depth of start node is 0 

    visited= [start]  # to avoid inserting the same node twice into the queue 

    # keep looping until there are nodes still to be checked 
    while queue: 
     # pop shallowest node (first node) from queue 
     node = queue.pop(0) 
     explored.append(node) 
     neighbours = graph[node] 

     # add neighbours of node to queue 
     for neighbour in neighbours: 
      if neighbour not in visited: 
       queue.append(neighbour) 
       visited.append(neighbour) 

       levels[neighbour]= levels[node]+1 
       # print(neighbour, ">>", levels[neighbour]) 

    print(levels) 

    return explored 

ans = bfs_connected_component(graph,'A') # returns ['A', 'B', 'C', 'E', 'D', 'F', 'G'] 
print(ans) 

Answer 2

Ja, dieser Code besucht nur die Knoten in einer Breite-zuerst-Weise. Dies ist selbst für viele Anwendungen nützlich (z. B. Suchen nach kürzesten Pfaden in einem ungewichteten Graphen).

Um den BFS-Baum tatsächlich zurückzugeben, wären zusätzliche Arbeiten erforderlich. Sie können darüber nachdenken, entweder eine Liste von Kindern für jeden Knoten zu speichern oder Paare von (Knoten, Elternknoten) zurückzugeben. Jede Darstellung sollte Ihnen erlauben, die Struktur des Baumes herauszufinden.

Eine andere Sache, die hier zu beachten ist, ist, dass der Code Python-Listen als eine Warteschlange verwendet, was keine gute Idee ist. Das Entfernen des ersten Elements aus einer Liste erfordert O (n) Zeit.