Breadth-first search (BFS)
Në shqip: Kërkimi në gjerësi
ShpjegimiSQ
BFS e eksploron një graf nivel pas niveli: së pari të gjithë fqinjët e afërt, pastaj fqinjët e tyre, e kështu me radhë, duke përdorur një radhë (queue). Në grafe pa pesha, gjen rrugën më të shkurtër.
EnglishEN
BFS explores a graph level by level: first all the nearby neighbours, then their neighbours, and so on, using a queue. In unweighted graphs, it finds the shortest path.
Si ta mendosh
Si valët kur hedh një gur në liqen: zgjerohen rreth e qark, një rreth pas tjetrit.
Lexoje në anglisht
Like ripples when you throw a stone in a lake: they spread out ring after ring.
Shembull kodipython
def bfs(graf, fillimi): # deque nga collections
pare, radha = {fillimi}, deque([fillimi])
while radha:
for f in graf[radha.popleft()]:
if f not in pare: pare.add(f); radha.append(f)