Python programma pirmā platuma meklēšanai vai BFS grafikam
Platuma pirmā šķērsošana (vai meklēšana) jo grafiks ir līdzīgs koka platuma šķērsošanai vispirms (skatiet 2. metodi no šo ziņu ).
Vienīgais āķis šeit ir tas, ka atšķirībā no kokiem grafikos var būt cikli, tāpēc mēs varam atkal nonākt tajā pašā mezglā. Lai izvairītos no mezgla apstrādes vairāk nekā vienu reizi, mēs izmantojam Būla apmeklēto masīvu. Vienkāršības labad tiek pieņemts, ka visas virsotnes ir sasniedzamas no sākuma virsotnes. Piemēram, nākamajā grafikā mēs sākam šķērsošanu no 2. virsotnes. Kad nonākam līdz virsotnei 0, mēs meklējam visas tai blakus esošās virsotnes. 2 ir arī blakus virsotne ar 0. Ja mēs neatzīmēsim apmeklētās virsotnes, tad 2 tiks apstrādāts vēlreiz, un tas kļūs par procesu, kas nebeidzas. Sekojošā diagrammas pirmā šķērsošana platumā ir 2, 0, 3, 1. 
Tālāk ir norādītas vienkāršas Breadth First Traversal ieviešanas no konkrēta avota.
Īstenošana izmanto blakus saraksta attēlojums no grafikiem. STL 's saraksta konteiners tiek izmantots, lai saglabātu blakus esošo mezglu sarakstus un mezglu rindu, kas nepieciešamas BFS šķērsošanai.
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 Izvade
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1
Laika sarežģītība: O(V+E), kur V ir virsotņu skaits grafā un E ir šķautņu skaits
Palīgtelpa: O(V)
Lūdzu, skatiet pilnu rakstu par Platuma pirmā meklēšana vai BFS diagrammai sīkākai informācijai!
