BFS peržiūri grafiką lygis po lygio, aplankydama visus mazgo kaimynus prieš einant giliau. Jis naudoja eilę ir randa trumpiausią kelią (mažiausiai briaunų) nesusvarstytuose grafikuose.
Pradėkite nuo šaltinio, įdėkite jį į eilę, tada pakartotinai išimkite mazgą, aplankykite jo neaplandytus kaimynus ir jų įdėkite. visited aibė nuo naujo aplankimo.
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']
Naudokite BFS trumpiausiam keliui nesusvarstytuose grafikuose, lygio tvarka apeigas ir sujungtų komponentų radimą. Sunaudoja daugiau atminties nei DFS (visą sieną iš karto). Visada sekite visited, arba jūs gali užsikliudyti cikle.
BFS yra algoritmas trumpiausiems keliams, kai kiekviena briauna yra vienodai svarbi — maršrutizavimas, interneto žvejyba, socialinio tinklo atskyrimo laipsnis.
Jo eilės pagrindimas ir lygio po lygio struktūra yra pagrindinė apėjimo schema.
BFS ir DFS žinojimas leidžia pasirinkti tinkamą įrankį pasiekamumui, keliams ir rūšiavimo problemoms.