BFS a thairbhéanann graf leibhéal ar leibhéal, ag cuartú a laige ar fad de nód sula n-imíonn sé níos doimhne. Úsáideann sé scuaine agus faightear an conair is gearr (an líon imill is lú) i ngraif gan bhreise.
An smaoineamh
Tosaigh ag foinse, chuir san fhiú ar an scuaine, ansin atair faoi dhéin dí-scuaine nód, cuartaigh a chomhrsheachránaigh neamhthairbhithe, agus cuir an scuaine orthu. Seachann a bhfreagra visited athchuairt.
Sampla
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']
Castacht
- Am: O(V + E) — gach rinn agus imeall uair amháin.
- Spás: O(V) don scuaine agus an tsraith fé bhraistint.
Cathain a úsáid / leithscéal
Bain úsáid as BFS do conair is gearr i ngraif gan bhreise, taiscéalaí leibhéal-ord, agus codanna nasctha a fháil. Úsáideann sé breis spáis ná DFS (íobairt iomlán ag an am). Rianaigh i gcónaí visited nó d'fhéadfadh tú foluain go deo ar thimthriallta.
Cén fáth go bhfuil tábhacht ann
Is é BFS an algartam do na conairí is gearr nuair a bhíonn gach imeall comhionann — rúta, snámh ar an gréasán, na céimeanna scartha líonra sóisialta.
Tá struchtúr scuaine-bhunaithe, leibhéal-ar-leibhéal bunúsach i bpatrúin taiscéalacha.
Aithneoireacht BFS i gcoinne DFS a thugann duit an uirlis cheart a roghnú do fhadhbanna inroichte, conairí, agus ordúchán.