BFS vs DFS: Cunoașteți diferența

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ă.

După vizitare, 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 afla:

• 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 traversarea 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, vom am folosit graficul având 6 vârfuri.

Exemplu de BFS

Pasul 1)

Aveți un grafic de șapte numere cuprinse între 0 – 6.

Pasul 2)

0 sau zero au fost marcate ca nod rădăcină.

Pasul 3)

0 este vizitat, marcat , și inserat în structura de date a cozii.

Pasul 4)

Rămân 0 adiacente și nevizitate nodurile sunt vizitate, marcate și inserate în coadă.

Pasul 5)

Iterațiile de traversare se repetă până 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 plasarea acestuia în lista vizitată și punerea simultană a tuturor vârfurilor sale adiacente în date structură numită stivă.

Pasul 2)

Veți vizita elementul , care este în partea de sus a stivei, de exemplu, 1 și mergeți la nodurile sale adiacente. Acest lucru se datorează faptului 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 nevizitate. Am finalizat traversarea graficului utilizând 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 subarborescență, apoi urmărește .
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 o stivă 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 arborelui.
Este implementat folosind FI Lista FO.	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ă soluția de cale mai superficială.
Nu este nevoie de backtracking în BFS.	Există o nevoie de backtracking în DFS.
Nu puteți fi niciodată prins în bucle finite.	Puteți fi prins în bucle infinite.
Dacă nu găsiți niciun obiectiv, poate fi necesar să extindeți mai multe noduri înainte ca soluția să fie găsită.	Dacă nu găsiți niciun scop, retragerea nodului frunză apar.

Aplicații ale BFS

Iată aplicațiile BFS:

Ne-ponderate Grafice:

Algoritmul BFS poate crea cu ușurință cea mai scurtă cale și un arbore minim de întindere 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 dintr-o rețea peer to peer. Astfel veți găsi datele necesare mai repede.

Web Crawlers:

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 și 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 DFS

Iată aplicații 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 căii:

Ne putem specializa în algoritmul DFS pentru a căuta o cale între două vârfuri.

Sortare topologică:

Este utilizat în principal pentru planificarea lucrărilor din dependențele date din grupul de joburi. Î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 vertexuri 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, incluzând noduri pe calea existentă în setul vizitat.