BFS raziskuje graf po nivojih in obišče vse sosede vozlišča, preden se premakne globlje. Uporablja vrsto in najde najkrajšo pot (najmanj robov) v neuteženih grafih.
Začnite pri izvoru, ga vstavite v vrsto, nato ponavljajoče odstranjujete vozlišče, obiščite njegova neobjiskana sosednja vozlišča in jih vstavite v vrsto. Množica visited prepreči ponovno obiskovanje.
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']
Uporabite BFS za najkrajšo pot v neuteženih grafih, obhod po nivojih in iskanje povezanih komponent. Porabi več pomnilnika kot DFS (celo obrobje naenkrat). Vedno sledite visited, sicer se lahko zanke na ciklih.
BFS je algoritem za najkrajše poti, kadar ima vsak rob enako težo — usmerjevanje, spletno grajenje, stopnje ločenosti v družbenih omrežjih.
Njena struktura na osnovi vrste in po nivojih je temeljni vzorec prečkovanja.
Vedenje BFS proti DFS vam omogoči, da izberete pravo orodje za dosegljivost, poti in probleme urejevanja.