Algoritmul BFS (Broadth First Search) cu EXEMPLU
Sarah Chen
⚡ Rezumat inteligent
Căutarea pe lățime (BFS) este un algoritm care parcurge un graf nivel cu nivel, vizitând toți vecinii unui nod înainte de a se deplasa mai adânc. Folosește o coadă FIFO și găsește cea mai scurtă cale în grafurile neponderate, fără bucle infinite.
Ce este algoritmul BFS (Breadth-First Search)?
Căutarea pe lățime (BFS) este un algoritm utilizat pentru reprezentarea grafică a datelor sau pentru căutarea unui arbore sau a structurilor de traversare. Forma completă a BFS este căutarea pe lățime.
Algoritmul vizitează și marchează eficient toate nodurile cheie într-un grafic într-un mod precis pe lățime. Acest algoritm selectează un singur nod (punct inițial sau sursă) într-un grafic și apoi vizitează toate nodurile adiacente nodului selectat. Amintiți-vă, BFS accesează aceste noduri unul câte unul.
Odată ce algoritmul vizitează și marchează nodul de pornire, apoi se deplasează către cele mai apropiate noduri nevizitate și le analizează. Odată vizitate, toate nodurile sunt marcate. Aceste iterații continuă până când toate nodurile graficului au fost vizitate și marcate cu succes.
Ce este Graph traversals?
O traversare a graficului este o metodologie utilizată în mod obișnuit pentru localizarea poziției vârfurilor în grafic. Este un algoritm avansat de căutare care poate analiza graficul cu viteză și precizie împreună cu marcarea secvenței vârfurilor vizitate. Acest proces vă permite să vizitați rapid fiecare nod dintr-un grafic fără a fi blocat într-o buclă infinită.
Arhitectura algoritmului BFS
- În diferitele niveluri ale datelor, puteți marca orice nod ca nod de pornire sau inițial pentru a începe traversarea. BFS va vizita nodul, îl va marca ca vizitat și îl va plasa în coadă.
- Acum BFS va vizita nodurile cele mai apropiate și nevizitate și le va marca. Aceste valori sunt, de asemenea, adăugate în coadă. Coada funcționează pe Model FIFO.
- În mod similar, nodurile rămase, cele mai apropiate și nevizitate de pe grafic, sunt analizate, marcate și adăugate în coadă. Aceste elemente sunt șterse din coadă pe măsură ce sunt primite și sunt afișate ca rezultat.
De ce avem nevoie de algoritmul BFS?
Există numeroase motive pentru a utiliza algoritmul BFS pentru căutarea în setul de date. Câteva dintre cele mai importante aspecte care fac din acest algoritm prima dvs. alegere sunt:
- BFS este util pentru analiza nodurilor dintr-un grafic și pentru a construi calea cea mai scurtă de parcurgere prin acestea.
- BFS poate parcurge un grafic în cel mai mic număr de iterații.
- Arhitectura algoritmului BFS este simplă și robustă.
- Rezultatul algoritmului BFS deține un nivel ridicat de precizie în comparație cu alți algoritmi.
- Iterațiile BFS sunt fără întreruperi și nu există posibilitatea ca acest algoritm să fie prins într-o problemă de buclă infinită.
Cum funcționează algoritmul BFS?
Traversarea graficelor necesită algoritmului să viziteze, să verifice și/sau să actualizeze fiecare nod nevizitat într-o structură arborescentă. Traversările grafice sunt clasificate în ordinea în care vizitează nodurile din grafic.
Algoritmul BFS începe operația de la primul nod sau de pornire dintr-un grafic și îl parcurge complet. Odată ce traversează cu succes nodul inițial, atunci următorul vârf netraversat din grafic este vizitat și marcat.
Prin urmare, se poate spune că toate nodurile adiacente vârfului curent sunt vizitate și traversate în prima iterație. O metodologie simplă de coadă este utilizată pentru a implementa funcționarea unui algoritm BFS și constă în următorii pași:
Pas 1)
Fiecare vârf sau nod din grafic este cunoscut. De exemplu, puteți marca nodul ca V.
Pas 2)
În cazul în care vârful V nu este accesat, atunci adăugați vârful V în coada BFS.
Pas 3)
Porniți căutarea BFS și, după finalizare, marcați vârful V ca vizitat.
Pas 4)
Coada BFS nu este încă goală, prin urmare eliminați vârful V al graficului din coadă.
Pas 5)
Se recuperează toate vârfurile rămase de pe graf care sunt adiacente vârfului V.
Pas 6)
Pentru fiecare vârf adiacent, să zicem V1, în cazul în care nu a fost încă vizitat, atunci adăugați V1 la coada BFS.
Pas 7)
BFS va vizita V1, îl va marca ca vizitat și îl va șterge din coadă.
Exemplu de algoritm BFS
Pas 1)
Ai un grafic cu șapte numere de la 0 la 6.
Pas 2)
0 sau zero a fost marcat ca nod rădăcină.
Pas 3)
0 este vizitat, marcat și inserat în structura de date a cozii.
Pas 4)
Nodurile rămase, adiacente la 0 și nevizitate, sunt vizitate, marcate și inserate în coadă.
Pas 5)
Iterațiile de traversare sunt repetate până când toate nodurile sunt vizitate.
Regulile algoritmului BFS
Iată câteva reguli importante pentru utilizarea algoritmului BFS:
- O coadă (FIFO – Primul intrat, primul ieșit) structură de date este folosit de BFS.
- Marchezi orice nod din grafic ca rădăcină și începi să parcurgi datele de la acesta.
- BFS traversează toate nodurile din graf și continuă să abandonezeping le ca fiind finalizate.
- BFS vizitează un nod adiacent nevizitat, îl marchează ca finalizat și îl inserează într-o coadă.
- Elimină vârful anterior din coadă în cazul în care nu se găsește niciun vârf adiacent.
- Algoritmul BFS iterează până când toate vârfurile din graf sunt traversate cu succes și marcate ca finalizate.
- Nu există bucle cauzate de BFS în timpul parcurgerii datelor de la orice nod.
Aplicații ale algoritmului BFS
Să aruncăm o privire la unele dintre aplicațiile din viața reală în care o implementare a algoritmului BFS poate fi foarte eficientă.
- Grafice neponderate: Algoritmul BFS poate crea cu ușurință cea mai scurtă cale și un arbore de acoperire minim pentru a vizita toate vârfurile grafului în cel mai scurt timp posibil și cu o precizie ridicată.
- Rețele P2P: BFS poate fi implementat pentru a localiza toate nodurile cele mai apropiate sau vecine dintr-o rețea peer-to-peer. Acest lucru va găsi datele necesare mai rapid.
- Crawlerele web: Motoarele de căutare sau crawlerele web pot construi cu ușurință mai multe niveluri de indici prin utilizarea BFS. Implementarea BFS începe de la sursă, care este pagina web, apoi vizitează toate linkurile din acea sursă.
- Sisteme de navigație: BFS vă poate ajuta să găsiți toate locațiile învecinate din locația principală sau sursă.
- Difuzare în rețea: Un pachet difuzat este ghidat de algoritmul BFS pentru a găsi și ajunge la toate nodurile pentru care are adresa.
