Prima traversata in ampiezza (o ricerca) per un grafico è simile al Breadth First Traversal di un albero (Vedi metodo 2 di questo post ).
L'unico problema qui è che, a differenza degli alberi, i grafici possono contenere cicli, quindi potremmo ritrovarci di nuovo sullo stesso nodo. Per evitare di elaborare un nodo più di una volta, utilizziamo un array visitato booleano. Per semplicità si assume che tutti i vertici siano raggiungibili dal vertice iniziale. Ad esempio, nel grafico seguente, iniziamo l'attraversamento dal vertice 2. Quando arriviamo al vertice 0, cerchiamo tutti i suoi vertici adiacenti. 2 è anche un vertice adiacente di 0. Se non contrassegniamo i vertici visitati, 2 verrà elaborato nuovamente e diventerà un processo non terminato. Una traversata in ampiezza del grafico seguente è 2, 0, 3, 1. 
Di seguito sono riportate le implementazioni del semplice Breadth First Traversal da una determinata fonte.
L'implementazione utilizza Rappresentazione della lista di adiacenza di grafici. STL 'S contenitore dell'elenco viene utilizzato per memorizzare elenchi di nodi adiacenti e code di nodi necessari per l'attraversamento BFS.
Pitone # 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> Produzione
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Complessità temporale: O(V+E), dove V è il numero di vertici nel grafico ed E è il numero di spigoli
Spazio ausiliario: O(V)
stringa Java su int
Si prega di fare riferimento all'articolo completo su Ricerca in ampiezza o BFS per un grafico per ulteriori dettagli!