BFS meneroka graf peringkat demi peringkat, mengunjungi semua jiran nod sebelum bergerak lebih dalam. Ia menggunakan baris gilir dan mencari laluan terpendek (tepi paling sedikit) dalam graf tidak berwajaran.
Mulai dari sumber, masukkan ke dalam baris gilir, kemudian berulang kali keluarkan nod, lawati jiran yang belum dikunjungi, dan masukkan mereka. Set visited mencegah lawatan semula.
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']
Gunakan BFS untuk laluan terpendek dalam graf tidak berwajaran, traversal peringkat-tertib, dan mencari komponen bersambung. Menggunakan lebih banyak memori daripada DFS (seluruh sempadan sekaligus). Selalu jejaki visited atau anda mungkin bergelung selamanya pada kitaran.
BFS adalah algoritma untuk laluan terpendek apabila setiap tepi sama pentingnya — penghala, penyusur web, darjah pemisahan rangkaian sosial.
Struktur berasaskan baris gilir dan peringkat-demi-peringkat ialah corak traversal asas.
Mengetahui BFS berbanding DFS membolehkan anda memilih alat yang tepat untuk masalah ketercapaian, laluan, dan susunan.