Căutarea (parcurgerea) în lățime (BFS) este un algoritm pentru parcurgerea sau căutarea într-o structură de date de tip arbore sau graf. Aceasta începe cu rădăcina arborelui (sau cu un nod arbitrar dintr-un graf, uneori denumit „cheie de căutare”[1]) și explorează nodurile mai întâi nodurile vecine acestuia, înainte de a trece la vecinii de pe nivelul următor (vecinii vecinilor).

Exemplu animat de căutare în lățime

BFS și aplicarea acestuia în găsirea de componente conexe ale grafurilor au fost inventate în 1945 de către Konrad Zuse, în teza sa de doctorat (respinsă) despre limbaj de programare Plankalkül⁠(d), dar aceasta a fost publicată abia în 1972.[2] A fost reinventat în 1959 de către E. F. Moore⁠(d), care l-a folosit pentru a găsi cea mai scurtă cale de ieșire dintr-un labirint,[3][4] și descoperită independent⁠(d) de C. Y. Lee ca algoritm de rutare a cablajelor⁠(d) (publicat în 1961).[5][6]

Pseudocod

modificare

Intrare: Un graf Graph și un nod inițial root al lui Graph

Ieșire: Starea finală. Legăturile părinte urmează calea cea mai scurtă înapoi la root

O implementare nerecursivă a căutării în lățime:

Breadth-First-Search(Graph, root):
    
    create empty set S
    create empty queue Q      

    add root to S
    Q.enqueue(root)                      

    while Q is not empty:
        current = Q.dequeue()
        if current is the goal:
            return current
        for each node n that is adjacent to current:
            if n is not in S:
                add n to S
                n.parent = current
                Q.enqueue(n)

Mai multe detalii

modificare

Această implementare nerecursivă este similară cu cea nerecursivă a căutării în adâncime, dar are două diferențe față de acesta:

  1. Utilizează o coadă (First In First Out), în loc de stivă; și
  2. Verifică dacă un nod a fost descoperit înainte de a-l pune în coadă, în loc să amâne această verificare până la scoaterea nodului din coadă.

Coada Q conține frontiera de-a lungul căreia algoritmul efectuează căutarea.

Mulțimea S este utilizată pentru a urmări care noduri au fost vizitate (necesar pentru o căutare generală prin graf, dar nu și pentru cea prin arbore). La începutul algoritmului, mulțimea este vidă. La sfârșitul algoritmului, acesta conține toate nodurile aflate la o distanță față de rădăcină mai mică decât a nodului căutat.


Părintele atribut fiecărui nod este util pentru accesarea nodurilor pe calea cea mai scurtă, de exemplu, făcând backtracking de la nodul destinație la nodul de pornire, după ce s-a aplicat BFS, și s-au stabilit nodurile predecesoare.

Căutarea în lățime produce așa-numitul arbore de căutare în lățime. Funcționarea unui arbore de căutare în lățime este ilustrată de următorul exemplu.

Acesta este un exemplu de arbore de căutare în lățime obținut prin rularea BFS pornind de la Frankfurt:

 
Graf pe baza unei hărți a Germaniei cu unele conexiuni între orașe
 
Arborele de căutare în lățime obținut atunci când se rulează BFS pe graful de mai sus, pornind de la Frankfurt

Complexitatea în timp și spațiu

modificare

Complexitatea în timp poate fi exprimată ca deoarece în cel mai rău caz vor fi analizate fiecare nod și fiecare muchie. este numărul de noduri și este numărul de muchii din graf.   poate varia între și , în funcție de cât de rar este graful dat la intrare.[7]

Atunci când numărul de noduri din graf este cunoscut dinainte, și se utilizează structuri de date suplimentare pentru a determina care noduri au fost deja adăugate la coadă, complexitatea în spațiu poate fi exprimată ca , unde  este cardinalul⁠(d) mulțimii nodurilor. Aceasta în plus față de spațiul necesar pentru graful în sine, care poate varia în funcție de reprezentarea grafului⁠(d) utilizată de implementarea algoritmului.

