BFS vs DFS - Diferența dintre ei
Diferența cheie între BFS și DFS
- BFS găsește cea mai scurtă cale către destinație, în timp ce DFS merge în partea de jos a unui subarboresc, apoi face înapoi.
- 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 ține evidența următoarei locații de vizitat. în timp ce DFS folosește o stivă pentru a ține evidența următoarei locații 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 o listă FIFO; pe de altă parte, DFS este implementat folosind o listă LIFO.
- În BFS, nu poți fi niciodată prins în bucle finite, în timp ce în DFS, poți fi prins în bucle infinite.
Ce este BFS?
BFS este un algoritm care este utilizat pentru a reprezenta grafice de date sau pentru a căuta în arbore sau pentru a traversa structuri. 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. 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. Forma completă a BFS este căutarea pe lățimea întâi.
Ce este DFS?
DFS este un algoritm pentru găsirea sau traversarea graficelor sau arborilor în direcția adâncimii. Execuția algoritmului începe la nodul rădăcină și explorează fiecare ramură înainte de a reveni. Folosește o structură de date stiva pentru a reține, pentru a obține vârful următor și pentru a începe o căutare, ori de câte ori apare un punct mort în orice iterație. Forma completă a DFS este căutarea în profunzime.
Diferența dintre arborele binar BFS și DFS
Iată diferențele importante dintre 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 subarboresc, apoi dă înapoi. |
Forma completă a BFS este Breadth-First Search. | Forma completă a DFS este Depth First Search. |
Folosește o coadă pentru a ține evidența următoarei locații de vizitat. | Folosește o stivă pentru a ține evidența următoarei locații de vizitat. |
BFS traversează în funcție de nivelul copacului. | DFS traversează în funcție de adâncimea arborelui. |
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 mică soluție de cale. |
Nu este nevoie de întoarcere în BFS. | Este nevoie de backtracking în DFS. |
Nu poț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 multe noduri înainte de a găsi soluția. | Dacă nu găsiți niciun obiectiv, poate apărea întoarcerea nodului frunză. |
Exemplu de BFS
În următorul exemplu de BFS, am folosit graficul având 6 vârfuri.
Exemplu de BFS
Pas 1)
Aveți un grafic cu șapte numere cuprinse între 0 și 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)
Cele 0 noduri adiacente și nevizitate rămase sunt vizitate, marcate și inserate în coadă.
Pas 5)
Iterațiile de traversare sunt repetate 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.
Pas 1)
Am pornit de la vârful 0. Algoritmul începe prin a-l introduce în lista vizitată și, simultan, a pune toate vârfurile adiacente în structură de date numit stivă.
Pas 2)
Veți vizita elementul, care se află în partea de sus a stivei, de exemplu, 1 și veți merge la nodurile adiacente. Se datorează faptului că 0 a fost deja vizitat. Prin urmare, vizităm vârful 2.
Pas 3)
Vertex 2 are un vârf nevizitat în apropiere în 4. Prin urmare, îl adăugăm în stivă și îl vizităm.
Pas 4)
În cele din urmă, vom vizita ultimul vârf 3, acesta nu are noduri adiacente nevizitate. Am finalizat parcurgerea graficului folosind algoritmul DFS.
Aplicații ale BFS
Iată aplicațiile BFS:
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 graficului în cel mai scurt timp posibil, cu o precizie ridicată.
Rețele P2P
BFS poate fi implementat pentru a localiza toate nodurile cele mai apropiate sau învecinate într-o rețea peer to peer. Aceasta va găsi mai rapid datele necesare.
Crawlerele web
Motoare de cautare sau crawlerele web pot construi cu ușurință mai multe niveluri de indici folosind BFS. Implementarea BFS începe de la sursă, care este pagina web, apoi vizitează toate linkurile din acea 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.
Aplicații ale DFS
Iată aplicații importante ale DFS:
Graficul ponderat
Într-un grafic ponderat, traversarea graficului DFS generează cel mai scurt arbore de cale și arborele de acoperire minim.
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 pentru 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 folosit în principal pentru programarea locurilor de muncă din dependențele date dintre grupul de locuri de muncă. În informatică, este utilizat în programarea instrucțiunilor, serializarea datelor, sinteza logică, determinarea ordinii sarcinilor de compilare.
Căutarea componentelor puternic conectate ale unui grafic
Este 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 adaptat cu ușurință pentru a căuta toate soluțiile într-un labirint prin includerea nodurilor pe calea existentă în setul vizitat.