Vizualizare sursă pentru „Căutare în lățime”

[[Fișier:Animated_BFS.gif|miniatura|187x187px|Exemplu animat de căutare în lățime]]
'''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”<ref>{{Citat web|url=http://www.graph500.org/specifications#sec-5|publisher=Graph500.org, 2010|titlu=Graph500 benchmark specification (supercomputer performance evaluation)|accessdate=2017-07-31|archive-date=2015-03-26|archive-url=https://web.archive.org/web/20150326055019/http://www.graph500.org/specifications#sec-5|dead-url=yes}}</ref>) și explorează nodurile mai întâi nodurile vecine acestuia, înainte de a trece la vecinii de pe nivelul următor (vecinii vecinilor).

BFS și aplicarea acestuia în găsirea de [[Componentă conexă|componente conexe]] ale grafurilor au fost inventate în 1945 de către [[Konrad Zuse]], în teza sa de doctorat (respinsă) despre limbaj de programare {{Ill-wd|Q34280}}, dar aceasta a fost publicată abia în 1972.<ref>{{Citation|title=Der Plankalkül|year=1972|last=Zuse|first=Konrad|author-link=Konrad Zuse|authorlink=Konrad Zuse|url=http://zuse.zib.de/item/gHI1cNsUuQweHB6|publisher=Konrad Zuse Internet Archive|language=German}}. </ref>
A fost reinventat în 1959 de către {{Ill-wd|Q92882|3=E. F. Moore}}, care l-a folosit pentru a găsi cea mai scurtă cale de ieșire dintr-un labirint,<ref>{{Cite conference|last=Moore|first=Edward F.|author-link=Edward F. Moore|authorlink=Edward F. Moore|year=1959|pages=285–292|title=Proceedings of the International Symposium on the Theory of Switching|publisher=Harvard University Press}}</ref><ref name="skiena">{{Citat carte|nume=Skiena|prenume=Steven|legătură-autor=Steven Skiena|an=2008|titlu=The Algorithm Design Manual|pagină=480|editură=Springer|doi=10.1007/978-1-84800-070-4_4}}</ref>
și {{Ill-wd|Q1645643|3=descoperită independent}} de C. Y. Lee ca algoritm de {{Ill-wd|Q1446839|3=rutare a cablajelor}} (publicat în 1961).<ref>{{Cite conference|last=Leiserson|last1=Leiserson|last2=Schardl|first1=Charles E.|first=Charles E.|first2=Tao B.|authorlink1=Charles E. Leiserson|year=2010|conference=ACM Symp. on Parallelism in Algorithms and Architectures|title=A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers)|url=http://supertech.csail.mit.edu/papers/pbfs.pdf}}</ref><ref>{{Citat știre|title=An Algorithm for Path Connections and Its Applications|url=http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=5219222|prenume=C. Y.|nume=Lee|journal=IRE Transactions on Electronic Computers|work=IRE Transactions on Electronic Computers|an=1961}}</ref>

== Pseudocod ==
'''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:<source lang="java">
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)
</source>

=== Mai multe detalii ===
Această implementare nerecursivă este similară cu cea nerecursivă a [[Căutare în adâncime|căutării în adâncime]], dar are două diferențe față de acesta:
# Utilizează o coadă (First In First Out), în loc de [[Stivă (structură de date)|stivă]]; și
# 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.

=== Exemplu ===
Acesta este un exemplu de arbore de căutare în lățime obținut prin rularea BFS pornind de la ''Frankfurt'':
[[Fișier:MapGermanyGraph.svg|centru|miniatura|252x252px|Graf pe baza unei hărți a [[Germania|Germaniei]] cu unele conexiuni între orașe]]
[[Fișier:GermanyBFS.svg|centru|miniatura|250x250px|Arborele de căutare în lățime obținut atunci când se rulează BFS pe graful de mai sus, pornind de la [[Frankfurt pe Main|Frankfurt]]]]

== Analiza ==

=== Complexitatea în timp și spațiu ===
Complexitatea în timp poate fi exprimată ca <math />deoarece  în cel mai rău caz vor fi analizate fiecare nod și fiecare muchie. <math /> este numărul de noduri și <math /> este numărul de muchii din graf.  <math /> poate varia între <math /> și <math />, în funcție de cât de rar este graful dat la intrare.<ref name="clrs">{{Introduction to Algorithms|edition=2|chapter=22.2 Breadth-first search|pages=531–539}}</ref>

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 <math />, unde <math /> este {{Ill-wd|Q4049983|3=cardinalul}} mulțimii nodurilor. Aceasta în plus față de spațiul necesar pentru graful în sine, care poate varia în funcție de {{Ill-wd|Q2479726|3=reprezentarea grafului}} 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 {{Math|d}} față de nodul de start (măsurată în număr de muchii) solicită BFS un timp și un spațiu de {{Math|''O''(''b''<sup>''d'' + 1</sup>)}}, unde {{Math|b}} este „factorul de ramificare” al grafului (gradul exterior mediu).<ref>{{Cite AIMA|edition=2}}</ref>{{Rp|81}}

