Căutare în lățime
From Wikipedia, the free encyclopedia
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).
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/4/46/Animated_BFS.gif)
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]