BFS utforsker en graf nivå for nivå, og besøker alle naboer til en node før det går dypere. Det bruker en kø og finner den korteste stien (færrest kanter) i uvektede grafer.
Start ved en kilde, sett den inn i køen, fjern deretter gjentatte ganger en node fra køen, besøk dens ubesøkte naboer, og sett dem inn i køen. Et visited sett forhindrer gjenbesøk.
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']
Bruk BFS for korteste sti i uvektede grafer, nivårekkefølge-traversal og finne sammenkoblede komponenter. Det bruker mer minne enn DFS (hele grensen på en gang). Spor alltid visited eller du kan gå i uendelig løkke på sykler.
BFS er algoritmen for korteste stier når hver kant teller like mye — ruting, web crawling, social-network degrees of separation.
Its købaserte, nivå-for-nivå struktur er et grunnleggende traversal-mønster.
Å kjenne BFS kontra DFS lar deg velge rett verktøy for rekkevidde, stier og ordningsproblemer.
Et bibliotek av IT-intervjuspørsmål med detaljerte svar — fra Junior til Senior.
Doner