Breadth First Traversal (eller sökning) för en graf liknar Breadth First Traversal av ett träd (Se metod 2 av den här posten ).
Den enda haken här är att till skillnad från träd kan grafer innehålla cykler, så vi kan komma till samma nod igen. För att undvika att bearbeta en nod mer än en gång använder vi en boolesk besökt array. För enkelhetens skull antas det att alla hörn är nåbara från startpunkten. Till exempel, i följande graf, börjar vi traversering från vertex 2. När vi kommer till vertex 0 letar vi efter alla intilliggande hörn av den. 2 är också en angränsande hörn på 0. Om vi inte markerar besökta hörn, kommer 2 att bearbetas igen och det blir en icke-avslutande process. En Breadth First Traversal av följande graf är 2, 0, 3, 1. 
Rekommenderas: Vänligen lös det ÖVA först innan du går vidare till lösningen.
Följande är implementeringarna av enkel Breadth First Traversal från en given källa.
python rest-operator
Implementeringen använder angränsande listrepresentation av grafer. STL 's listbehållare används för att lagra listor över intilliggande noder och kö av noder som behövs för BFS-traversering.
Pytonorm # 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> Produktion
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Tidskomplexitet: O(V+E), där V är antalet hörn i grafen och E är antalet kanter
Hjälputrymme: O(V)
Se hela artikeln om Breadth First Search eller BFS för en graf för mer detaljer!