Breadth First Traversal (eller søk) for en graf ligner på Breadth First Traversal av et tre (se metode 2 av denne posten ).
Den eneste fangsten her er at i motsetning til trær, kan grafer inneholde sykluser, så vi kan komme til samme node igjen. For å unngå å behandle en node mer enn én gang, bruker vi en boolsk besøkt matrise. For enkelhets skyld antas det at alle toppunktene er tilgjengelige fra startpunktet. For eksempel, i følgende graf, starter vi traversering fra toppunkt 2. Når vi kommer til toppunkt 0, ser vi etter alle tilstøtende toppunkter av det. 2 er også et tilstøtende toppunkt på 0. Hvis vi ikke merker besøkte toppunkter, vil 2 bli behandlet på nytt og det blir en ikke-avsluttende prosess. En Breadth First Traversal av følgende graf er 2, 0, 3, 1. 
Følgende er implementeringene av enkel Breadth First Traversal fra en gitt kilde.
javascript strengtrim
Implementeringen bruker tilknytningslisterepresentasjon av grafer. STL 's listebeholder brukes til å lagre lister over tilstøtende noder og kø med noder som trengs for BFS-gjennomgang.
de tidlige mukerePython
# 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> Produksjon
Following is Breadth First Traversal (starting from vertex 2) 2 0 3 1>
Tidskompleksitet: O(V+E), der V er antall toppunkter i grafen og E er antall kanter
Hjelpeplass: O(V)
Vennligst se fullstendig artikkel om Breadth First Search eller BFS for en graf for flere detaljer!