Breitendurchlauf (oder Suche) für ein Diagramm ähnelt der Breiten-ersten-Durchquerung eines Baums (siehe Methode 2 von dieser Beitrag ).
Der einzige Haken hier ist, dass Graphen im Gegensatz zu Bäumen Zyklen enthalten können, sodass wir möglicherweise wieder zum selben Knoten gelangen. Um zu vermeiden, dass ein Knoten mehr als einmal verarbeitet wird, verwenden wir ein boolesches besuchtes Array. Der Einfachheit halber wird angenommen, dass alle Scheitelpunkte vom Startscheitelpunkt aus erreichbar sind. Im folgenden Diagramm beginnen wir beispielsweise mit der Durchquerung von Scheitelpunkt 2. Wenn wir Scheitelpunkt 0 erreichen, suchen wir nach allen angrenzenden Scheitelpunkten. 2 ist auch ein angrenzender Scheitelpunkt von 0. Wenn wir besuchte Scheitelpunkte nicht markieren, wird 2 erneut verarbeitet und es wird zu einem nicht terminierenden Prozess. Ein Breitendurchlauf des folgenden Diagramms ist 2, 0, 3, 1. 
Empfohlen: Bitte lösen Sie es auf ÜBEN zuerst, bevor wir zur Lösung übergehen.
Im Folgenden sind die Implementierungen des einfachen Breadth First Traversal aus einer bestimmten Quelle aufgeführt.
Die Implementierung verwendet Darstellung der Adjazenzliste von Grafiken. STL 'S Listencontainer wird zum Speichern von Listen benachbarter Knoten und einer Warteschlange von Knoten verwendet, die für die BFS-Durchquerung benötigt werden.
Python # Python3 Program to print BFS traversal # from a given source vertex. BFS(int s) # traverses vertices reachable from s. from collections import defaultdict # This class represents a directed graph # using adjacency list representation class Graph: # Constructor def __init__(self): # Default dictionary to store graph self.graph = defaultdict(list) # Function to add an edge to graph def addEdge(self, u, v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): # Mark all the vertices as not visited visited = [False] * (max(self.graph) + 1) # Create a queue for BFS queue = [] # Mark the source node as # visited and enqueue it queue.append(s) visited[s] = True while queue: # Dequeue a vertex from # queue and print it s = queue.pop(0) print(s, end=' ') # Get all adjacent vertices of the # dequeued vertex s. # If an adjacent has not been visited, # then mark it visited and enqueue it for i in self.graph[s]: if not visited[i]: queue.append(i) visited[i] = True # Driver code if __name__ == '__main__': # Create a graph given in # the above diagram g = Graph() g.addEdge(0, 1) g.addEdge(0, 2) g.addEdge(1, 2) g.addEdge(2, 0) g.addEdge(2, 3) g.addEdge(3, 3) print('Following is Breadth First Traversal' ' (starting from vertex 2)') g.BFS(2) # This code is contributed by Neelam Yadav # This code is modified by Susobhan Akhuli> Ausgabe
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Zeitkomplexität: O(V+E), wobei V die Anzahl der Eckpunkte im Diagramm und E die Anzahl der Kanten ist
Hilfsraum: O(V)
Den vollständigen Artikel finden Sie unter Breitensuche oder BFS für ein Diagramm für mehr Details!