Ce este BFS?
BFS este un algoritm care este utilizat pentru graficarea datelor sau căutarea în arborele sau structurile de traversare. Algoritmul vizitează și marchează în mod eficient toate nodurile cheie într-un grafic într-o manieră exactă în funcție de latură.
Acest algoritm selectează un singur nod (punct inițial sau sursă) într-un grafic și apoi vizitează toate nodurile adiacente nodului selectat. Odată ce algoritmul vizitează și marchează nodul de pornire, acesta se deplasează spre cele mai apropiate noduri nevizitate și le analizează.
Odată vizitate, toate nodurile sunt marcate. Aceste iterații continuă până când toate nodurile grafului au fost vizitate și marcate cu succes. Forma completă a BFS este prima căutare a lățimii.
În acest BSF vs. Tutorial arborele binar DFS, veți învăța:
- Ce este BFS?
- Ce este DFS?
- Exemplu de BFS
- Exemplu de DFS
- Diferența dintre arborele binar BFS și DFS
- Aplicații ale BFS
- Aplicații ale DFS
Ce este DFS?
DFS este un algoritm pentru găsirea sau parcurgerea graficelor sau copacilor în direcția de adâncime. Executarea algoritmului începe de la nodul rădăcină și explorează fiecare ramură înainte de a urmări înapoi. Acesta folosește o structură de date stivă pentru a vă aminti, pentru a obține vârful ulterior și pentru a începe o căutare, ori de câte ori apare o fundătură în orice iterație. Forma completă a DFS este prima căutare în adâncime.
Exemplu de BFS
În următorul exemplu de DFS, am folosit un grafic cu 6 vârfuri.
Exemplu de BFS
Pasul 1)
Aveți un grafic de șapte numere cuprinse între 0 și 6.
Pasul 2)
0 sau zero a fost marcat ca nod rădăcină.
Pasul 3)
0 este vizitat, marcat și inserat în structura de date a cozii.
Pasul 4)
Restul de 0 noduri adiacente și nevizitate sunt vizitate, marcate și inserate în coadă.
Pasul 5)
Iterațiile de traversare se repetă până când toate nodurile sunt vizitate.
Exemplu de DFS
În următorul exemplu de DFS, am folosit un grafic nedirecționat având 5 vârfuri.
Pasul 1)
Am început de la vârful 0. Algoritmul începe prin introducerea acestuia în lista vizitată și punerea simultană a tuturor vârfurilor adiacente în structura de date numită stivă.
Pasul 2)
Veți vizita elementul, care este în partea de sus a stivei, de exemplu, 1 și veți merge la nodurile sale adiacente. Este pentru că 0 a fost deja vizitat. Prin urmare, vizităm vârful 2.
Pasul 3)
Vertex 2 are un vârf nevizitat în apropiere în 4. Prin urmare, adăugăm acest lucru în stivă și îl vizităm.
Pasul 4)
În cele din urmă, vom vizita ultimul vârf 3, nu are noduri alăturate nevăzute. Am finalizat traversarea graficului folosind algoritmul DFS.
Diferența dintre arborele binar BFS și DFS
| BFS | DFS |
| BFS găsește cea mai scurtă cale către destinație. | DFS merge în partea de jos a unui subarborescent, apoi înapoi. |
| Forma completă a BFS este Breadth-First Search. | Forma completă a DFS este Depth First Search. |
| Folosește o coadă pentru a urmări următoarea locație de vizitat. | Folosește un teanc pentru a urmări următoarea locație de vizitat. |
| BFS traversează în funcție de nivelul arborelui. | DFS traversează în funcție de adâncimea copacului. |
| Este implementat folosind lista FIFO. | Este implementat folosind lista LIFO. |
| Necesită mai multă memorie în comparație cu DFS. | Necesită mai puțină memorie în comparație cu BFS. |
| Acest algoritm oferă cea mai mică soluție de cale. | Acest algoritm nu garantează cea mai superficială soluție de cale. |
| Nu este nevoie de backtracking în BFS. | Este nevoie de backtracking în DFS. |
| Nu puteți fi niciodată prins în bucle finite. | Poți fi prins în bucle infinite. |
| Dacă nu găsiți niciun obiectiv, poate fi necesar să extindeți mai multe noduri înainte de a găsi soluția. | Dacă nu găsiți niciun obiectiv, poate avea loc retragerea nodului frunzei. |
Aplicații ale BFS
Iată, sunt aplicațiile BFS:
Grafice neponderate:
Algoritmul BFS poate crea cu ușurință cea mai scurtă cale și un arbore care se întinde minim pentru a vizita toate vârfurile graficului în cel mai scurt timp posibil cu o precizie ridicată.
Rețele P2P:
BFS poate fi implementat pentru a localiza toate cele mai apropiate sau vecine noduri într-o rețea de la egal la egal. Astfel veți găsi datele necesare mai repede.
Crawlerele web:
Motoarele de căutare sau crawlerele web pot construi cu ușurință mai multe niveluri de indexuri utilizând BFS. Implementarea BFS începe de la sursă, care este pagina web, apoi vizitează toate linkurile din sursa respectivă.
Difuzare în rețea:
Un pachet difuzat este ghidat de algoritmul BFS pentru a găsi și a ajunge la toate nodurile pentru care are adresa.
Aplicații ale DFS
Iată aplicațiile importante ale DFS:
Grafic ponderat:
Într-un grafic ponderat, traversarea graficului DFS generează cel mai scurt arbore de cale și arborele minim de întindere.
Detectarea unui ciclu într-un grafic:
Un grafic are un ciclu dacă am găsit o margine din spate în timpul DFS. Prin urmare, ar trebui să rulăm DFS pentru grafic și să verificăm marginile din spate.
Găsirea drumului:
Ne putem specializa în algoritmul DFS pentru a căuta o cale între două vârfuri.
Sortare topologică:
Este utilizat în principal pentru programarea lucrărilor din dependențele date din grupul de locuri de muncă. În informatică, este utilizat în planificarea instrucțiunilor, serializarea datelor, sinteza logică, determinarea ordinii sarcinilor de compilare.
Căutarea componentelor puternic conectate ale unui grafic:
S-a folosit în graficul DFS atunci când există o cale de la fiecare vârf din grafic la alte vârfuri rămase.
Rezolvarea puzzle-urilor cu o singură soluție:
Algoritmul DFS poate fi ușor adaptat pentru a căuta toate soluțiile la un labirint prin includerea nodurilor pe calea existentă în setul vizitat.
DIFERENȚE CHEIE:
- BFS găsește cea mai scurtă cale către destinație, în timp ce DFS merge în partea de jos a unui subarborescență, apoi urmărește.
- Forma completă a BFS este Breadth-First Search, în timp ce forma completă a DFS este Depth First Search.
- BFS folosește o coadă pentru a urmări următoarea locație de vizitat. întrucât DFS folosește un teanc pentru a urmări următoarea locație de vizitat.
- BFS traversează în funcție de nivelul arborelui, în timp ce DFS traversează în funcție de adâncimea arborelui.
- BFS este implementat folosind lista FIFO pe de altă parte DFS este implementat utilizând lista LIFO.
- În BFS, nu puteți fi niciodată prins în bucle finite, în timp ce în DFS puteți fi prins în bucle infinite.