Traversée en largeur (ou recherche) pour un graphique est similaire à la traversée en largeur d'un arbre (voir méthode 2 de ce post ).

Le seul problème ici est que contrairement aux arbres, les graphiques peuvent contenir des cycles, nous pouvons donc revenir au même nœud. Pour éviter de traiter un nœud plus d'une fois, nous utilisons un tableau booléen visité. Pour simplifier, on suppose que tous les sommets sont accessibles à partir du sommet de départ. Par exemple, dans le graphique suivant, nous commençons le parcours à partir du sommet 2. Lorsque nous arrivons au sommet 0, nous recherchons tous les sommets adjacents de celui-ci. 2 est également un sommet adjacent de 0. Si nous ne marquons pas les sommets visités, alors 2 sera à nouveau traité et deviendra un processus sans fin. Un premier parcours en largeur du graphique suivant est 2, 0, 3, 1.

Voici les implémentations du simple Breadth First Traversal à partir d’une source donnée.

La mise en œuvre utilise représentation de liste de contiguïté de graphiques. STL 's conteneur de liste est utilisé pour stocker les listes de nœuds adjacents et la file d'attente de nœuds nécessaires à la traversée BFS.

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

Complexité temporelle : O(V+E), où V est le nombre de sommets du graphe et E est le nombre d'arêtes
Espace auxiliaire : O(V)

Veuillez vous référer à l'article complet sur Recherche en largeur d'abord ou BFS pour un graphique pour plus de détails!