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”) ș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 componente conexe ale grafurilor au fost inventate în 1945 de către Konrad Zuse, în teza sa de doctorat (respinsă) despre limbaj de programare , dar aceasta a fost publicată abia în 1972.. A fost reinventat în 1959 de către , care l-a folosit pentru a găsi cea mai scurtă cale de ieșire dintr-un labirint, și de C. Y. Lee ca algoritm de (publicat în 1961).
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: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 Această implementare nerecursivă este similară cu cea nerecursivă a 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ă; ș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: centru|miniatura|252x252px|Graf pe baza unei hărți a Germaniei cu unele conexiuni între orașe 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
Analiza
Complexitatea în timp și spațiu 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.
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 mulțimii nodurilor. Aceasta în plus față de spațiul necesar pentru graful în sine, care poate varia în funcție de 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 față de nodul de start (măsurată în număr de muchii) solicită BFS un timp și un spațiu de , unde este „factorul de ramificare” al grafului (gradul exterior mediu).
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ța artificială, datele de intrare pot fi o 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ă.Coppin, B. (2004). Artificial intelligence illuminated. Jones & Bartlett Learning. pp. 79–80.
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 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 Căutarea în lățime poate fi folosită pentru a rezolva multe probleme din teoria grafurilor, de exemplu: Garbage collection, 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ăutarea în adâncime) Reducerea benzii Metoda Ford–Fulkerson de calcul a printr-o 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 . Testarea bipartitudinii unui graf.
Bibliografie
Legături externe
Open Data Structures - Secțiunea 12.3.1 - Căutarea în lățime
Categorie:Algoritmi