BFS აკვირდება გრაფს დონე-დონეზე, პირველ რიგში ეწვევა ყველა მეზობელ კვანძს, სანამ უფრო ღრმად წახდეს. იყენებს რიგს და პოულობს უმოკლეს ბილიკი (ყველაზე ნაკლები კიდეები) წონის გარეშე გრაფებში.
დაიწყეთ წყაროდან, დაამატეთ ის რიგში, შემდეგ განმეორებით გამოიღეთ კვანძი, ეწვიეთ მის მოუსულელ მეზობლებს და დაამატეთ მათი. visited სიმრავლე ხელს უშლის ხელახლა ვიზიტირებას.
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']
გამოიყენეთ BFS უმოკლესი ბილიკი წონის გარეშე გრაფებში, დონის რიგის გასავლელი და დაკავშირებული კომპონენტების ძებნა. იყენებს მეტ მეხსიერებას, ვიდრე DFS (მთელი საზღვარი ერთდროულად). ყოველთვის ზედმეტად იყავით visited ან შეიძლება უსასრულო ციკლი მოხდეს.
BFS არის ის ალგორითმი უმოკლესი ბილიკებისთვის, როდესაც ყველა კიდე თანაბრად მნიშვნელოვანია — მარშრუტიზაცია, ვებ-კრალეტი, სოციალური ქსელის გამყოფი ხარისხი.
მისი რიგ-ბაზირებული, დონე-დონეზე სტრუქტურა არის ფундამენტური გასავლელი ნიმუში.
BFS და DFS ცოდნა საშუალებას გაძლევთ აირჩიოთ სწორი ხელსაწყო მიღწევადობა, ბილიკი და დალაგების პრობლემებისთვის.