Breadth First Search (BFS) este unul dintre cei mai cunoscuți algoritmi pentru căutarea sau traversarea unui arbore sau a unei structuri de date grafice. În acest tutorial, vom învăța pe scurt cum funcționează BFS și vom explora un model de bază care poate fi utilizat pentru a rezolva unele probleme ușoare și medii din Leetcode.

Să începem, nu-i așa?

Deci, știm cu toții că un grafic este un set de vârfuri și muchii: G = {V, E}. Parcurgerea unui grafic înseamnă a vizita fiecare vârf și fiecare margine exact o dată în mod ordonat.

În BFS, ni se cere să parcurgem graficul în funcție de lățime sau nivel. Aceasta înseamnă că mai întâi ne-am deplasa pe orizontală și am vizita toate nodurile stratului curent înainte de a trece la următorul strat.

Prin urmare, ori de câte ori ni se cere să facem ceva traversarea ordinii de nivel, putem folosi tehnica BFS.

Prima cautare in latime Un ghid de traversare a

În BFS, am începe să traversăm de la 1 (nodul rădăcină) și să-i vizităm nodurile copil 8, 5 și 2. Le-am stoca în ordinea în care au fost vizitate. Acest lucru ne-ar permite să vizităm mai întâi nodurile copilului de 8 (adică 6, 4 și 3), apoi de 5 (adică nul), apoi de 2 (adică 9) și așa mai departe.

Implementare

Pentru a implementa BFS, a coadă se folosește structura datelor. Coada stochează nodul și îl marchează ca „vizitat” până când sunt marcate toate vârfurile adiacente.

Coada urmează metoda First In First Out (FIFO). Aceasta înseamnă că vecinii nodului vor fi vizitați în ordinea în care au fost introduși.

Vrajă magică BFS:

  1. Adăugați un nod la coadă
  2. Eliminați nodul
  3. Recuperați vecinii nevizitați ai nodului eliminat, adăugați-i la coadă
  4. Repetați pașii 1, 2 și 3 atâta timp cât coada nu este goală.

Acum să ne uităm la câteva probleme Leetcode și să aplicăm ceea ce am învățat.

102. Transversarea ordinii binare a nivelului arborelui (dificultate: medie)

Întrebarea ne cere să parcurgem graficul și să imprimăm nodurile de la fiecare nivel într-o listă legată. Pentru a-l rezolva, tot ce trebuie să facem este să ne aplicăm vraja magică!

1611676205 222 Prima cautare in latime Un ghid de traversare a

Asigurați-vă că înțelegeți bine codul, deoarece acesta este șablon de bază vom folosi pentru a rezolva mai multe probleme. Deci, să o parcurgem.

În codul de mai sus, am introdus la început nodul rădăcină în coadă. Deși coada nu este goală, am eliminat acest nod din coadă și i-am inserat copilul din stânga și din dreapta în coadă.

Dar înainte de aceasta, am verificat dacă fiecare dintre copiii săi este nul sau nu. Dacă este nul, am fi obținut o excepție a indicatorului nul.

Procesul se repetă din nou cu următoarele elemente care rămân în coadă. pentru bucla este menținut pentru a ne oferi lista nodurilor de la fiecare nivel în liste separate separate.

637. Media nivelurilor într-un arbore binar (dificultate: ușoară)

Această întrebare ne spune să găsim valoarea medie a nodurilor la fiecare nivel al unui arbore binar dintr-o matrice. Acest lucru urmează aceeași procedură ca problema noastră anterioară, cu o mică modificare.

1611676206 356 Prima cautare in latime Un ghid de traversare a

După cum puteți vedea, nu am făcut decât să copiem și să lipim codul șablonului. Apoi punem pur și simplu o variabilă sumă în bucla for care ne poate da suma valorilor nodului la fiecare nivel. Aceasta este ceea ce vom folosi pentru a calcula media dorită.

429. Traversarea ordinii nivelului copacului N-ari (dificultate: medie)

Un copac în care are fiecare nod nu mai mult de Numărul N de copii este numit copac N-ari.

1611676206 941 Prima cautare in latime Un ghid de traversare a

Aceasta urmează exact aceeași procedură ca și traversarea unui arbore binar, cu excepția faptului că aici, introducem toți copiii unui nod în coadă. Amintiți-vă că, în timp ce rezolvăm probleme legate de arborele binar, am inserat doar copiii din stânga și din dreapta unui nod dat în coadă.

Asta e tot! Sper că acest lucru te-a ajutat să înțelegi mai bine BFS și că ți-a plăcut tutorialul. Vă rugăm să recomandați această postare dacă credeți că ar putea fi utilă pentru altcineva!