BFS vs DFS - Diferența dintre ei

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.