BFS inachunguza grafu kwa kila kiwango, inakaribisha majibu yote ya nodi kabla ya kusonga zaidi. Inatumia foleni na kupata njia fupi zaidi (kingo inacho chache) katika grafu bila uzani.
Anza kwa chanzo, ingiza katika foleni, kisha kurudia kwa kuondoa nodi, kutembelea majibu yake ambayo hayajatembelewa, na kuingiza katika foleni. Seti ya visited inazuia kutembelea tena.
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']
Tumia BFS kwa njia fupi zaidi katika grafu bila uzani, kumngata kwa kiwango, na kutafuta sehemu zilizounganishwa. Inatumia kumbukumbu zaidi kuliko DFS (mzunguko mzima wakati mmoja). Sema kila wakati visited au unaweza kufa katika mzunguko usiotopiana.
BFS ni algoriti ya njia fupi zaidi wakati kila kingo inakisabi kwa usawa — kuzuia njia, kumata wavuti, kiwango cha utengano katika mtandao wa kijamii.
Umbo lake linalotumia foleni na kiwango-kwa-kiwango ni muundo wa kimsingi wa kuvuka.
Kujua BFS dhidi ya DFS hukuruhusu kuchagua zana sahihi kwa upanuzi, njia, na matatizo ya kuagiza.