BFS menjelajahi grafik level demi level, mengunjungi semua tetangga dari sebuah simpul sebelum bergerak lebih dalam. Ini menggunakan sebuah queue dan menemukan jalur terpendek (paling sedikit sisi) dalam grafik yang tidak berbobot.
Mulai dari sumber, masukkan ke dalam queue, kemudian secara berulang keluarkan simpul, kunjungi tetangga yang belum dikunjungi, dan masukkan mereka. Sebuah set mencegah kunjungan berulang.
visitedfrom 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']
Gunakan BFS untuk jalur terpendek dalam grafik yang tidak berbobot, traversal urutan level, dan menemukan komponen yang terhubung. Ini menggunakan lebih banyak memori daripada DFS (seluruh frontier sekaligus). Selalu lacak visited atau Anda mungkin memasuki loop tak terbatas pada siklus.
BFS adalah algoritma untuk jalur terpendek ketika setiap sisi memiliki bobot yang sama — perutean, web crawling, derajat pemisahan jaringan sosial.
Struktur berbasis queue, level demi level adalah pola traversal fundamental.
Mengetahui BFS vs DFS memungkinkan Anda memilih alat yang tepat untuk masalah jangkauan, jalur, dan pengurutan.