BFS utforskar en graf nivå för nivå och besöker alla grannar till en nod innan den går djupare. Den använder en kö och hittar kortaste vägen (minst kanter) i oviktade grafer.
Börja vid en källa, sätt in den i kön, upprepa sedan genom att ta ut en nod, besöka dess obesökta grannar och sätta in dem i kön. En visited-uppsättning förhindrar att man besöker samma nod igen.
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']
Använd BFS för kortaste vägen i oviktade grafer, nivåordning och att hitta sammankopplade komponenter. Det använder mer minne än DFS (hela gränsen på en gång). Spåra alltid visited eller du kan hamna i en oändlig loop på cykler.
BFS är algoritmen för kortaste vägar när varje kant räknas lika — dirigering, webbkrypning, separationsgrader i sociala nätverk.
Dess köbaserade, nivå-för-nivå-struktur är ett grundläggande traverseringsmönster.
Att kunna BFS kontra DFS låter dig välja rätt verktyg för nåbarhet, vägar och sorteringsproblem.