Prima traversare a lățimii (sau căutare) pentru că un grafic este similar cu lățimea prima traversare a unui arbore (vezi metoda 2 din acest post ).
Singura captură aici este că, spre deosebire de copaci, graficele pot conține cicluri, așa că putem ajunge din nou la același nod. Pentru a evita procesarea unui nod de mai multe ori, folosim o matrice booleană vizitată. Pentru simplitate, se presupune că toate vârfurile sunt accesibile de la vârful de pornire. De exemplu, în graficul următor, începem traversarea de la vârful 2. Când ajungem la vârful 0, căutăm toate vârfurile adiacente ale acestuia. 2 este, de asemenea, un vârf adiacent de 0. Dacă nu marchem vârfurile vizitate, atunci 2 va fi procesat din nou și va deveni un proces care nu se încheie. O primă traversare în lățime a următorului grafic este 2, 0, 3, 1. 
Recomandat: Vă rugăm să rezolvați problema PRACTICĂ mai întâi, înainte de a trece la soluție.
Următoarele sunt implementările simple Breadth First Traversal dintr-o sursă dată.
Implementarea foloseste reprezentarea listei de vecinătate de grafice. STL ’s container de listă este folosit pentru a stoca liste de noduri adiacente și coada de noduri necesare pentru traversarea BFS.
Piton # 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> Ieșire
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Complexitatea timpului: O(V+E), unde V este numărul de vârfuri din grafic și E este numărul de muchii
Spațiu auxiliar: O(V)
Vă rugăm să consultați articolul complet pe Breadth First Search sau BFS pentru un grafic pentru mai multe detalii!