BFS egy gráfot szintről szintre hajt végig, meglátogatva egy csomópont összes szomszédját, mielőtt mélyebbre haladna. Egy sort használ és megtalálja a legrövidebb utat (legkevesebb él) súlyozatlan gráfokban.
Kezdj egy forrásból, tedd be a sorba, majd ismételten vedd ki a sorból egy csomópontot, látogasd meg annak felkeresetlen szomszédjait, és tedd be őket a sorba. Egy halmaz megakadályozza az újbóli meglátogatást.
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']
Használd a BFS-t a legrövidebb út súlyozatlan gráfban, szint szerinti bejáráshoz és összefüggő komponensek kereséséhez. Több memóriát használ, mint a DFS (egyszerre az egész határt). Mindig követeld nyomon a visited értéket, vagy végtelen ciklusa lehet az éleken.
A BFS az az algoritmus a legrövidebb utakhoz, amikor minden él ugyanannyit ér — útválasztás, webhasználati bejárás, közösségi hálózatok szeparációs fokszáma.
Annak sort alapú, szintről szintre történő szerkezete egy alapvető bejárási minta.
A BFS és DFS ismerete lehetővé teszi, hogy kiválaszd a megfelelő eszközt az elérhetőség, az utak és az rendezési problémákhoz.