Prvi prehod v širino (ali iskanje) za graf je podoben prvemu prehodu drevesa po širini (glejte metodo 2 od ta objava ).
Edina težava tukaj je, da za razliko od dreves lahko grafi vsebujejo cikle, tako da lahko spet pridemo do istega vozlišča. Da bi se izognili večkratni obdelavi vozlišča, uporabimo logično obiskano matriko. Zaradi enostavnosti se predpostavlja, da so vsa oglišča dosegljiva iz začetnega oglišča. Na primer, v naslednjem grafu začnemo prečkanje iz točke 2. Ko pridemo do točke 0, poiščemo vse sosednje točke. 2 je tudi sosednja vozlišča 0. Če ne označimo obiskanih vozlišč, bo 2 ponovno obdelan in bo postal proces brez zaključka. Prvi prehod v širino naslednjega grafa je 2, 0, 3, 1. 
Priporočeno: prosimo, rešite ga na VADITE najprej, preden preidete na rešitev.
Sledijo implementacije preprostega Breadth First Traversal iz danega vira.
Izvedba uporablja predstavitev seznama sosednosti grafov. STL 's vsebnik seznama se uporablja za shranjevanje seznamov sosednjih vozlišč in čakalne vrste vozlišč, potrebnih za prehod BFS.
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> Izhod
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Časovna zapletenost: O(V+E), kjer je V število vozlišč v grafu in E število robov
Pomožni prostor: O(V)
Oglejte si celoten članek Iskanje najprej v širino ali BFS za graf za več podrobnosti!