Căutarea în lățime (BFS)
Aruncați o piatră într-un lac și undele se răspândesc uniform, în inele. Căutarea în lățime explorează un graf la fel: mai întâi tot ce e la un pas de start, apoi tot ce e la doi pași și așa mai departe. Tocmai această ordine simplă o face să găsească cele mai scurte drumuri.
Ideea
Un graf este o mulțime de noduri unite prin muchii: locuri și drumuri, oameni și prietenii, căsuțele unui labirint și deschiderile dintre ele. Căutarea în lățime răspunde la întrebarea: pornind de aici, unde pot ajunge și în cât de puțini pași? Ea păstrează o coadă de noduri care urmează să fie vizitate. Dacă nodurile se iau din față și cele noi se adaugă la capăt, nodurile sunt tratate în ordinea în care au fost descoperite.
Pas cu pas
Puneți startul în coadă, la distanța 0. Luați nodul din față. Pentru fiecare vecin care nu a fost văzut, notați distanța lui ca fiind cu unu mai mare decât a nodului curent, rețineți nodul curent ca drumul prin care a fost atins și adăugați-l la capătul cozii. Săriți vecinii văzuți deja. Repetați până când coada se golește sau ținta este atinsă.
Un exemplu
Luați un graf cu muchiile A–B, A–C, B–D, C–D, C–E și D–F și porniți din A. Când A este scos din coadă, se găsesc B și C la distanța 1. B găsește D la distanța 2. C constată că D a fost deja văzut și găsește E la distanța 2. D găsește F la distanța 3. E și F nu găsesc nimic nou, iar coada este goală. Urmând nodurile reținute înapoi de la F se obține F ← D ← B ← A, deci un drum minim de la A la F este A → B → D → F, lung de trei muchii.
De ce distanțele sunt corecte
Fiecare nod la distanța 1 intră în coadă înaintea oricărui nod la distanța 2, fiecare nod la distanța 2 înaintea oricărui nod la distanța 3 și așa mai departe, pentru că vecinii unui nod intră în coadă abia când nodul însuși iese din ea. Așadar, primul drum care atinge un nod are cele mai puține muchii, iar BFS nu trebuie niciodată să corecteze o distanță. Fiecare nod este luat o dată și fiecare muchie este examinată de la ambele capete, deci munca crește cu numărul de noduri plus numărul de muchii.
Istorie și utilizări
Konrad Zuse a descris căutarea în lățime în 1945, în lucrarea despre limbajul său Plankalkül, publicată abia în 1972. Edward F. Moore a reinventat-o în 1959 pentru a găsi cel mai scurt drum de ieșire dintr-un labirint, iar C. Y. Lee a folosit-o în 1961 pentru a trasa firele pe plăcile de circuit. Astăzi găsește cele mai puține mutări în puzzle-uri, gradele de separare în rețelele sociale, paginile la care un crawler web ajunge primele și cea mai apropiată celulă liberă în jocuri. Când muchiile au lungimi, algoritmul lui Dijkstra o generalizează.
Explorați
Deschideți aplicația și apăsați Pas. Nodul vizitat acum este evidențiat, nodurile care așteaptă în coadă sunt albastre, iar nodurile vizitate sunt verzi, fiecare cu distanța sa. Coada este afișată sub graf, începând cu fața ei. Comutați clicul pe Țintă și alegeți un nod pentru a vă opri acolo și a vedea cel mai scurt drum sau creați un graf nou cu mai multe noduri și muchii.
Întrebări frecvente
Care este complexitatea în timp a BFS?
O(V + E) pentru V noduri (vertices) și E muchii (edges): fiecare nod intră și iese din coadă o singură dată, iar fiecare muchie este examinată de la ambele capete. Necesită O(V) memorie suplimentară pentru coadă și distanțe.
De ce folosește BFS o coadă?
Pentru că regula primul intrat, primul ieșit păstrează nodurile în ordinea în care au fost descoperite, adică în ordinea distanței lor. Cu o stivă în locul cozii, căutarea ar coborî mai întâi în adâncime: aceasta este căutarea în adâncime.
Poate BFS găsi cele mai scurte drumuri în grafuri ponderate?
În general, nu: numără muchiile, nu lungimile lor. Pentru grafuri ponderate fără muchii negative, folosiți algoritmul lui Dijkstra. Dacă fiecare pondere este 0 sau 1, funcționează o variantă numită 0-1 BFS.
Unde se folosește BFS?
La rezolvarea puzzle-urilor și labirinturilor din cât mai puține mutări, la găsirea prietenilor prietenilor în rețelele sociale, la parcurgerea webului nivel cu nivel, la difuzarea mesajelor în rețele și ca element de bază pentru alți algoritmi, de exemplu pentru găsirea fluxului maxim.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați căutarea în lățime