Breedte eerste traversal (of zoeken) voor een grafiek is vergelijkbaar met de breedte van de eerste doorgang van een boom (zie methode 2 van deze post ).

Het enige probleem hier is dat grafieken, in tegenstelling tot bomen, cycli kunnen bevatten, waardoor we mogelijk weer op hetzelfde knooppunt terechtkomen. Om te voorkomen dat een knooppunt meerdere keren wordt verwerkt, gebruiken we een Booleaanse bezochte array. Voor de eenvoud wordt aangenomen dat alle hoekpunten bereikbaar zijn vanaf het startpunt. In de volgende grafiek beginnen we bijvoorbeeld vanaf hoekpunt 2. Wanneer we bij hoekpunt 0 komen, zoeken we naar alle aangrenzende hoekpunten ervan. 2 is ook een aangrenzend hoekpunt van 0. Als we de bezochte hoekpunten niet markeren, wordt 2 opnieuw verwerkt en wordt het een niet-beëindigend proces. Een breedte-eerste doorgang van de volgende grafiek is 2, 0, 3, 1.

Hieronder volgen de implementaties van eenvoudige Breadth First Traversal vanuit een bepaalde bron.

De implementatie maakt gebruik van aangrenzende lijst representatie van grafieken. STL 'S lijstcontainer wordt gebruikt om lijsten met aangrenzende knooppunten en een wachtrij met knooppunten op te slaan die nodig zijn voor BFS-traversal.

# 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>

Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>

Tijdcomplexiteit: O(V+E), waarbij V het aantal hoekpunten in de grafiek is en E het aantal randen
Hulpruimte: O(V)

voor loop bash

Raadpleeg het volledige artikel op Breedte eerst zoeken of BFS voor een grafiek voor meer details!