BFS prozkoumává graf úroveň po úrovni, navštěvuje všechny sousedy uzlu před tím, než se posune hlouběji. Používá frontu a najde nejkratší cestu (nejméně hran) v neváženných grafech.
Začněte u zdroje, vložte jej do fronty, poté opakovaně odeberte uzel z fronty, navštivte jeho nenavštívené sousedy a vložte je do fronty. Sada visited brání opětovné návštěvě.
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']
Používejte BFS pro nejkratší cestu v neváženných grafech, procházku po úrovních a hledání spojených komponent. Používá více paměti než DFS (celá hranice najednou). Vždy sledujte visited, jinak se můžete dostat do nekonečné smyčky na cyklech.
BFS je algoritmus pro nejkratší cesty, když se každá hrana počítá stejně — směrování, web crawling, stupně oddělení v sociálních sítích.
Její struktura založená na frontě a úroveň za úrovní je základní vzor procházení.
Znalost BFS versus DFS vám umožňuje vybrat správný nástroj pro problémy dosažitelnosti, cest a řazení.