Python-program til Breadth First Search eller BFS for en graf
Breadth First Traversal (eller søgning) for en graf ligner Breadth First Traversal af et træ (Se metode 2 af dette indlæg ).
Den eneste fangst her er, at i modsætning til træer kan grafer indeholde cyklusser, så vi kan komme til den samme knude igen. For at undgå at behandle en node mere end én gang, bruger vi et boolesk besøgt array. For nemheds skyld antages det, at alle toppunkter er tilgængelige fra startpunktet. For eksempel, i den følgende graf, starter vi traversering fra toppunkt 2. Når vi kommer til toppunkt 0, leder vi efter alle tilstødende toppunkter af det. 2 er også et tilstødende toppunkt på 0. Hvis vi ikke markerer besøgte toppunkter, vil 2 blive behandlet igen, og det bliver en ikke-afsluttende proces. En Breadth First Traversal af følgende graf er 2, 0, 3, 1. 
Følgende er implementeringerne af simpel Breadth First Traversal fra en given kilde.
Implementeringen bruger tilgrænsende listerepræsentation af grafer. STL 's listebeholder bruges til at gemme lister over tilstødende noder og kø af noder, der er nødvendige for BFS-gennemgang.
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 Produktion
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1
Tidskompleksitet: O(V+E), hvor V er antallet af hjørner i grafen, og E er antallet af kanter
Hjælpeplads: O(V)
Se venligst hele artiklen vedr Breadth First Search eller BFS for en graf for flere detaljer!
