BFS verkent een graaf niveau voor niveau en bezoekt alle buren van een knooppunt voordat het dieper gaat. Het gebruikt een queue en vindt het kortste pad (minste randen) in ongewogen grafen.
Start op een bron, zet het in de queue, dequeue vervolgens herhaaldelijk een knooppunt, bezoek zijn onbezochte buren, en zet ze in de queue. Een visited set voorkomt herbezoek.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft() # FIFO: explore nearest first
order.append(node)
for nbr in graph[node]:
if nbr not in visited:
visited.add(nbr)
queue.append(nbr)
return order
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A') # -> ['A', 'B', 'C', 'D']
Gebruik BFS voor kortste pad in ongewogen grafen, level-order traversal en het vinden van verbonden componenten. Het gebruikt meer geheugen dan DFS (een hele grens tegelijk). Volg altijd visited of je kan voor altijd in een lus komen op cycli.
BFS is het algoritme voor kortste paden wanneer elke rand evenveel telt — routing, web crawling, social-network degrees of separation.
De queue-gebaseerde, level-voor-level structuur is een fundamenteel traversalpatroon.
Het kennen van BFS versus DFS stelt je in staat het juiste gereedschap te kiezen voor bereikbaarheid, paden en ordeproblemen.