BFS jessplorja graff livell għal livell, biex tqajjem il-ġirien kollha ta' nodu qabel tmur aktar il-fond. Tuża queue u ssib il-iqsar mogħdija (l-inqas ħxuna) f'graffs mingħajr piż.
Ibda minn sors, aggiungi fil-queue, imbagħad irrepeti biex tneħħi nodu, żur il-ġirien li ma ntlaħxux, u aggiunihom. Set ta' visited iffrena l-vżitaturi mill-ġdid.
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']
Uża BFS għal iqsar mogħdija f'graffs mingħajr piż, traversal ta' livell-ordni, u ssib komponenti marbuta. Tuża aktar memorja minn DFS (il-fruntiera kollha f'daqqa). Dejjem segwi visited jew tista' taħbel eternament fuq ċikli.
BFS hija l-algoritmu għal mogħdiji l-iqsar meta kull ħxuna għaddha l-istess - routing, web crawling, gradi ta' separazzjoni tan-network soċjali.
L-istruttura bbażata fuq queue u livell-għal-livell tagħha hija mudell fundamentali ta' traversal.
Il-għarfien ta' BFS vs DFS jippermettilek tagħżel l-għodda t-tajba għal problemi ta' raaġġ, mogħdiji, u ordnar.