BFS, bir grafı seviye seviye keşfeder, bir düğümün tüm komşularını ziyaret ettikten sonra daha derinlere gider. Bir kuyruk kullanır ve ağırlıksız graflarda en kısa yolu (en az kenar) bulur.
Bir kaynaktan başlayın, kuyrukta tutun, ardından tekrarlayarak bir düğümü çıkarın, ziyaret edilmemiş komşularını ziyaret edin ve kuyrukta tutun. visited seti yeniden ziyareti engeller.
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']
ağırlıksız graflarda en kısa yol, seviye sırası geçişi ve bağlı bileşenleri bulmak için BFS kullanın. DFS'den daha fazla bellek kullanır (tüm sınır aynı anda). Her zaman visited izleyin veya döngülerde sonsuz döngüye girebilirsiniz.
BFS, her kenarın eşit değerli olduğu en kısa yollar için algoritmadır — yönlendirme, web taraması, sosyal ağ ayırma dereceleri.
Kuyruk tabanlı, seviye seviye yapısı temel bir geçiş desenidir.
BFS ve DFS bilgisi, ulaşılabilirlik, yollar ve sıralama sorunları için doğru aracı seçmenizi sağlar.