=== Completitudine și optimalitate ===
Î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ță artificială|inteligența artificială]], datele de intrare pot fi o {{Ill-wd|Q6007291|3=reprezentare implicită}} 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ă.<ref name="coppin">Coppin, B. (2004). Artificial intelligence illuminated. Jones & Bartlett Learning. pp.&nbsp;79–80.</ref>

== Ordonarea BFS ==
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 <math>G=(V,E)</math> un graf cu <math>n</math> noduri și fie <math>N(v)</math> mulțimea vecinilor lui <math>v</math>.
Pentru <math>\sigma=(v_1,\dots,v_m)</math> o listă de elemente distincte din <math>V</math>, și pentru <math>v\in V\setminus\{v_1,\dots,v_m\}</math>, fie <math>\nu_{\sigma}(v)</math> cel mai mic <math>i</math> astfel încât <math>v_i</math> este vecin cu <math>v</math>, dacă există <math>i</math>, și <math>\infty</math> altfel.

Fie <math>\sigma=(v_1,\dots,v_n)</math> o enumerare a nodurilor lui <math>V</math>.
Enumerarea <math>\sigma</math> este o ordonare BFS (cu originea <math>v_1</math>) dacă, pentru orice <math>1<i\le n</math>, <math>v_i</math> este nodul <math>w\in V\setminus\{v_1,\dots,v_i-1\}</math> astfel încât <math>\nu_{(v_1,\dots,v_{i-1})}(w)</math> este minimal. Echivalent, <math>\sigma</math> este o ordonare BFS dacă, oricare ar fi <math>1\le i<j<k\le n</math> cu <math>v_i\in N(v_j)\setminus N(v_k)</math>, există un vecin <math>v_m</math> al lui <math>v_j</math> astfel încât <math>m<i</math>. 

== Aplicații ==
Căutarea în lățime poate fi folosită pentru a rezolva multe probleme din teoria grafurilor, de exemplu:
* {{Ill-wd|Q322202|3=Garbage collection}}, {{Ill-wd|Q5091169|3=algoritmul lui Cheney}}
* Găsirea celui mai scurt drum între două noduri ''u'' și ''v'', cu lungimea măsurată prin numărul de muchii (avantaj față de [[Căutare în adâncime|căutarea în adâncime]])<ref>{{Citat carte|nume=Aziz|nume2=Prakash|prenume=Adnan|prenume2=Amit|dată=2010|titlu=Algorithms for Interviews|pagină=144|capitol=4. Algorithms on Graphs|isbn=1453792996}}</ref>
* Reducerea benzii {{Ill-wd|Q1146458|3=reverse Cuthill–McKee}}
* [[Algoritmul Ford Fulkerson|Metoda Ford–Fulkerson]] de calcul a {{Ill-wd|Q2585642|3=debitului maxim}} printr-o {{Ill-wd|Q1412924|3=rețea de debit}}
* Serializarea/deserializarea unui arbore binar vs serializarea în ordine sortată, permite reconstruirea arborelui într-o manieră eficientă.
* Construcția ''funcției de eșec'' a identificatorului de șabloane {{Ill-wd|Q402342}}.
* Testarea [[Graf bipartit|bipartitudinii unui graf]].

== Bibliografie ==
<references />
{{refbegin}}
* {{Citation
 | last=Knuth
 | first=Donald E.
 | title=The Art of Computer Programming Vol 1. 3rd ed.
 | publisher=Addison-Wesley
 | place=Boston
 | year=1997
 | ISBN=0-201-89683-4
 | url=http://www-cs-faculty.stanford.edu/~knuth/taocp.html
 | access-date=2017-07-31
 | archive-date=2008-09-04
 | archive-url=https://web.archive.org/web/20080904163709/http://www-cs-faculty.stanford.edu/~knuth/taocp.html
 | dead-url=yes
 }}
{{refend}}

== Legături externe ==
{{Commonscat}}
* [http://opendatastructures.org/versions/edition-0.1e/ods-java/12_3_Graph_Traversal.html#SECTION001531000000000000000 Open Data Structures - Secțiunea 12.3.1 - Căutarea în lățime]

[[Categorie:Algoritmi]]