BFS udforsker en graf niveau for niveau og besøger alle naboer til en knude før man går dybere. Den bruger en kø og finder korteste vej (færrest kanter) i uvægtede grafer.
Start ved en kilde, put den i køen, og gentag derefter ved at tage en knude ud af køen, besøge dens ubesøgte naboer og put dem i køen. Et visited sæt forhindrer genbezøg.
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']
Brug BFS til korteste vej i uvægtede grafer, niveau-ordensgennemgang og at finde tilsluttede komponenter. Den bruger mere hukommelse end DFS (en hel grænse på én gang). Spor altid visited, ellers kan du ende i en uendelig løkke på cyklusser.
BFS er algoritmen for korteste stier, når hver kant tæller ligeligt — routing, web crawling, grader af adskillelse i sociale netværk.
Dens købaserede, niveau-for-niveau-struktur er et grundlæggende gennemgangssmønster.
At kende BFS vs DFS giver dig mulighed for at vælge det rigtige værktøj til tilgængeligheds-, vej- og ordningsproblemer.