BFS eksploruje graf poziom za poziomem, odwiedzając wszystkich sąsiadów węzła przed pójściem głębiej. Używa kolejki i znajduje najkrótszą ścieżkę (najmniej krawędzi) w grafach nieważonych.
Zacznij od źródła, umieść je w kolejce, następnie wielokrotnie usuń węzeł z kolejki, odwiedź jego nieodwiedzone sąsiedztwa i umieść je w kolejce. Zbiór visited zapobiega ponownemu odwiedzeniu.
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żywaj BFS do najkrótszej ścieżki w grafach nieważonych, przechodzenia w porządku poziomów i znajdowania połączonych komponentów. Zużywa więcej pamięci niż DFS (cała granica naraz). Zawsze śledź visited lub możesz wejść w nieskończoną pętlę na cyklach.
BFS to algorytm do najkrótszych ścieżek, gdy każda krawędź liczy się równo — routing, web crawling, stopnie separacji sieci społecznej.
Jego struktura oparta na kolejce, poziom po poziomie, jest podstawowym wzorem przechodzenia.
Znajomość BFS kontra DFS pozwala wybrać odpowiednie narzędzie do problemów osiągalności, ścieżek i porządkowania.
Biblioteka pytań rekrutacyjnych IT ze szczegółowymi odpowiedziami — od Juniora do Seniora.
Wesprzyj