Atunci când se lucrează cu grafuri care sunt prea mari pentru a fi stocate în mod explicit (sau infinite), este mai practic să se descrie complexitatea căutării în lățime în alți termeni: găsirea nodurilor aflate la distanța d față de nodul de start (măsurată în număr de muchii) solicită BFS un timp și un spațiu de O(bd + 1), unde b este „factorul de ramificare” al grafului (gradul exterior mediu).[8]:81

Completitudine și optimalitate

modificare

În analiza algoritmilor, datele de intrare ale căutării în lățime sunt presupuse a fi un graf finit, reprezentat în mod explicit ca listă de adiacență sau ceva similar. Cu toate acestea, la aplicarea metodelor de parcurgere a grafurilor folosite în inteligența artificială, datele de intrare pot fi o reprezentare implicită⁠(d) a unui graf infinit. În acest context, o metodă de căutare este descrisă ca fiind completă atunci când este garantat că va găsi o stare căutată, dacă există una. Căutarea în lățime este completă, dar cea în adâncime nu este. Atunci când este aplicată grafurilor infinite reprezentate implicit, căutarea în lățime va găsi în cele din urmă starea căutată, dar cea în lățime poate să se piardă în unele părți din graf în care nu există starea căutată și să nu se mai întoarcă niciodată.[9]

Ordonarea BFS

modificare

O enumerare a nodurilor unui graf este declarată a fi o ordonare BFS dacă este o ieșire posibilă a aplicării BFS pe graful respectiv.

Fie   un graf cu   noduri și fie   mulțimea vecinilor lui  . Pentru   o listă de elemente distincte din  , și pentru  , fie   cel mai mic   astfel încât   este vecin cu  , dacă există  , și   altfel.

Fie   o enumerare a nodurilor lui  . Enumerarea   este o ordonare BFS (cu originea  ) dacă, pentru orice  ,   este nodul   astfel încât   este minimal. Echivalent,   este o ordonare BFS dacă, oricare ar fi   cu  , există un vecin   al lui   astfel încât  .

Aplicații

modificare

Căutarea în lățime poate fi folosită pentru a rezolva multe probleme din teoria grafurilor, de exemplu:

Bibliografie

modificare
  1. ^ „Graph500 benchmark specification (supercomputer performance evaluation)”. Graph500.org, 2010. Arhivat din original la . Accesat în . 
  2. ^ Zuse, Konrad (), Der Plankalkül (în German), Konrad Zuse Internet Archive  Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor).
  3. ^ Moore, Edward F. (). Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. pp. 285–292.  Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor)
  4. ^ Skiena, Steven (). The Algorithm Design Manual. Springer. p. 480. doi:10.1007/978-1-84800-070-4_4. 
  5. ^ Leiserson, Charles E.; Schardl, Tao B. (). A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers) (PDF). ACM Symp. on Parallelism in Algorithms and Architectures.  Mai multe valori specificate pentru |last1= și |last= (ajutor); Mai multe valori specificate pentru |first1= și |first= (ajutor)
  6. ^ Lee, C. Y. (). „An Algorithm for Path Connections and Its Applications”. IRE Transactions on Electronic Computers.  Mai multe valori specificate pentru |work= și |journal= (ajutor)
  7. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford () [1990]. „22.2 Breadth-first search”. Introduction to Algorithms⁠(d) (ed. 2nd). MIT Press and McGraw-Hill. pp. 531–539. ISBN 0-262-03293-7. 
  8. ^ Russell, Stuart; Norvig, Peter () [1995]. Artificial Intelligence: A Modern Approach⁠(d) (ed. 2nd). Prentice Hall. ISBN 978-0137903955. 
  9. ^ Coppin, B. (2004). Artificial intelligence illuminated. Jones & Bartlett Learning. pp. 79–80.
  10. ^ Aziz, Adnan; Prakash, Amit (). „4. Algorithms on Graphs”. Algorithms for Interviews. p. 144. ISBN 1453792996. 

Legături externe

modificare
 
Commons
Wikimedia Commons conține materiale multimedia legate de căutare în lățime