BFS explorează un graf nivel după nivel, vizitând toți vecinii unui nod înainte de a merge mai adânc. Folosește o coadă și găsește calea cea mai scurtă (cele mai puține muchii) în grafuri neponderate.
Porniți dintr-o sursă, adăugați-o în coadă, apoi în mod repetat scoateți un nod din coadă, vizitați vecinii lui nevizitați și adăugați-i în coadă. Un set visited previne revizitarea.
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']
Folosiți BFS pentru calea cea mai scurtă în grafuri neponderate, traversare în ordine de nivel și găsirea componentelor conectate. Folosește mai multă memorie decât DFS (toată granița deodată). Urmăriți întotdeauna visited sau s-ar putea să intrati într-o buclă infinită pe cicluri.
BFS este algoritmul pentru cele mai scurte căi când fiecare muchie contează la fel — rutare, web crawling, grade de separare în rețele sociale.
Structura sa bazată pe coadă, nivel după nivel, este un model fundamental de traversare.
Cunoașterea BFS versus DFS vă permite să alegeți instrumentul potrivit pentru problemele de accesibilitate, căi și ordonare.
O bibliotecă de întrebări de interviu IT cu răspunsuri detaliate — de la Junior la Senior.
Donează