BFS eksploron një graf nivel për nivel, vizitim të gjithë fqinjët e një nyje para se të lëvizë më thellë. Përdor një radhë dhe gjen shtegun më të shkurtër (burimet më të rralla) në grafe pa peshë.
Filloni në një burim, futeni në radhë, pastaj në mënyrë të përsëritur hiqni një nyje, vizitoni fqinjët e tij të pavizituar, dhe futini në radhë. Një grup visited parandalon ri-vizitimin.
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']
Përdorni BFS për shtegim më të shkurtër në grafe pa peshë, përshkrim sipas nivelit, dhe gjetje të komponentëve të lidhur. Përdor më shumë memorie sesa DFS (një kufiri i tërë në të njëjtën kohë). Gjithmonë gjurmoni visited ose mund të bini në unaza në cikle.
BFS është algoritmi për shteget më të shkurtër kur çdo brinjë ka të njëjtën peshë — rrutat, Web crawling, shkallët e ndarjes në rrjete shoqerore.
Struktura e saj bazuar në radhë dhe nivel për nivel është një model themelor i përshkimit.
Njohuritë e BFS kundrejt DFS ju lejojnë të zgjidhni mjetin e duhur për arritshmëri, shteget dhe problemet e rendit.
Një bibliotekë pyetjesh intervistash IT me përgjigje të detajuara — nga Junior te Senior.
Dhuro